Das euklidische Steinerbaumproblem in der Ebene


Bachelorarbeit, 2013
53 Seiten, Note: 1,3

Leseprobe

Inhaltsverzeichnis

1 Einleitung
1.1 Was ist ein euklidisches Steinerbaumproblem ?
1.2 Motivation und praktische Relevanz

2 Grundlegende Definitionen
2.1 Definitionen aus der Graphentheorie
2.2 Spezifische Terminologie zum ESTP

3 Geometrische Lösungen zum ESTP
3.1 Lösung des ESTP für n=3
3.2 Lösung des ESTP für n=4

4 Grundlegende Resultate für das ESTP
4.1 Eigenschaften von euklidischen Steinerbäumen
4.2 Die Steinertopologien
4.3 Die Komplexität des Problems

5 Exakte Algorithmen zum ESTP
5.1 Der Melzak-Algorithmus
5.1.1 Die Funktionsweise des Verfahrens
5.1.2 Beschränkung auf volle Steinertopologien
5.1.3 Erzeugung voller Steinerbäume in linearer Laufzeit
5.2 Der Algorithmus von Smith
5.3 Herausforderungen exakter Algorithmen
5.4 Der Geosteiner-Algorithmus

6 Der minimale Spannbaum
6.1 Der Algorithmus von Prim
6.2 MST als Näherung für den euklidischen Steinerbaum

7 Heuristiken zum ESTP
7.1 Die Beasley-Heuristik
7.2 Ausblick: Weitere Heuristiken

8 Zusammenfassung

9 Anhang

Literaturverzeichnis

Abbildungsverzeichnis

1.1 Die Situation im Beispiel

2.1 Zwei Bäume mit identischer Topologie

2.2 Nichtexistenz eines RMT

2.3 Schrumpfen und Aufspalten

2.4 Relativer minimaler Spannbaum und Steinerbaum

2.5 Volle Steinertopologien für vier Terminalpunkte

3.1 Ein Innenwinkel ist größer gleich 120◦

3.2 Die Simpson-Konstruktion

3.3 Die Toricelli-Konstruktion

3.4 Kein Steinerpunkt wird hinzugefügt

3.5 Hinzufügen eines Steinerpunkts

3.6 Hinzufügen zweier Steinerpunkte

4.1 Die Winkelbedingung

4.2 Steinertopologie mit unterliegender voller Topologie

4.3 Teilmengen der Kardinalität vier

4.4 Volle Steinertopologien mit k = 2

4.5 Aus Abb. 4.4. a) erzeugte Steinertopologien

5.1 Veranschaulichung zu den Lemmata 5.1 und 5.3 sowie Satz 5.2

5.2 Die Ausgangssituation

5.3 Die Merging-Phase nach Iteration eins

5.4 Die Merging-Phase nach Iteration zwei

5.5 Die Rekonstruktionsphase nach Iteration eins

5.6 Die Rekonstruktionsphase nach Iteration zwei

5.7 Zerlegung der Steinertopologie in volle Steinerkomponenten

5.8 Ausgangssituation

5.9 Nach erster Iteration

5.10 Nach zweiter Iteration

5.11 Optimallösung

6.1 Anwendung des Prim-Algorithmus

7.1 Terminalpunkte

7.2 Minimaler Spannbaum

7.3 Nach Schritt III

7.4 Nach Schritt IV

7.5 Baum in zweiter Iteration nach Schritt III

7.6 Finales Ergebnis der Heuristik nach zweiter Iteration

7.7 Geclusterte Terminalmenge

7.8 Delaunay Triangulation für zehn Terminale

7.9 Delaunay Triangulation für die geclusterte Terminalmenge

9.1 Steinertopologien mit n=4 und k=0

9.2 Steinertopologien mit n=4 und k=1

9.3 Steinertopologien mit n=4 und k=2

9.4 Beispiel-SMT zu Abschnitt 5.1.3

1 Einleitung

Diese Ausarbeitung beschäftigt sich mit dem euklidischen Steinerbaumproblem in der Ebene, im Folgenden ESTP (für „Euclidean Steiner Tree Problem“) genannt.

1.1 Was ist ein euklidisches Steinerbaumproblem ?

