Mathematisches Seminar für LAK

Graphentheorie und dasRundreisendenproblem

Michael Hubmann

Oktober 2014

Inhaltsverzeichnis1 Einleitung 3

2 Historisches und Motivation 3

3 Grundlagen 53.1 Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53.2 Wege . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.3 Brückenproblem betrachtet als Graph . . . . . . . . . . . . . . . . . . . . 63.4 Algorithmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.5 O-Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.6 NP-Vollständigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

4 Darstellung eines Graphen durch eine Adjazenzmatrix 9

5 Bäume 105.1 Bestimmung der Anzahl von Bäumen . . . . . . . . . . . . . . . . . . . . 11

6 Planare und nicht planare Graphen 126.1 Der Satz von Kuratowski . . . . . . . . . . . . . . . . . . . . . . . . . . . 136.2 Die Eulersche Polyederformel . . . . . . . . . . . . . . . . . . . . . . . . . 14

7 Traveling Salesman Problem 157.1 Erklärung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157.2 Mathematische Beschreibung . . . . . . . . . . . . . . . . . . . . . . . . . 157.3 Beispiel für das Rundreisendenproblem . . . . . . . . . . . . . . . . . . . . 167.4 Probleme bei großen Zahlen . . . . . . . . . . . . . . . . . . . . . . . . . . 17

7.4.1 Laufzeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177.5 Ziel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2

1 EinleitungDiese Seminararbeit wurde im Rahmen der Lehrveranstaltung „Mathematisches Seminarfür LAK“ verfasst. Sie beschäftigt sich mit der Graphentheorie, sowie dem Rundreisen-denproblem, welches eine Anwendung der Graphentheorie darstellt.

Die Seminararbeit ist so aufgebaut, dass zu Beginn untersucht wird woher die Graphen-theorie stammt und auch wo sie in unserer heutigen Zeit Anwendung findet. Anschließendwerden die grundlegenden Begriffe der Graphentheorie, sowie das nötige Basiswissen zumRundreisendenproblem eingeführt. Das darauffolgende Kapitel behandelt die Möglichkeiteinen Graphen mithilfe einer Adjazenzmatrix darzustellen. Die nächsten beiden Kapitelbeschäftigen sich mit speziellen Graphen: Bäumen und planaren Graphen. Das letzteKapitel beschäftigt sich mit dem Rundreisendenproblem, bzw. den Problemen, welcheim Zusammenhang mit diesem auftreten.

Als inhaltliche Grundlage diente "50 Mathematical Ideas You Really Need to Know"von Tony Crilly.

2 Historisches und MotivationDas Königsberger Brückenproblem [1], [2] (zu damaliger Zeit gehörte Königsberg zuDeutschland; heute heißt es Kaliningrad und liegt in Russland) markiert den Beginn dermodernen Graphentheorie. Es bezieht sich auf die sieben Brücken der Stadt Königsbergüber den Pregel. Dabei ergab sich folgende Fragestellung: „Gibt es einen Weg, bei demalle sieben Brücken genau einmal überquert werden?“ In Abbildung 1 ist dieser Sach-verhalt dargestellt; dabei ist die Insel in der Mitte des Flusses mit I bezeichnet und dieUfer des Flusses mit A,B und C.

Abbildung 1: Königsberger Brückenproblem: Stadtplan

3

Leonhard Euler (1707–1783) beschäftigte sich mit diesem Problem und präsentierte imJahr 1735 seine Lösung der russischen Akademie. Euler erkannte, dass kein Weg dieoben genannte Forderung erfüllen konnte. Außerdem stellte er fest, dass dieses Problemauch dargestellt werden kann indem die Landteile durch Punkte und die Brücken durchVerbindungen zwischen den Punkten dargestellt werden. Was er nun erhielt, war einGraph, wie er in Abbildung 2 dargestellt ist:

Abbildung 2: Königsberger Brückenproblem als Graph

Aber warum ist solch eine Reise nicht möglich? Wir betrachten hierzu den Speziallfallder Rundreise, dass unser Ausgangspunkt auch unser Endpunkt ist. Starten wir hierzuunsere Tour beim Punkt C, ganz im Osten der Stadt Königsberg. Wir verlassen nun Cüber eine der drei zu C führenden Brücken. Wenn wir nun das erste Mal wieder zu Czurückkehren (was notwendig ist, da alle Brücken überquert werden sollen), verlassenwir C über die letzte noch nicht überquerte Brücke. Allerdings können wir jetzt nicht-mehr zu C zurückkehren ohne, dass wir eine der schon überquerten Brücken nochmalsüberqueren müssten. Den allgemeinen Fall werden wir später betrachten.Euler zeigte, dass eine wie oben geforderte Rundreise genau dann möglich ist, wenn sichan keinem der Ufer (Knoten) eine ungerade Zahl von Brücken (Kanten) befindet. Für dieErfüllbarkeit des allgemeinen Königsberger Brückenproblems dürfen maximal zwei Ufer(Knoten) mit einer ungeraden Anzahl an angeschlossenen Brücken (Kanten) existieren.Diese zwei Ufer könnten Ausgangs- bzw. Endpunkt sein. Die restlichen Ufer müssteneine gerade Anzahl von Brücken haben, um sie auch wieder verlassen zu können. Wirwerden dieses Problem später nochmals aufgreifen und es etwas abstrakter betrachten.

Die Graphentheorie findet in vielen Gebieten Anwendung. Allerdings wurde sie lan-ge Zeit nicht als mathematische Disziplin anerkannt [3]. Dies lag daran, dass sich dieGraphentheorie ’ja nur mit endlichen Objekten’ auseinandersetzt. Aber im vorigen Jahr-hundert wurde die Komplexität dieses Gebietes, etwa am Vierfarbensatz, welcher erstdurch den Einsatz von Computern bewiesen werden konnte, erkannt.Als eine der ersten Anwendungen der Graphentheorie gelten chemische Konstitutionsfor-

4

meln. Heute werden viele Alltagsprobleme durch die Graphentheorie modelliert. Zahlrei-che algorithmische Probleme (z.B. das Rundreisendenproblem) können auf die Graphen-theorie zurückgeführt werden. Darüberhinaus basiert die Lösung graphentheoretischerProbleme häufig auf Algorithmen. Dadurch hat die Graphentheorie vor allem in derInformatik eine große Bedeutung.

3 Grundlagen3.1 Graphen

Definition 1 (Graph[4]). Ein Graph G ist ein geordnetes Paar (V, E), wobei V eineMenge von Knoten (auch Ecken) und E eine Menge von Kanten (auch Bögen) bezeichnet.

Als Graph bezeichnen wir also eine endliche Menge von Punkten (Knoten) und Verbin-dungen zwischen diesen Knoten als Kanten. Des Weiteren wird bei Graphen zwischengerichteten (auch Digraph) und ungerichteten Graphen unterschieden. Bei einem gerich-teten Graphen (siehe Abbildung 3) sind alle Kanten gerichtet, d.h. sie sind nur in einerRichtung befahrbar. Bei einem ungerichteten Graphen (siehe Abbildung 2) spielt dieRichtung in welcher der Graph durchfahren wird keine Rolle.

Abbildung 3: gerichteter Graph

So ergeben sich auch unterschiedliche Schreibweisen.

1. Bei einem ungerichteten Graphen werden Kanten als Mengen geschrieben; zumBeispiel für Abbildung 2: {C, I}, {I, A}, ...

2. Bei einem gerichteten Graphen werden Kanten als geordnete Paare geschrieben;zum Beispiel für Abbildung 3: (A, B), (B, C), ...

5

Darüber hinaus gibt es sogenannte gewichtete Graphen; bei diesen wird jeder Kante einereelle Zahl als Kantengewicht zugeordnet. Diese Werte können beispielsweise für Kosten,eine Entfernung oder eine Zeitdauer stehen.Ein Beispiel für einen gewichteten Graphen ist eine Straßenkarte, hier würden die KnotenOrte repräsentieren, die Kanten Straßen und die Gewichte an den Kanten die Entfer-nungen zwischen den Orten.

3.2 Wege

Definition 2 (Weg[5]). Ein Weg im Graphen G=(V, E) ist eine Folge von KnotenW=[v1, ..., vn], mit v1, ..., vn ∈ V , wobei die Kante e = [vi, vi+1], i = 1, ..., n − 1, in derMenge E enthalten ist.

Ein Weg ist also eine Abfolge von Knoten welche nacheinander jeweils durch Kanten ver-bunden sind. Ferner beschreibt ein Weg W einen geschlossenen Weg, wenn gilt vn = v1.Ein Kreis in G ist ein geschlossener Weg der Länge > 2, der außer vn = v1 keine Wieder-holungen hat. Ein ungerichteter Graph heißt zusammenhängend, wenn je zwei Knotenx,y durch mindestens einen Weg verbunden sind. Als Pfad bezeichnen wir einen Weg beiwelchem alle Knoten voneinader verschieden sind d.h., dass für alle i, j ∈ {1, .., n} gilt,dass vi 6= vj , wenn i 6= j.