Ziel des ESTP ist es, n fix lokalisierte Punkte in der euklidischen Ebene distanzminimal miteinander zu verbinden. Hierbei können, im Gegensatz zum minimalen SpannbaumProblem (siehe hierfür Kapitel 6), zu den ursprünglichen n Punkten weitere Punkte hinzugefügt werden, um die Länge der Verbindungen zu reduzieren. Zur Lösung des ESTP sind die folgenden Fragen zu beantworten:

- Wieviele zusätzliche Punkte sollen den n Ausgangspunkten gegebenenfalls hinzu- gefügt werden?
- Wo sind diese zusätzlichen Punkte in der euklidischen Ebene einzubetten?
- Wie sollen die Punkte der Gesamtknotenmenge miteinander verbunden werden?

Das ESTP lässt sich also kurz und prägnant charakterisieren. Wie sich im weiteren Verlauf dieser Arbeit herausstellen wird, ist es mit wachsender Problemgröße jedoch schwer eine exakte Lösung für diese Fragestellung zu ermitteln.

1.2 Motivation und praktische Relevanz

Das ESTP findet überall dort Anwendung, wo eine gegebene Anzahl von Punkten in der Ebene distanzminimal miteinander zu verbinden ist. Wichtige Anwendungsfelder finden sich demnach vor allem im Bereich des Netzwerkdesigns. Von der Gestaltung von Rohrleitungssystemen, über die Planung von Elektrizitätsnetzwerken, bis hin zur Strukturierung von Telekommunikationsnetzen erstrecken sich breite Anwendungsgebiete. Das folgende Beispiel soll die Praxisrelevanz verdeutlichen.

Beispiel 1.1

Die Bundesregierung forciert den Ausbau des Breitband-Internets in den Provinzen. Man stelle sich vor, neun Ortschaften auf dem Land sollten an das Breitband-Internet ange- schlossen werden. Im linken Schaubild der Abbildung 1.1 wird die Lage eines jeden Ortes durch einen schwarzen Punkt repräsentiert. Die Verlegung der Glasfaserkabel hin zum Anbindungspunkt in der nächsten großen Stadt ( = eingekreister Punkt) bringt enor- me Kosten mit sich, sodass die ausführende Telekommunikationsgesellschaft an einem möglichst kurzen Netzwerk zwischen den ländlichen Ortschaften interessiert ist.

Abbildung in dieser eseprobe nicht enthalten

Abb. 1.1: Die Situation im Beispiel

Es sei angenommen, dass keinerlei Hindernisse zwischen den jeweiligen Ortschaften vorhanden sind, sodass in jede Richtung unterirdisch Kabel verlegt werden können. Die optimale Lösung dieses einführenden Beispiels ist im rechten Teil von Abbildung 1.1 veranschaulicht (angelehnt an Punktemenge „estein10.txt“ von[31] ). Man sieht dort, dass zur kürzesten und damit kostenminimalen Verbindung dieser neun Orte vier zusätzliche Punkte eingefügt werden, welche rot eingezeichnet sind.

Zu Beginn dieser Arbeit werden wichtige Definitionen und Resultate aufgeführt, die für das Verständnis der Ausarbeitung im weiteren Verlauf unerlässlich sind. Anschlie- ßend wird in Kapitel 3 die geometrische Lösung eines ESTP für eine Menge von drei und von vier Ausgangspunkten erläutert. Kapitel 4 thematisiert Bedingungen, welche an eine Lösung des ESTP geknüpft sind. Des Weiteren wird dort der zentrale Begriff der „Steinertopologie“ erläutert und auf die Komplexität des Problems eingegangen. Kapitel

5 befasst sich mit exakten Verfahren zur Lösung des ESTP. Unter anderem wird dort der Melzak-Algorithmus, der erste exakte Algorithmus zur Lösung dieses Problems, vorgestellt. In Kapitel 6 wird der minimale Spannbaum und dessen Ermittlung behandelt. Kapitel 7 beschäftigt sich ausführlich mit einer Heuristik zur näherungsweisen Lösung des ESTP. Abschließend wird in Kapitel 8 eine Zusammenfassung gegeben. Dieser Ausarbeitung liegt eine Daten-CD bei, welche für eine Reihe der in dieser Arbeit vorgestellten Algorithmen MATLAB-Programme enthält.

2 Grundlegende Definitionen

Im Folgenden werden grundlegende Definitionen eingeführt, welche eine Basis für die weitere Problembehandlung legen. Zunächst werden allgemeine Definitionen der Graphentheorie ([5] ) gegeben, ehe auf die spezifische Terminologie zum euklidischen Steinerbaumproblem eingegangen wird ([12],[10] ).

2.1 Definitionen aus der Graphentheorie

Ein Graph G = (V, E) besteht aus einer nichtleeren Knotenmenge V = {v1, v2, .., vn} und einer Menge von Kanten E ⊆{{vi,vj} | vi = vj mit vi,vj ∈ V}. Sind zwei Kno- ten vi und vj über eine Kante {vi, vj } verbunden, so sind sie adjazent zueinander und werden als Nachbarn bezeichnet. Die Kostenfunktion c : E → Ê+ legt für jede Kante {vi, vj } des Graphen zugehörige Kosten bzw. Kantengewichte cij fest. Man nennt einen Graphen mit dieser Kostenzuweisung einen gewichteten Graphen und schreibt dann G = (V, E, c). Ist jeder Knoten der Knotenmenge mit jedem anderen Knoten ad- jazent, so wird von einem vollständigen Graphen gesprochen. Eine Kante {vi, vj } ist inzident zu einem Knoten, wenn dieser Knoten ein Knoten der Kante ist. Als Kno- tengrad δ(vi) von vi bezeichnet man die Anzahl aller Kanten, welche zu vi inzident sind. Eine Folge ({vi0 , vi1 }, {vi1 , vi2 }, ..., {vin−1 , vin }) wird Kantenfolge genannt. Falls die Kanten der Kantenfolge paarweise verschieden sind, wird die Kantenfolge als Pfad definiert. Sind die Knoten der Kantenfolge paarweise verschieden, so spricht man von einem Weg zwischen vi0 und vin . Wenn Anfangs- und Endknoten des Weges gleich sind, also vi0 = vin gilt, so bezeichnet man ihn mit Kreis. Zwei Knoten vi und vj des Graphen sind miteinander verbunden, wenn es eine Kantenfolge zwischen vi und vj gibt. Man sagt vj ist von vi aus erreichbar. Ist jeder Knoten des Graphen von jedem anderen Kno- ten aus erreichbar, so heißt der Graph zusammenhängend. Ein zusammenhängender Graph ohne Kreise wird Baum genannt. Beinhaltet ein Baum B die gesamte Knoten- menge eines Graphen G, so wird von einem Spannbaum oder spannenden Baum von G gesprochen. Falls kein anderer Spannbaum über der Knotenmenge von G niedrigere Kosten als ein Baum B aufweist, so bezeichnet man B als minimalen Spannbaum von G. Die Kosten eines Baums ergeben sich als Summe aller seiner Kantengewichte.

Man nennt einen Graphen G′ = (V′, E′) für V′ ⊆ V und E′ ⊆ E einen Teilgraph von G. Der Teilgraph G′ heißt induziert von V′ in G, wenn er alle Kanten {vi, vj } ∈ E mit vi,vj ∈ V′ enthält. Ein solcher induzierter Teilgraph wird Untergraph genannt.

2.2 Spezifische Terminologie zum ESTP

Das ESTP hat zum Ziel eine Punktemenge V = {v1, v2, .., vn}, die sogenannten Termi- nalpunkte, oder auch Terminale genannt, distanzminimal zu verbinden. Jedes Ter- minal liegt hierbei in der euklidischen Ebene. Die Distanz zwischen zwei Terminalen vi,vj ∈ Ê[2] mit vi = (v[1] i ,vi)T und vj = (vj,vj)T ist gegeben durch die euklidische

Abbildung in dieser eseprobe nicht enthalten

Ein minimaler Spannbaum, welcher die Terminale V als Knoten besitzt und dessen Kan- tengewichtung der euklidischen Norm entspricht, ist nicht immer die kürzeste Verbin- dung über diese Terminale. Es ist möglich, dass distanzminimalere Spannbäume entste- hen, wenn den Ausgangsknoten zusätzliche Knoten hinzugefügt werden. Knoten, deren Hinzufügen die Länge des Baums reduziert, werden Steinerpunkte genannt und mit S bezeichnet. Jeder Steinerpunkt wird durch einen Punkt im Ê[2] repräsentiert. Ist im Folgenden von Terminalen im Zusammenhang mit einem Baum die Rede, so impliziert dies stets, dass der Baum diese Terminale als Knoten besitzt. Die Anzahl der Terminale V sei durch n und die Kardinalität der Menge der Steinerpunkte S sei durch k gege- ben. In allen Abbildungen dieser Ausarbeitung werden die Terminale immer mit einem schwarzen Punkt und die Steinerpunkte mit einem roten Punkt dargestellt.