3.3 Brückenproblem betrachtet als Graph

Betrachten wir nun das Brückenproblem in der neu eingeführten Sprechweise, so lautetes: ’Finde einen Weg, der jede Kante genau einmal enthält’. Ein solcher Weg wird ineinem (ungerichteten) Graphen Eulerscher Weg genannt.

Bemerkung 1. Der Eulersche Kreis in einem (ungerichteten) Graphen ist ein geschlos-sener Eulerscher Weg.

Um das Problem nun zu lösen, definierte Euler noch den Begriff des Grades. Dieserbeschreibt die Anzahl der von einem Knoten ausgehenden Kanten. Nun können wirfolgenden Satz formulieren:

Satz 1 (Satz von Euler). Sei G=(V, E) ein zusammenhängender Graph.

a) In G existiert ein Eulerscher Weg von x nach y genau dann, wenn alle Knoten außerx und y einen geraden Grad haben.

b) In G existiert ein Eulerscher Kreis von x nach y genau dann, wenn alle Knoten einengeraden Grad haben.

6

Betrachten wir mit diesem Wissen nun den Graph in Abbildung 2, so wird wiederumklar, wieso die gewünschte Tour, also jede Brücke einmal zu überqueren, nicht möglichist. Jeder Knoten besitzt nämlich eine ungerade Anzahl an Kanten und dies widersprichtdem von Euler formulierten Satz. Um eine solche Tour möglich zu machen, müsste einezusätzliche Brücke zwischen I und C gebaut werden; damit hätten die beiden Punkteeine gerade Anzahl an Kanten und der Satz von Euler wäre erfüllt. Allerdings müsstenwir unsere Wanderung beim Punkt A starten und beim Punkt B beenden, denn nur derKnoten bei welchem wir starten bzw. unsere Tour beenden darf eine ungerade Anzahl anKanten haben. Möchten wir unsere Wanderung an einem beliebigen Punkt starten undsie auch an diesem beenden, so muss auch noch eine Brücke zwischen A und B gebautwerden. Dann hätte jeder Punkt einen geraden Grad.

3.4 Algorithmus

Ein Algorithmus (Methode, Verfahren, Rezept) nimmt gewisse Daten als Input undtransformiert diese nach festen Regeln in einen Output. Im Allgemeinen kann eine Trans-formation von mehreren verschiedenen Algorithmen geleistet werden.

Eigenschaften eines Algorithmus [9]:

• Ein Algorithmus muss eine allgemeine Gültigkeit besitzen d.h., er löst eine Mengegleicher Probleme einer ganzen Problemklasse.• Ein Algorithmus muss stets eindeutig sein; d.h., der nächste durchzuführendeSchritt muss eindeutig festgelegt sein. Eng damit verbunden ist der Begriff desDeterminismus. Hier ist festgelegt, dass ein Algorithmus für das gleiche Problemstets das gleiche Resultat liefern muss.• Ein Algorithmus muss endlich sein; d.h. er besteht nur aus einer begrenzten Anzahlan Anweisungen welche eine endliche Länge haben. Ferner darf er für seine Datennur endlich viel Speicherplatz benötigen.• Ein Algorithmus muss nach endlicher Zeit terminieren; d.h., dass er nach endlicherZeit ein Ergebnis liefern oder anhalten muss.

Beispiele für Algorithmen:

• Sortierungsverfahren (Informatik)• Euklidischer Algorithmus zur Bestimmung des ggT (Mathematik)

3.5 O-Notation

Laufzeit und Speicherbedarf von Algorithmen werden oft durch asymptotische obereSchranken angegeben; d.h. es wird das Verhalten für „größerwerdenden“ Input beschrie-ben. Eine solche asymptotische obere Schranke ist die O-Notation, welche wie folgtdefiniert wird:

7

Definition 3 (O-Notation). Seien f,g Funktionen von N → R+. Wir schreiben f(n) =O(g(n)), wenn es eine Konstante c > 0 und ein n0 ∈ N gibt sodass f(n) 6 c ∗ g(n)∀n > n0.

Die O-Notation gibt also nichts anderes als eine obere Schranke zur Laufzeit des Algo-rithmus an, welche auch im ungünstigen Fall nicht überschritten wird oder anders gesagt„f(n) wächst höchstens so schnell wie g(n)“.