Die konvexe Hülle der Terminalpunkte ist das kleinste konvexe Polygon, welches alle Terminalpunkte enthält. Konvex bedeutet anschaulich, dass jede Verbindung zwischen zwei beliebigen Terminalpunkten im Polygon der Terminalpunkte verläuft.

Die Topologie eines Baums entspricht dessen Kantenmenge. Sie beschreibt also welche Knoten miteinander über eine Kante verbunden sind. Eine Topologie liefert aber keine Aussagen über die explizite Lage der Knoten. In einem euklidischen Steinerbaumpro- blem ist die Lage der Terminalpunkte vorgegeben, die Lage der optional hinzufügbaren Steinerpunkte jedoch nicht. Wird also eine Topologie mit Steinerpunkten betrachtet, so lassen sich keine Aussagen über die genaue Lage dieser Steinerpunkte treffen und somit auch keine Rückschlüsse auf die Länge der zu ihnen inzidenten Kanten ziehen. Die Abbil- dung 2.1 zeigt zwei verschiedene Bäume mit identischer Topologie. Beide Bäume besitzen die Kantenmenge E ={{v1, s1}, {v2, s1}, {s1, s2}, {v3, s2}, {v4, s2}} und unterscheiden sich nur durch die Lage der Steinerpunkte. Die Platzierung der beiden Steinerpunkte s1 und s2 bestimmt unmittelbar die Länge dieser Spannbäume.

Abbildung in dieser eseprobe nicht enthalten

Abb. 2.1: Zwei Bäume mit identischer Topologie

Man muss somit zwischen der Topologie eines Baums, also der reinen Beschreibung der Struktur, und dem konkreten Objekt des Baums selbst differenzieren. In den nachfolgenden Abbildungen dieser Ausarbeitung ist die Topologie nicht immer explizit aufgeführt, sondern aus den gezeichneten Bäumen ersichtlich.

Offensichtlich ist eine kürzeste Verbindung von Punkten in der euklidischen Ebene im- mer ein spannender Baum für die korrespondierende Knotenmenge, also insbesondere kreisfrei. Ein Spannbaum, welcher kürzer ist als jeder andere Baum zu einer gegebenen Topologie, wird relativer minimaler Spannbaum (RMT) genannt. Relative minimale Spannbäume dürfen keine Kanten der Länge null enthalten. Daher gibt es Topologien, welche keinen RMT besitzen. Diese Topologien werden degeneriert genannt. Die Ab- bildung 2.2 zeigt einen Baum. Die Länge dieses Baums kann durch Schrumpfen der Kante {s1, s2} minimiert werden, sodass man im Grenzprozess ||s1 − s2|| −→ 0 erhält.

Abbildung in dieser eseprobe nicht enthalten

Abb. 2.2: Nichtexistenz eines RMT

Dies ist im rechten Teil der Abbildung 2.2 ersichtlich. Schrumpfen bedeutet also das Lö- schen der Kante aus der Topologie und die Vereinigung der zu dieser Kante gehörenden Endpunkte. Der so entstandene neue Baum enthält nur noch einen Steinerpunkt. Die Topologie des neuen Baums wird als Degeneriertheit der Ausgangstopologie bezeich- net. Die Ausgangstopologie in Abbildung 2.2 stimmt mit der Topologie in Abbildung 2.1 überein. Im Gegensatz zur Abbildung 2.2 ist die identische Topologie in Abbildung 2.1 mit den zugehörigen Terminalpunkten jedoch nicht degeneriert. Der Grund hierfür ist, dass die Terminale in Abbildung 2.1 quadratisch angeordnet sind, in Abbildung 2.2 jedoch nicht. Ob eine Topologie zu einer Terminalmenge degeneriert ist oder nicht, ist somit abhängig von der Lage der Terminalpunkte. Neben dem Schrumpfen einer Kante gibt es eine weitere Operation, welche auf einem Baum durchgeführt werden kann, das Aufspalten von Kanten. Diese beiden Operationen sind invers zueinander. Die nachstehende Abbildung 2.3 veranschaulicht den Zusammenhang.

Abbildung in dieser eseprobe nicht enthalten

Abb. 2.3: Schrumpfen und Aufspalten

Beim Aufspalten werden zwei zu demselben Knoten inzidente Kanten des Baums über die Terminalpunkte gelöscht und alle Knoten, zu denen diese zwei Kanten inzident waren, mit einem neuen Steinerpunkt, hier s1, verbunden. Insgesamt wird die Anzahl der Knoten dadurch also um eins erhöht. Durch Schrumpfen der Kante {s1,v2} und letztendlicher Fusion der Knoten im Terminal v2 wird die Ausgangssituation wieder hergestellt. Kann ein Baum weder durch Verschiebung von Steinerpunkten in der Ebene, noch durch Aufspaltung von Kanten, d.h. durch Hinzufügen von Steinerpunkten, in seiner Länge verkürzt werden, so wird dieser Baum Steinerbaum genannt. Daraus folgt mit der Definition des relativen minimalen Spannbaums, dass ein Steinerbaum immer auch ein relativer minimaler Spannbaum auf seiner Topologie ist.

Abbildung in dieser eseprobe nicht enthalten

Abb. 2.4: Relativer minimaler Spannbaum und Steinerbaum

In der Abbildung 2.4 a) und c) ist jeweils ein relativer minimaler Spannbaum zu der dort gegebenen Topologie zu sehen. Die Bäume aus a) und c) lassen sich durch Auf- spalten und anschließendes Verschieben der Steinerpunkte jeweils zu einem kürzeren Baum formen, dem Steinerbaum. Der Steinerbaum zu a) ist in b) gegeben und entsteht aus dem Aufspalten der Kanten {s1, v1} und {v1, v2} sowie anschließendem Verschieben der zwei Steinerpunkte zur optimalen Position. Der Steinerbaum zu c) ist in d) darge- stellt. Einen Steinerbaum kann man sich also als relativen minimalen Spannbaum mit gegebener Ausgangstopologie vorstellen, welcher, sofern möglich, durch Anwendung der Operation Aufspalten und anschließendem Verschieben der Steinerpunkte gekürzt wird. Ein minimaler Steinerbaum (SMT) ist definiert als der kürzeste Baum aus der Menge aller Steinerbäume zu einer bestimmten Terminalmenge. Dieser SMT ist die Optimallö- sung des ESTP. Als Steinerhülle der n Terminalpunkte wird eine Region in der Ebene charakterisiert, in welcher sich der SMT befindet.

Ein Steinerbaum heißt voller Steinerbaum, wenn er genau k = n − 2 Steinerpunkte enthält. Eine volle Steinertopologie ist entsprechend eine Topologie, welche n Termi- nalpunkte und genau k = n − 2 Steinerpunkte aufweist. In Abb. 2.5 sind drei Bäume mit allen drei möglichen vollen Steinertopologien zu vier Terminalpunkten aufgezeigt.

Abbildung in dieser eseprobe nicht enthalten

Abb. 2.5: Volle Steinertopologien für vier Terminalpunkte

Bei Betrachtung der Anzahl möglicher verschiedener Topologien werden die Steinerpunk- te nicht einzeln nummeriert, sondern als Gesamtheit erachtet. Es gibt hier die Möglich- keit die Terminale v1 und v2 (a) mit einem Steinerpunkt zu verbinden. Ebenso können die Terminalpaare v1 und v4 (b) sowie v1 und v3 (c) jeweils mit einem Steinerpunkt verbunden werden, sodass man insgesamt die obigen drei vollen Steinertopologien er- hält. Es wird deutlich, dass die volle Steinertopologie in c) zu dieser Lage der Terminale degeneriert ist, da die Länge des Baums durch Schrumpfen der Kante zwischen den bei- den Steinerpunkten reduziert werden könnte. Das Schrumpfen unterbindet eine unnötige Überkreuzung der Kanten. Zu dieser Topologie existiert also kein RMT und folglich auch kein Steinerbaum. Für die vier Terminale aus der Abbildung 2.5 stellt der Baum aus a) den SMT dar und ist somit die Lösung des ESTP zu dieser Lage der vier Terminale.

Zusammenfassend kann man konstatieren, dass ein minimaler Steinerbaum immer auch ein Steinerbaum ist. Ebenso ist ein Steinerbaum immer ein RMT auf seiner Topologie.