Konstante Faktoren werden hier vernachlässigt, da diese nicht nur von Algorithmensondern von anderen Komponenten wie der Hardware oder der Programmiersprache ab-hängen. Für wachsende Inputgrößen spielen diese Faktoren jedoch eine immer geringereRolle.

Beispiel 1. 5n + 3 = O(n); zu zeigen: ∃c ∈ R, c > 0, ∃n0 ∈ N : 5n + 3 6 c ∗ nBeweis: c=6, n0 = 35n + 3 6 6n für n > 33 6 n für n > 3

3.6 NP-Vollständigkeit

Wir bezeichnen ein Problem als NP-vollständig, wenn wir es in polynomieller Zeit nicht-deterministisch lösen können; daher auch NP (Nonderterministic Polynomial). Bei NP-vollständigen Problemen handelt es sich um eine Klasse von Problemen bei denen derStatus ob sie lösbar sind oder nicht ungeklärt ist. Lösbarkeit in polynomieller Zeit mar-kiert die Trennlinie zwischen „behandelbaren“ und „unbehandelbaren“ Problemen, auspraktischer Sicht.

Wir unterscheiden zwischen zwei Klassen von Problemen: P und NP. Dabei ist die KlasseP jene Klasse von Problemen, welche von einem Computer in polynomieller Zeit deter-ministisch gelöst werden kann.Bei der Klasse der NP-Probleme gibt es eine alternative Definition zu oben: Gegeben seieine Lösung für ein Problem. Die Klasse NP umfasst nun all jene Probleme für die eineLösung in polynomieller Zeit überprüft werden kann.

Eine der im Moment wohl wichtigsten offen Frage in der theoretischen in Informatik,ist die, ob P=NP gilt. Also die Frage, ob ein Problem welches in polynomieller Zeitnachprüfbar ist auch in polynomieller Zeit gelöst werden kann. Mehr als die Hälfte derWissenschaftler sind der Meinung dass P=NP nicht gilt, also, dass es Probleme gibt,welche zwar in polynomieller Zeit überprüft aber nicht gelöst werden können. Für denNachweis dieser Frage, also ob P=NP gilt oder nicht, sind aktuell 1.000.000 $ ausge-schrieben.

Ein Beispiel für ein NP-Problem ist das Rundreisendenproblem, welches wir später nochgenauer behandeln werden. Es gibt 21 NP-Probleme. Wenn auch nur eines dieser gelöstwerden könnte, wären auch alle anderen Probleme gelöst, da die Probleme aufeinanderreduzierbar sind.

8

4 Darstellung eines Graphen durch eineAdjazenzmatrix

Soll ein Graph mit einem Programm eingelesen bzw. dargestellt werden, so gibt es hierfürverschiedene Möglichkeiten; eine davon ist die Adjazenzmatrix.

Definition 4 (Adjazenzmatrix). Sei G=(V, E) ein (ungerichteter) Graph mit V =