3 Geometrische Lösungen zum ESTP

Die Ursprünge des euklidischen Steinerbaumproblems reichen weit bis in das 17. Jahrhundert zurück. Schon Fermat (1607-1665) formulierte die Frage, wo man einen Punkt positionieren muss, damit die Summe der Abstände zu drei vorgegebenen Punkten in der Ebene minimal wird. Dies entspricht in heutiger Terminologie einem ESTP mit n = 3 und k = 1. Toricelli (1608-1647) löste dieses Problem und Simpson (1710-1761) bewies eine alternative Lösungskonstruktion für diese Aufgabe[4].

Für die Terminalanzahl n = 1 und n = 2 ist das ESTP trivial. Das Verbinden eines Punkts mit sich selbst bedarf der Länge Null. Die kürzeste Verbindung zweier Punkte in der euklidischen Ebene ist die direkte Verbindung durch eine Gerade. Im Folgenden wird die Konstruktion eines SMT für drei bzw. vier Terminalpunkte vorgestellt.

3.1 Lösung des ESTP für n=3

Betrachtet man drei Terminalpunkte, so ist es möglich einen SMT geometrisch zu konstruieren. Für die Punkte v1, v2 und v3 sind zunächst die Innenwinkel des sich daraus ergebenden Dreiecks △v1v2v3 zu prüfen und zwei Fälle zu beachten[15].

Ein Innenwinkel ≥ 120◦: Der SMT ergibt sich aus den beiden Kanten, welche inzident zu dem Knoten sind, an dem der stumpfe Winkel angenommen wird. In Abbildung 3.1 besteht der SMT folglich aus den Kanten {v1, v3} und {v3, v2}.

Abbildung in dieser eseprobe nicht enthalten

Abb. 3.1: Ein Innenwinkel ist größer gleich 120◦

Alle Innenwinkel < 120◦: Sofern alle Winkel des Dreiecks kleiner als 120◦ sind, wird der von Toricelli und Simpson lokalisierte Punkt ermittelt. Zur Konstruktion die- ses Punkts ist in beiden Vorgehensweisen zunächst über jeder Kante des von den vorgegebenen Terminalpunkten v1, v2 und v3 aufgespannten Dreiecks ein gleichschenkliges Dreieck zu konstruieren. Anschließend verbindet man nach Simpson jeweils die Spitzen der gleichschenkligen Dreiecke, in der Abbildung 3.2 die Punkte v12,v23 und v13, mit dem jeweiligen gegenüberliegenden Terminalpunkt des Ausgangsdreiecks. Diese drei Verbindungsgeraden, die sogenannten Simpson-Linien, schneiden sich alle in dem optimalen Punkt s1.

Abbildung in dieser eseprobe nicht enthalten

Abb. 3.2: Die Simpson-Konstruktion Abb. 3.3: Die Toricelli-Konstruktion

Bei der Vorgehensweise von Toricelli, zu sehen in der Abbildung 3.3, werden jeweils Kreise durch die Kanteneckpunkte und die Spitze des zugehörigen gleichgeschenkli- gen Dreiecks gezeichnet. Der Schnittpunkt dieser Kreise ist der nach ihm benannte Toricelli-Punkt. Der SMT zu den Terminalen v1, v2 und v3 besteht aus den dick gezeichneten schwarzen Kanten in den obigen Abbildungen 3.2 bzw. 3.3. 3.2 Lösung des ESTP für n=4

Der Fall für vier Terminale birgt erheblich mehr Komplexität in sich und lässt keine Einordnung in nur zwei Fälle zu. Anders als für n = 3 sind hierbei, abhängig von der Lage der Terminale, diverse Unterscheidungen zu treffen. Diese würden den Rahmen der Ausarbeitung sprengen. Daher wird für eine Detailbetrachtung auf[8] verwiesen. Im Endeffekt beschränken sich die dort gezeigten Resultate darauf, den SMT für vier Terminale dezidiert in einen der nachfolgend vorgestellten drei Fälle einzuordnen und dann zielgerichtet die dafür notwendige Konstruktion durchzuführen. Durch Behandlung aller drei Optionen und Wahl derer, welche den kürzesten Spannbaum über die Terminale und die ggfs. ermittelten Steinerpunkte liefert, erhält man auf unstringentere Art und Weise den SMT[18].

Kein Steinerpunkt: Zum einen kann der Fall auftreten, dass den Terminalen kein Stei- nerpunkt hinzugefügt wird. Analog zum entsprechenden Fall bei n = 3 besteht der SMT dann aus den drei kürzesten zusammenhängenden Kanten zwischen den Terminalpunkten, welche keinen Kreis bilden. Eine derartige Anordnung der Terminale v1, v2, v3 und v4 ist in der Abbildung 3.4 veranschaulicht.

Abbildung in dieser eseprobe nicht enthalten

Abb. 3.4: Kein Steinerpunkt wird hinzugefügt

Ein Steinerpunkt: Zum anderen muss geprüft werden, ob sich der minimale Steiner- baum als SMT von drei der vier Terminalpunkte, verbunden mit dem noch nicht angebundenen Terminalpunkt, ergibt. Genauer gesagt betrachtet man alle Teil- mengen der Größe drei von den Terminalpunkten v1, v2, v3 und v4 und ermittelt zum jeweiligen Punktetripel den SMT, wie in Abschnitt 3.1 gezeigt. Anschließend werden die euklidischen Abstände des Terminals, welches nicht in dem Punkte- tripel enthalten ist, zu den anderen drei Terminalen geprüft. Schließlich wird der fehlende Terminalpunkt mit jenem Terminalpunkt aus dem Punktetriple verbun- den, zu dem er die kürzeste Entfernung aufweist. In Abbildung 3.5 wird der noch nicht angebundene Terminalpunkt v4 folglich mit dem Terminal v2 verbunden.

Abbildung in dieser eseprobe nicht enthalten

Abb. 3.5: Hinzufügen eines Steinerpunkts

Zwei Steinerpunkte: Nun wird der dritte Fall behandelt, bei dem zwei Steinerpunkte ermittelt werden. Bilden die vier Terminalpunkte v1, v2, v3 und v4 ein konvexes Viereck, so sind durch eine Konstruktion zwei Punkte zu bestimmen. Diese zwei konstruierten Punkte kommen nur als Steinerpunkte in Betracht, sofern sie in der konvexen Hülle der Terminalpunkte liegen. Ausgangspunkt der Konstruktion sind wiederum gleichseitige Dreiecke auf den gegenüberliegenden Kanten des durch die Terminalpunkte gebildeten konvexen Vierecks. Da es zwei Möglichkeiten gibt, zwei knotendisjunkte Kanten des konvexen Vierecks zu wählen, müssen auch beide Optionen auf Optimalität geprüft werden.

Abbildung in dieser eseprobe nicht enthalten

Abb. 3.6: Hinzufügen zweier Steinerpunkte

Bei der Anordnung der Terminalpunkte gemäß der Abbildung 3.6 ergeben sich die beiden Kantenpaarungen {v1, v2} und {v3, v4} sowie {v1, v4} und {v2, v3}. Das Vorgehen für die Kantenpaarung {v1, v4} und {v2, v3} wird in der Abbildung 3.6 ex- emplarisch dargestellt. Durch die Eckpunkte der jeweiligen gleichseitigen Dreiecke über den Kanten {v1,v4} und {v2,v3} wird ein Kreis konstruiert. Der Schnittpunkt dieses Kreises mit der Verbindungsgeraden zwischen den beiden außen liegenden Dreieckspunkten v14 und v23 stellt jeweils einen Steinerpunkt dar, da diese Schnitt- punkte in dem blau eingezeichneten konvexen Viereck liegen. Die Konstruktion war erfolgreich und das Verbinden der Terminal- und Steinerpunkte, wie in Abbildung 3.6 gezeigt, bildet eine zu prüfende Option für den SMT. Existiert der sogenannte spitze Steinerbaum, d.h. zwei Terminale einer Kante aus einer Kantenpaarung einer erfolgreichen obigen Konstruktion spannen mit dem Diagonalenschnittpunkt O einen Winkel kleiner als 90◦ auf, dann ist dieser der SMT. Im Spezialfall, dem Quadrat, sind die Konstruktionen von beiden Kantenpaarungen optimal[8].