{v1, ..., vn}. Die Matrix A = (ai,j)16i,j6n mit{

ai,j = 1, falls (vi, vj) ∈ E

ai,j = 0, sonstheißt Adja-

zenzmatrix.

Eine Adjazenzmatrix besitzt für jeden Knoten eine eigene Zeile und Spalte. Dadurchergibt sich eine quadratische n × n Matrix. Ein Eintrag in der i-ten Zeile und j-tenSpalte gibt an, ob es eine Kante vom i-ten Knoten zum j-ten Knoten gibt. Hierbei stehteine 0 dafür, dass es keine Kante gibt und eine 1 steht für eine Kante. Also speicherteine Adjazenzmatrix, welche Knoten durch eine Kante in einem Graphen verbundensind. Es gibt mehrere Definitionen einer Adjazenzmatrix eine weitere wäre, dass in ai,j

festgehalten wird, wieviele Kanten es von einem Knoten i zu einem anderen Knoten jgibt, dies würde Anwendung in einem Graphen mit mehrfachen Kanten finden. Eineandere Definition besagt, dass in ai,j das Gewicht der Kante vom Knoten i zum Knotenj festgehalten wird, dies würde Anwendung bei einem gewichteten Graphen finden. Wirbegnügen uns allerdings mit der obigen Definition.

Beispiel 2. Gegeben ist folgende Adjazenzmatrix:

0 1 0 01 0 1 10 1 0 00 1 0 0

Der aus dieser Matrix resultierende Graph würde so aussehen:

Abbildung 4: Graph: Beispiel 2

Mithilfe einer Adjazenzmatrix lässt sich auch die Anzahl der Wege vom Knoten i zumKnoten j bestimmen, welche genau die Länge k haben. Dies kann durch folgenden Satzformuliert werden:

9

Satz 2. [5] Die Anzahl der Wege der Länge k vom Knoten xi zum Knoten xj ist (ai,j)(k).

Beweis. Durch Induktion nach k.

Die Aussage ist für k=1 richtig.

Angenommen, die Aussage stimmt für k, und zwar für alle Knoten xi, xj . Jeder Wegder Länge k+1 von xi nach xj kann in eine Anfangskante von xi zu einem Knotenx′i und den darauffolgenden Weg der Länge k von x′i nach xj zerlegt werden. Zu jederAnfangskante von xi nach x′i gibt es nach Annahme (ai′,j)(k) Wege der Länge k von x′inach xj . Daher ist die Anzahl der Wege der Länge k+1 von xi über x′i (1.Schritt) nachxj gleich ai,i′(ai′,j)(k). Variieren des Punktes x′i ergibt alle verschiedenen Möglichkeiten,also ist die Anzahl der Wege der Länge k+1 von xi nach xj :

∑ni′=1 ai,i′(ai′,j)(k) . Nach

Definition der Matrixmultiplikation ist das (ai,j)(k+1).

Beispiel 3. Gegeben sei folgende Matrix:

0 1 0 01 0 1 00 0 0 10 0 1 0

Gesucht wird die Anzahl der Wege vom Knoten 2 zum Knoten 3, mit Länge 3.

Hierzu müssen wir die Matrix A3 berechnen: A3 =

0 1 0 11 0 2 00 0 0 10 0 1 0

Es gibt also 2 Wege im Graphen, welche vom Knoten 2 zum Knoten 3 gehen und genau3 Kanten enthalten: der erste ist 2-1-2-3, der zweite 2-3-4-3.

5 BäumeDefinition 5 (Baum). Ein Baum ist ein zusammenhängender Graph ohne Kreise.

Ein Baum unterscheidet sich von den bisher kennengelernten Graphen. Bei den bisherbehandelten Graphen war es unter Umständen möglich, wieder zum Ausgangspunktüber eine andere Route zurückzukehren (Kreis). Dies ist bei einem Baum nicht möglich,da er keine Kreise besitzt. Ein Beispiel für einen Baum ist in Abbildung 5 ersicht-lich:

Ein Beispiel für einen derartigen Aufbau sind Ordnerstrukturen am Computer. Auch hiergibt es immer einen obersten Ordner, in welchem sich sodann mehrere Unterordner be-finden können, in welchen sich wiederum Unterordner befinden können. Darüber hinausgibt es auch in einer Ordnerstruktur keine Kreise, es ist also nicht möglich von einem Ast

10

Abbildung 5: Darstellung eines Graphen als Baum

zu einem anderen zu gelangen, mit Ausnahme über den jeweiligen root-Ordners beiderÄste.

Eigenschaften von Bäumen: Jede der folgenden Bedingungen charakterisiert einen Gra-phen T=(V,E) mit n Knoten als Baum:

• T ist zusammenhängend und hat n-1 Kanten.• T ist zusammenhängend und jede Kante ist eine Brücke1.• Für je zwei Knoten x, y gibt es genau einen Pfad von x nach y.

Definition 6 (Spannbaum [8]). Sei G = (V, E) ein (ungerichteter) Graph. Ein TeilgraphT = (V, E′) heißt Spannbaum von G, wenn er ein Baum ist und aus allen Knoten vonG besteht.

Ein Beispiel für einen Spannbaum eines Graphen ist in Abbildung 6 dargestellt. Linksist der eigentliche Graph abgebildet, rechts sein Spannbaum:

Abbildung 6: Ein Regenschirm als Spannbaum

5.1 Bestimmung der Anzahl von Bäumen

Arthur Cayley griff die Frage auf, wie viele verschiedene Bäume aus einer gegebenenAnzahl von Knoten erstellt werden können. Er formulierte den Satz von Cayley, welcherbesagt, dass ein vollständiger Graph mit n Knoten n(n−2) verschiedene Spannbäumebesitzt.

1Wird eine Kante aus einem Graphen entfernt und ist sodann der Restgraph nicht mehr zusammen-hängend, so war die entfernte Kante eine Brücke.

11

Beispiel 4. Gesucht sind alle Spannbäume eines vollständigen Graphens mit 4 Knoten.Wie viele gibt es?Laut Formel von Cayley müsste es 42 = 16 Bäume geben. Mittels Zeichnung kann diesnachgewiesen werden:

Abbildung 7: zeichnerische Lösung

Die Zeichnung zeigt, dass es tatsächlich 16 Spannbäume gibt.

Anwendung findet das Abzählen von Bäumen in der Chemie, da die Verbindungen mitderselben Anzahl an Atomen, aber unterschiedlicher Anordnung dieser unterschiedlichechemische Eigenschaften haben.

6 Planare und nicht planare GraphenDefinition 7 (Planar[6]). Ein Graph heißt planar falls er in einer Ebene so gezeichnetwerden kann, dass sich die Verbindungslinien(Kanten) nicht kreuzen.Beispiel 5. Gegeben sei der Graph G = (V,E) mit der Knotenmenge V = {1, 2, 3, 4, 5, 6}und Kanten E = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {3, 4}, {3, 5}, {3, 6}, {4, 5}, {4, 6}}. Ist derGraph planar?

Abbildung 8: Darstellung des Graphen

Der Graph ist ohne Überkreuzungen darstellbar, also ist er planar.

12

6.1 Der Satz von Kuratowski

Wir betrachten nun folgenden Sachverhalt: Es existieren 3 Häuser und alle diese 3 Häusersollen jeweils an die Gasleitung, Wasserleitung und Elektroleitung angeschlossen werden.Allerdings gibt es dazu eine Auflage: die Verbindungen zwischen Leitungen und den Häu-sern dürfen sich nie kreuzen. Kann dieser Sachverhalt bewerkstelligt werden?Die Antwort auf diese Frage ist: nein. Der dabei entstehende Graph wird durch 6 Punktedargestellt, welche die Häuser bzw. Leitungen repräsentieren, und durch 9 Kanten wel-che jeweils Verbindungen zwischen den Häusern und den Leitungen repräsentieren. WieAbbildung 9 nun zeigt, können die jeweiligen Kanten nicht alle in der Ebene gezeichnetwerden ohne, dass sich 2 Kanten schneiden.

Abbildung 9: Darstellung des Sachverhaltes

Solch einen Graphen bezeichnen wir als nicht planar und diesen speziell mit K3,3.

Ein weiteres Beispiel für einen nicht planaren Graphen ist ein Graph welcher aus 5Punkten besteht und bei welchem alle Knoten miteinander verbunden sind (ein solcherGraph wird auch als vollständiger Graph bezeichnet). Wir bezeichnen ihn mit K5. Erwird in Abbildung 10 dargestellt.

Abbildung 10: Nicht planarer aus 5 Knoten bestehender Graph

13

Diese beiden nicht planaren Graphen spielen eine wesentliche Rolle im Satz von Kura-towski welcher wie folgt lautet:

Satz 3 (Satz von Kuratowski[7]). Ein endlicher Graph ist genau dann planar, wenn erkeinen Teilgraphen enthält, der durch Erweiterung von K5 oder K3,3 entstanden ist.

Erweiterung bedeutet hier das beliebig oft wiederholbare (auch null mal) Einfügen vonneuen Knoten auf den Kanten. Mit Teilgraph ist hier ein Graph gemeint, der aus demursprünglichen Graphen durch Entfernen von Knoten bzw. Kanten entsteht, wobei dieEntfernung eines Knotens mitsamt aller induzierten Kanten einen induzierten Teilgraphergibt.

6.2 Die Eulersche Polyederformel

Jeder planare Graph teilt die Ebene in Gebiete. Die Anzahl der Gebiete wird mit gbezeichnet. Mit dem Begriff der Gebiete können wir einen Satz zur eulerschen Polyeder-formel formulieren:

Satz 4. Sei G ein zusammenhängender planarer Graph mit n Ecken, m Kanten und gGebieten. Dann gilt: n−m + g = 2.

Beweis. Induktion nach m.

m = 0: Ein zusammenhängender Graph ohne Kanten hat genau einen Knoten. Die Ebenewird in genau ein Gebiet unterteilt: 1− 0 + 1 = 2

m=1: Folgende Fälle sind möglich:Fall 1:

Abbildung 11: n=1,m=1,g=2

Fall 2:

Abbildung 12: n=2, m=1, g=1

14

In beiden Fällen gilt die Formel.