Die Konstruktion eines SMT für die Terminalanzahl n = 3 bzw. n = 4 spielt in vie- len Heuristiken zum ESTP eine wichtige Rolle. Daher wird diese Konstruktion in Ka- pitel 7 nochmals aufgegriffen. Auf dem beigefügten Datenträger sind die Programme „SMT_3.m“ und „SMT_4.m“ enthalten, mit denen nach den hier vorgestellten Kon- struktionsweisen für Terminalmengen der Kardinalität n = 3 bzw. n = 4 der SMT bestimmt und graphisch veranschaulicht werden kann. Algorithmen zur exakten Lösung des ESTP für eine beliebige Anzahl an Terminalen werden in Kapitel 5 vorgestellt.

4 Grundlegende Resultate für das ESTP

Schon im vorherigen Kapitel wurde klar, dass der Winkel zwischen den Kanten eines Baums eine wichtige Rolle spielt, wenn es darum geht den Terminalen Steinerpunkte hinzuzufügen oder nicht. Bei der Konstruktion eines minimalen Steinerbaums für drei bzw. vier Terminalpunkte ist insbesondere der Winkel 120◦ von Bedeutung. Im Folgen- den werden, neben einer allgemeinen Bedingung an die Winkel in einem Steinerbaum, weitere Anforderungen an Steinerbäume und die einzufügenden Steinerpunkte gegeben. Überdies wird in diesem Kapitel der zentrale Begriff der „Steinertopologie“ behandelt, ehe abschließend auf die Komplexität des ESTP eingegangen wird.

4.1 Eigenschaften von euklidischen Steinerbäumen

Ein Steinerbaum wurde als Baum definiert, welcher durch die Operationen Aufspalten und Verschieben von Steinerpunkten nicht mehr in seiner Länge reduziert werden kann. An einen solchen Baum sind gewisse Eigenschaften geknüpft:

Knotengradbedingung: Für alle s ∈ S gilt in einem Steinerbaum δ(s) = 3. Für den Knotengrad der Terminalpunkte gilt 1 ≤ δ(v) ≤ 3, ∀ v ∈ V[12].

Winkelbedingung: Zwei Kanten in einem Steinerbaum schließen mindestens einen Win- kel von 120 Grad ein[12].

Beweis (Knotengradbedingung) : Steinerpunkte werden nur dann hinzugefügt, wenn sie die Länge des Baums verkürzen. Angenommen ein Steinerpunkt würde den Knoten- grad eins haben. Offensichtlich wird dann durch Entfernen dieses optionalen Punkts die Länge des Baums verringert. Besitze ein Steinerpunkt den Grad zwei, so würde durch Entfernen dieses Steinerpunkts und direkter Verbindung der benachbarten Knoten eben- falls die Länge des Baums reduziert. Betrachtet man den Fall δ(s) ≥ 4, so würde die Winkelbedingung verletzt werden, sodass δ(s) = 3, ∀ s ∈ S folgt. Ebenso resultiert daraus δ(v) ≤ 3 und somit 1 ≤ δ(v) ≤ 3, ∀ v ∈ V . □

[...]

Ende der Leseprobe aus 53 Seiten

Details

Titel
Das euklidische Steinerbaumproblem in der Ebene
Hochschule
Technische Universität Dortmund  (Fachgebiet Operations Research und Wirtschaftsinformatik)
Note
1,3
Autor
Jahr
2013
Seiten
53
Katalognummer
V372476
ISBN (eBook)
9783668507425
ISBN (Buch)
9783668507432
Dateigröße
1038 KB
Sprache
Deutsch
Schlagworte
Steinerbaum, Topologie, Steinerbaumproblem, Minimaler Spannbaum, Kombinatorische Optimierung, Euklidischer Steinerbaum, Melzak Algorithmus, Minimum Spanning Tree, Terminalpunkte, Steinertopologie
Arbeit zitieren
Jan Weidner (Autor), 2013, Das euklidische Steinerbaumproblem in der Ebene, München, GRIN Verlag, https://www.grin.com/document/372476

Kommentare

  • Noch keine Kommentare.
Im eBook lesen
Titel: Das euklidische Steinerbaumproblem in der Ebene


Ihre Arbeit hochladen

Ihre Hausarbeit / Abschlussarbeit:

- Publikation als eBook und Buch
- Hohes Honorar auf die Verkäufe
- Für Sie komplett kostenlos – mit ISBN
- Es dauert nur 5 Minuten
- Jede Arbeit findet Leser

Kostenlos Autor werden