m− 1→ m :Wenn G ein Baum ist, dann ist g = 1 und nach den Eigenschaften der Bäume ist n =m+1, sodass die Formel stimmt.Wenn G kein Baum ist, dann kann eine Kante entfernt werden welche zu einem Kreisgehört und der übriggebliebene Graph ist immer noch zusammenhängend, mit folgendenParametern:

n Knoten, m− 1 Kanten, g − 1 Gebiete

da durch das Entfernen der Kante zwei Flächen zu einer verschmolzen sind. Nun ist dieInduktionsannahme anwendbar und es muss gelten:

n− (m− 1) + (g − 1) = 2

und die Formel gilt auch für den neuen Graphen.

Also gilt, dass die Anzahl der Ecken minus der Anzahl der Kanten addiert mit derGebiete stets konstant 2 ergibt bei einem zusammenhängenden planaren Graphen.

7 Traveling Salesman Problem7.1 Erklärung

Beim Traveling Salesman Problem, auch unter dem Namen Rundreisendenproblem be-kannt, geht es darum, durch eine Anzahl an vorgegebenen Destinationen einen Weg miteinem möglichst kurzen Zyklus zu bestimmen. Anders gesagt: wir haben einen Liefer-wagenfahrer, der von seinem Firmenlager Pakete zu verschiedenen Orten liefern und amEnde seiner Tour wieder zum Lager zurückkehren muss. Mit welcher Route schafft erdas am schnellsten?

7.2 Mathematische Beschreibung

Das Problem des Handlungsreisenden lässt sich mithilfe eines gewichteten Graphen dar-stellen [10]. Dabei repräsentieren die Knoten die Städte und die Kanten {i, j} die Verbin-dung zwischen den Knoten i und j. Den Kanten wird nun noch ein Gewicht zugeordnet,welches je nach Situation beispielsweise Kosten repräsentieren kann (z.B. Flugkosten)oder auch eine Distanz (z.B. in Kilometern) zwischen den einzelnen Städten angibt. Umdie Untersuchung des Problems zu vereinfachen und um sicherzustellen, dass es eine Tourgibt, wird meist angenommen, dass der Graph vollständig ist, dass also zwischen je zweiKnoten immer eine Kante existiert. Dies lässt sich dadurch erreichen, dass überall dort,

15

wo keine Kante existiert, eine künstliche, sehr lange Kante eingefügt wird. Aufgrundihrer hohen Länge wird eine solche Kante nie in einer kürzesten Tour vorkommen, es seidenn, es gäbe sonst keine Tour.

7.3 Beispiel für das Rundreisendenproblem

Wir betrachten die Rundreise des Verkäufers James Cook [1]:

Abbildung 13: Beispielhaftes Rundreiseproblem

Das Verkaufsgebiet von James Cook umfasst die Städte Albuquerque (A), Bismark (B),Chicago (C), Dallas (D) and El Paso (E). Von jeder Stadt aus kann jede andere Stadterreicht werden. Die jeweiligen Entfernungen sind an den Kanten vermerkt. Beispiels-weise beträgt die Distanz von Bismark nach Chicago 706 Meilen. James plant nun seineRoute; er startet in Bismark. Er fährt zu Beginn nach Chicago, da diese Stadt Bismarkam nächsten ist. Sein nächstes Ziel ist Dallas, das von Chicago die kürzeste Entfernunghat. In Summe ist James bereits 706 + 785 also 1491 Meilen gereist. Sein nächstes Zielist nun Albuquerque, welches Dallas wiederum am nächsten liegt. Von dort aus steuerter sein letztes Ziel El Paso an. Von dort aus fährt er zurück nach Bismark, wo er seineTour beendet. In Summe hat James nun eine Distanz von 3407 Meilen zurückgelegt.Diese Art und Weise eine Route zu planen wird auch als die „gierige“ Methode beschrie-ben, da immer nur eine lokale Entscheidung getroffen wird und keine weiter voraus-schauende. So kommt es auch, dass James sodann von El Paso aus einen langen Wegnach Bismark zurücklegen muss. So stellt sich also die Frage, ob mit der Tour BCDAEBbereits die kürzeste Route gefunden wurde?James betrachtet nun alle möglichen Routen und vergleicht sie miteinander. Bei 5 zubesuchenden Städten ergibt dies 24 mögliche Routen bzw. 12 wenn die Umkehrung einerRoute weggelassen wird. Aus dieser Auflistung von Routen heraus kann James nun diemit der kleinsten Gesamtdistanz auswählen. Es stellt sich heraus, dass dies die RouteBAEDCB (bzw. ihre Umkehrung BCDEAB) mit 3199 Meilen ist.

16

7.4 Probleme bei großen Zahlen

Das Traveling Salesman Problem gehört der Klasse der NP äquivalenten Probleme an.Das heißt: mit zunehmender Anzahl an Destinationen steigt der Aufwand der Berech-nung zumindest exponentiell und somit können keine genauen Lösungen in vernünftigerZeit berechnet werden. Betrachten wir nochmals unsere Rundreise von vorhin. DiesesMal allerdings nicht für 5, sondern für 13 Städte. Da die „greedy method“ keine zu-friedenstellenden Ergebnisse liefert, möchten wir wieder eine komplette Auflistung allermöglichen Routen haben. Die Anzahl der Routen würde 3, 1 ∗ 109 betragen; dies würdebedeuten, dass ein Computer für die Berechnung rund ein Jahrhundert benötigen würde.Um eine effiziente Laufzeit zu erreichen und trotzdem annähernd optimale Ergebnisse zuerhalten, bedienen wir uns intelligenter heuristischer Methoden.

7.4.1 Laufzeit

Zuvor wurde bereits erwähnt, dass James mit einem Computer bei der Berechnung deroptimalen Route für 13 Städte rund ein Jahrhundert benötigen würde. Wenn er jetztauch nur 2 Städte hinzufügen würde, würde er 20.000 Jahre für die Berechnung benö-tigen. Das daraus resultierende Wachstum würde O(n!) bei dieser Methode betragen,was ein exponentielles Wachstum bedeutet. Mit einer anderen Methode ist es möglich,dass das Problem mit O(2n) gelöst wird. Dadurch ergeben sich bei 13 Städten 8192Möglichkeiten. Allerdings ergibt sich auch hier immer noch eine exponentielle Lauf-zeit.

7.5 Ziel

Das Ziel wäre, dass das Rundreisendenproblem in polynomieller Laufzeit eindeutig lös-bar ist. So würde die Berechnung einer Rundreise eine akzeptable Zeitdauer in An-spruch nehmen. Darüber hinaus gehört das Rundreisendenproblem wie bereits erwähntzur Klasse der NP-Probleme. Wenn also nun das Rundreisendenproblem in polynomiel-ler Laufzeit eindeutig lösbar wäre, wären damit auch alle anderen NP-Probleme gelöstund eine der größten Fragen welche Informatiker im Moment beschäftigt wäre beantwor-tet.

17

Abbildungsverzeichnis1 Königsberger Brückenproblem: Stadtplan . . . . . . . . . . . . . . . . . . 32 Königsberger Brückenproblem als Graph . . . . . . . . . . . . . . . . . . . 43 gerichteter Graph . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 Graph: Beispiel 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 Darstellung eines Graphen als Baum . . . . . . . . . . . . . . . . . . . . . 116 Ein Regenschirm als Spannbaum . . . . . . . . . . . . . . . . . . . . . . . 117 zeichnerische Lösung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128 Darstellung des Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 Darstellung des Sachverhaltes . . . . . . . . . . . . . . . . . . . . . . . . . 1310 Nicht planarer aus 5 Knoten bestehender Graph . . . . . . . . . . . . . . 1311 n=1,m=1,g=2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1412 n=2, m=1, g=1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1413 Beispielhaftes Rundreiseproblem . . . . . . . . . . . . . . . . . . . . . . . 16

18

Literaturverzeichnis[1] 50mathematicalideas

[2] Geschichte der Mathematik VO SS2014,Uni Graz, Renate Tobies

[3] http://finanz.math.tugraz.at/ predota/old/history/resultate/bruecken.html

[4] http://wwwmath.uni-muenster.de/u/clara.loeh/discgeosem_ws0809/kampsGraphentheorie.pdf

[5] Diskrete Mathematik(Telematik SS2012) Frisch, Lehner, Wöss

[6] http://www.algebra.uni-linz.ac.at/Students/Win/fg07s/lec/planar.pdf

[7] http://www.mathepedia.de/Satz_von_Kuratowski.aspx

[8] http://www.inf.fh-flensburg.de/lang/algorithmen/graph/minimum-spanning-tree.htm

[9] http://www.info-wsf.de/index.php/Definition_Algorithmus

[10] http://de.wikipedia.org/w/index.php?title=Problem_des_Handlungsreisenden&redirect=no

19