Johannes-Gutenberg-Universität Mainz

Im Rahmen des Hauptseminares

�Eine Einführung in die Mathematik�

im SS 2017

Bei Prof. Dr. Mária Lukácová

Graphentheorie

Sarah Lawall

Inhaltsverzeichnis

1 Einführung 3

1.1 Königsberger Brückenproblem . . . . . . . . . . . . . . . . . . . . . . . . . 31.2 Grundlagen der Graphentheorie . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Geschichte der Graphentheorie . . . . . . . . . . . . . . . . . . . . . . . . 4

2 Diskrete Optimierung 5

2.1 Optimierungsprobleme . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Hypergraphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62.3 Beispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6

3 Informatik 7

4 Die probabilistische Methode 9

4.1 Zufällige Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94.2 Bsp. eines Beweises durch Wahrscheinlichkeitstheorie . . . . . . . . . . . . 9

5 Anwendungen 11

5.1 Anwendungsbeispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 115.2 Sehr groÿe Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11

6 Literatur 13

2

1 Einführung

1.1 Königsberger Brückenproblem

Das wohl bekannteste graphentheoretische Problem ist das Königsberger Brückenpro-blem,bei dem es darum geht, ob es möglich ist bei einem Spaziergang durch Königsbergjede der 7 Brücken genau einmal zu benutzen.Leonhard Euler löste das Problem 1736,was als Beginn der Graphentheorie angesehen wird.Zur Lösung des Problems vereinfachte Euler den Stadtplan (links), indem er für die

Abbildung 1.1: Stadtplan Köbigsberg

Abbildung 1.2: Graph Königsberg

Stadtteile Punkte und für die Brücken Verbindungen zwischen den Punkten zeichnete(rechts). Dabei wurde ihm klar, dass dieser Spaziergang nur möglich ist, wenn alle Stadt-teile eine gerade Anzahl von Brücken haben, da man rein und wieder raus kommen muss(lässt man verschiedene Anfangs- und Endpunkte zu dürfen diese eine ungerade Anzahlan Brücken haben). Da aber alle Stadtteile eine ungerade Anzahl an Brücken haben (3oder 5) ist es nicht möglich durch Königsberg laufen und dabei jede Brücke genau einmalbenutzen.

3

1 Einführung

1.2 Grundlagen der Graphentheorie

Def.: �Ein Graph ist ein Paar G = (V,E) mit einer endlichen Menge V 6= ∅ und einerendlichen Menge E ⊆ {{u, v}|u, v ∈ V, u 6= v}. Die Elemente von V heiÿen Knoten vonG. Die Elemente von E heiÿen Kanten von G. Eine Kante e ∈ E ist also von der Forme = {u, v} mit gewissen u, v ∈ V , welche als Endkoten von e bezeichnet werden.�1 Lässtman u = v zu, so erhält man eine Schleife.

Def.:Sei G = (V,E) ein Graph und v ∈ V ein Knoten. Dann bezeichnet man den Gradg(v) des Knotens v, als die Anzahl der Kanten e ∈ E mit Endknoten v.

Def.: Ein Eulerkreis in einem Graphen G ist ein geschlossener Kantenzug, der jede Kantevon G genau einmal durchläuft.

Das Königsberger Brückenproblem können wir nun also als Suche nach einem Euler Kreisin einem gegebenem Graphen formulieren und sagen, dass dieser nicht existiert weil alleKnoten ungeraden Grad haben.

1.3 Geschichte der Graphentheorie

Wie bereits erwähnt gilt das Jahr 1736 als Beginn der Graphentheorie. Doch auch alsim 19. Jahrhundert bereits viele Resultate im Zusammenhang mit elektrischen Netzwer-ken bewiesen wurden galt die Graphentheorie noch nicht als eigenständiges Gebiet. Diesänderte sich erst 1936 als Dénes König mit �Theorie der endlichen und unendlichen Gra-phen� das erste Buch über die Graphentheorie verö�entlichte.Die Graphentheorie spielt heute eine wichtige Rolle, da Forscher vieler Fachgebiete (Bio-logie, Soziologie, Geschichte...) ho�en mit ihrer Hilfe weitere Erkenntnisse zu erzielen.

4

2 Diskrete Optimierung

Nehmen wir einmal an, dass wir eine Heiratsagentur besitzen und möglichst viele Paa-re verheiraten wollen. Dabei können wir natürlich nicht jeden mit jeden verheiraten, essind nur bestimmte Paarungen möglich. In der Sprache der Graphentheorie bilden dieHeiratskandidaten die Knoten des Graphen und mögliche Knoten werden durch Kantendargestellt. Da wir möglichst viele Menschen verheiraten wollen (wobei wir von Mono-gamie ausgehen) stellt sich die Frage, wie man das Heiratsproblem optimieren kann.

2.1 Optimierungsprobleme

Optimierungsprobleme sind bereits aus der Analysis bekannt, wenn man dort ein Pro-blem optimieren will sucht an die Nullstellen der ersten Ableitung und sucht dann denentsprechend höchsten/niedrigsten Wert (und vergleicht ihn evtl. noch mit den Randwer-ten). Im Bezug auf Graphen betrachtet man aber diskrete Probleme, bei denen es keineAbleitungen gibt. Also müssen andere Methoden gefunden werden, um das Optimumeines Problems zu �nden.Eine dieser Methoden ist die Lineare Programmierung, bei der es im Grunde um dieLösung von linearen Ungleichungen geht. Dies ist schwieriger als das Lösen von linearenGleichungen, zumal man meist nicht irgendeine Lösung �nden will, sondern die optima-le, bei der eine bestimmte Abbildung ihr Maximum bzw. Minimum annimmt. Für diesesProblem gibt es jedoch relativ einfache Algorithmen, die das System auf ein linearesGleichungssystem zurückführen. Dies kann man geometrisch als das Lösen einer linearenFunktion auf einem konvexen Polyeder (einer sehr hohen Dimension) betrachten.Aber wofür genau braucht man dieses Verfahren? Ein verbreitetes Problem ist das Fin-den von Matchings.

Def.: Sei G = (V,E) ein Graph. Eine Menge M ⊆ E heiÿt Matching, wenn für zweiKanten e1, e2 ∈ E, e1 6= e2 kein Knoten v ∈ V existiert, so dass v sowohl Endknoten vone1 als auch von e2 ist.

Es geht also um die Frage, ob man die Knoten eines gegebenen Graphen so aufteilenkann, dass je zwei Knoten durch eine Kante verbunden sind. Wenn dies nicht möglichist stellt man die Frage, was die maximale Anzahl an Knoten ist, für die das möglich istund erhält ein Optimierungsproblem.Bezogen auf das Heiratsproblem suchen wir also ein Matching mit möglichst vielen Kan-ten.

5

2 Diskrete Optimierung

2.2 Hypergraphen

Bisher wurden Graphen betrachtet, bei denen jede Kante genau zwei Enden besitzt.Aber eine Kante kann beliebig viele Enden haben, also analog zu den Graphen einenHypergraphen de�nieren. Viele graphentheoretische Probleme lassen sich auf Hypergra-phenprobleme ausweiten (wenn auch häu�g nicht eindeutig), welche zum Teil immer nochnicht gelöst sind.

Def.: Ein Hypergraph H ist ein Paar (V,E) mit einer endlichen Menge V 6= ∅ und ei-ner endlichen Menge E ⊆ {{u1, ..., un} : ui ∈ V ∀i, ui 6= uj für i 6= j, n ≤ r ∈ N}

r ist die Beschränkung für die Anzahl der Knoten, die eine Kante verbindet, da es möglichist verschiedene Kantengrade in einem Hypergraphen zu haben.

2.3 Beispiel

Ein Beispiel für die Ausweitung von Graphenproblemen auf Hypergraphenprobleme sinddie Sätze von König über bipartite Graphen.

Def.: Ein bipartiter Graph ist ein Graph, bei dem es möglich ist die Knoten so in zweiKlassen einzuteilen, dass die Endknoten einer Kante immer in verschiedenen Klassenliegen.

Sätze von König:�Die Minimalzahl von Farben, die benötigt werden, um die Kanten eines Graphen sozu färben, dass Kanten mit einem gemeinsamen Ende verschieden gefärbt sind, ist dermaximale Grad seiner Knoten.�2

�Die Maximalanzahl paarweise disjunkter Kanten in einem bipartiten Graph ist die Mi-nimalanzahl der Knoten, so dass jede Kante an mindestens einem Knoten endet.�3

Diese beiden Sätze werde ich hier nicht beweisen. Aber diese beiden Sätze sind auchfür Hypergraphen sinnvoll, sofern man sich eine geeignete De�nition von Bipartitheit inHypergraphen überlegt.

Def.: Ein Hypergraph heiÿt 2-färbbar, genau dann wenn man die Knoten so in zweiKlassen aufteilen kann, dass jede Kante mindestens ein Ende pro Klasse hat.

Diese De�nition erscheint sinnvoll, jedoch gelten die beiden Sätze für diese (und an-dere De�nitionen von Bipartitheit) nicht, sie sind jedoch weiterhin äquivalent.

6

3 Informatik

Mathematische Resultate lassen sich auch in die Sprache der Graphentheorie übersetzen.So bilden die Zwischenschritte einer Rechnung die Knoten, und wenn ein Zwischen-schritt für einen anderen benötigt wird, so wird dies als gerichtete Kante interpretiert.Dann kann man aus der Komplexität des Graphen die Komplexität der dazugehörigenRechnung berechnen. Auf diese Weise wurde die lange ungelöste Frage geklärt, warumHamiltonkreisprobleme schwerer zu lösen sind als Matchingprobleme.

Def.:Ein Hamiltonkreis in einem Graphen G ist ein geschlossener Kantenzug, der je-den Knoten von G genau einmal durchläuft.

Um zu unserem Ausgangsbeispiel zurückzukommen geht es also um die Frage, ob esmöglich ist in alle vier Stadtteile zu gelangen ohne eine Brücke mehrfach zu benutzen,was o�ensichtlich möglich ist.Um das zu verstehen, muss man sich zunächst das �P = NP?�-Problem, eines der Mille-

Abbildung 3.1: Stadtplan Königsberg mitmöglichem Spaziergang

Abbildung 3.2: Graph zum Spaziergang

niumprobleme, anschauen, und dafür einen Abstecher in die Informatik machen. FrüheFormulierungen davon tauchten in Briefen bereit 1950 (John Forbes Nash) und 1956(Kurt Gödel).

Def.: Die Klasse P ist die Menge der Probleme, zu denen es einen Algorithmus gibt,

7

3 Informatik

der die Lösung in polynomieller Laufzeit �ndet.

Def.: Die Klasse NP ist die Menge der Probleme, zu denen es einen Algorithmus gibt,der einen Lösungskandidaten in polynomieller Laufzeit veri�zieren kann. (NP steht fürnichtdeterministisch polynomiell.)

Def.: NP-vollständige Probleme sind Probleme aus der Klasse NP, bei denen das Findeneiner Lösung in polynomieller Laufzeit zur Lösung aller NP-Probleme in polynomiellerLaufzeit führen würde, da man se in polynomieller Laufzeit an alle anderen NP-Problemeanpassen könnte.

Die Frage ist also, ob man �schwere� Probleme nicht schneller lösen kann, was geradebei groÿen Datensätzen viel Zeit (und damit auch Geld) sparen würde. Die meisten Wis-senschaftler gehen allerdings davon aus, dass P6=NP ist, es gibt also Probleme, bei denenman einen geratenen Wert in polynomieller Laufzeit veri�zieren kann, bei denen es aberkeinen Algorithmus gibt, der die Lösung in polynomieller Zeit �ndet.Das Hamiltonkreisproblem ist also schwerer zu lösen, weil es NP-vollständig ist, währenddas Matchingproblem in der Klasse P liegt.Mittlerweile ist die Graphentheorie eines der bedeutendsten Teilgebiete der Informatik,nicht nur, weil die Graphentheorie viele Fragen hervorgebracht hat, sondern auch, weilsie bei die Lösung vieler Probleme weiterhilft. So läuft zum Beispiel ein Ansatz zur Lö-sung das �P=NP?�-Problems auf die graphentheoretische Frage nach einem Hamiltonkreishinaus. Genauer sucht man nach einem Netzwerk, dass zu einem Graphen mit n Knotenausgibt, ob es einen Hamiltonkreis besitzt. Das Netzwerk kann man konstruieren, indemman zunächst die Knoten von 1 bis n durchnummeriert und dann die Werte vi,j genaudann auf wahr setzt, wenn der i-te und j-te Knoten durch eine Kante verbunden sind.Auf diese Weise werden dem Netzwerk

(n2

)Werte zugeordnet. Das Netzwerk soll genau

dann wahr ausgeben, wenn der Graph einen Hamiltonkreis besitzt. Wie man ein solchesNetzwerk konstruiert ist bekannt, für die Lösung des �P=NP�-Problems fehlt allerdingsdie Antwort auf die Frage, ob man die Gröÿe des Netzwerks durch ein Polyom angebenkann.

8

4 Die probabilistische Methode

4.1 Zufällige Graphen

Für einen zufälligen Graphen ist die Anzahl n der Knoten festgelegt. Dann werden mweitere Kanten zufällig eingefügt (zwischen Knoten, die nicht bereit durch eine Kanteverbunden sind). Abhängig davon, ob m ≤ 0, 49n oder m ≥ 0, 51n ist entstehen vieleEinzelkomponenten oder eine groÿe zusammenhängende Komponente (dies wurde bereitsbei der Vorstellung der Hauptseminare kurz erläutert). Sind m und n groÿ, so sind sichdie entstehenden Graphen nach dem Gesetz der groÿen Zahlen meist ähnlich. Es istmöglich typische Eigenschaften solcher Graphen zu �nden und diese für das Verständnisder Graphentheorie zu nutzen.

4.2 Bsp. eines Beweises durch Wahrscheinlichkeitstheorie

Aber auch in anderer Hinsicht ist die Wahrscheinlichkeitstheorie in der Graphentheoriesehr nützlich, wie ich an einem Beispiel zeigen möchte.

Satz: Ein Hypergraph H ist 2-färbbar, falls jede Kante von H höchstens r Knoten tri�t,und H weniger als 2r−1 Kanten hat.10

Beweis: Für einen Graphen (also r = 2) ist diese Aussage klar: Da der Graph nachVoraussetzung weniger als 2r−1 = 22−1 = 2 Kanten hat, ist er o�ensichtlich bipartit.(Ein nicht bipartiter Graph hat mindestens zwei Kanten, da er wenn er nur eine Kantehätte auch nur zwei Knoten haben könnte und damit bipartit wäre.)Für einen Hypergraphen gibt es jedoch über �normale� Methoden (wie Induktion) kei-ne Beweise, möglich ist aber ein Beweis mittels Wahrscheinlichkeitstheorie. Man färbtdie Knoten zufällig in 2 verschiedenen Farben (etwa durch Münzwurf). Wenn nun dieWahrscheinlichkeit, dass alle Kanten zweifarbig sind echtpositiv ist, so ist der Graphzweifärbbar.A := Der Graph ist zweifärbbarBi := i-te Kante ist einfarbigMan berechnet zunächst de Wahrscheinlichkeit, dass eine bestimmte Möglichkeit bei derder Graph nicht zweigefärbt ist eintritt. Dies ist gerade die Wahrscheinlichkeit, dass min-destens eine Kante einfarbig ist.Es gibt 2r Möglichkeiten um Färben der Knoten einer Kante (r Knoten mit jeweils 2Möglichkeiten). Bei zwei dieser Möglichkeiten ist die Kante einfarbig, also gilt:

9

4 Die probabilistische Methode

P (Bi) =2

2r= 21−r

P (∪iBi) ≤ ΣiP (Bi) = Σi21−r

Das ist die Wahrscheinlichkeit, dass mindestens eine Kante einfarbig ist. Da es nach Vor-aussetzung weniger als 2r−1 Kanten gibt gilt:

Σi21−r < 2r−1 · 21−r = 1

Da P (A) = 1− P (∪iBi) > 0 ist der Graph zweifärbbar. �Tatsächlich gilt die Aussage sogar ohne Einschränkung an die Kantenzahl, es darf aberjede Kante nur 2r−3

Neben der Stochastik �nden viele weitere Gebiete der Mathematik in der GraphentheorieAnwendung (z.B. Algebra und Topologie).

10

5 Anwendungen

5.1 Anwendungsbeispiele

Sehr groÿe Graphen werden auch Netzwerke genannt. Das verbreitetste Beispiel hierfürist das Internet, das wiederum aus verschiedenen Netzwerken besteht, wie dem Netzwerkder mit oder ohne Kabel (= Kanten) verbundenen Geräte ( = Knoten), oder dem Netz-werk der Internetseiten (=Knoten), die durch Links (=Kanten) miteinander verbundensind.Alltäglich sind auch soziale Netzwerke, bei denen Menschen die Knoten, und Verbin-dungen unter Menschen die Kanten darstellen. Diese Netzwerke sind von Soziologen bisheute noch nicht richtig verstanden worden, von allen sozialen Netzwerken am Bestenverstanden sind aber solche im Internet wie etwa Facebook.Netzwerke sind sind auch grundlegend, um weitere Erkenntnisse in der Biologie zu er-zielen, so sind z.B. unser Gehirn oder der Wald (Tiere und P�anzen, die einander beein-�ussen) groÿe Netzwerke, die bei weitem noch nicht gänzlich verstanden sind und die aufneue �Werkzeuge� aus der Graphentheorie angewiesen sind.

5.2 Sehr groÿe Graphen

Es gibt auch Fälle, in denen man �unendlich groÿe� Graphen durch endliche approximie-ren will, oder auch umgekehrt endliche Graphen als �unendliche� betrachten will.Der erste Fall tritt in der Physik häu�g auf, wenn man Gleichungen auf die Raumzeitanwenden muss. Ein sehr bekanntes Beispiel dafür ist die Wettervorhersage, bei der nurendlich viele Punkte betrachtet werden und dann die Entwicklung von Druck, Tempera-tur,... in diesen Punkten berechnet wird.Aber auch die umgekehrte Richtung �ndet häu�g Verwendung, so betrachtet zum Bei-spiel ein Metallbauer sein Metall als eine kontinuierliche Masse, obwohl sie ja eigentlichaus Atomen besteht und damit diskret ist. Warum das funktioniert sieht man an folgen-dem Beispiel:Für das linke Bild wurde ein zufälliger Graph konstruiert, bei dem, wenn bereits n Knotenvorhanden sind, mit Wahrscheinlichkeit 1

n ein neuer Knoten und mit Wahrscheinlichkeitn−1n eine neue Kante zwischen zwei zufälligen Knoten entsteht. In dem Bild ist die Ko-

ordinate (x,y) genau dann schwarz gefärbt, wenn der x-te und y-te Knoten durch eineKante verbunden sind. Da die Knoten in der linken oberen Ecke früher entstanden sind,sind sie auch mit höherer Wahrscheinlichkeit miteinander verbunden, also ist es dortdunkler.Das rechte Bild ist der Graph der Funktion 1-max(x,y). Obwohl der linke Graph zufällig

11

5 Anwendungen

Abbildung 5.1: Zufälliger Graph mit 100 Knoten und Funktion 1-max(x,y)

un diskret und der rechte Graph stetig ist, sehen sie sich doch sehr ähnlich. Diese Bildersind mit 100 Knoten, mit 1000 Knoten wird die Ähnlichkeit sogar noch gröÿer.Die Graphentheorie ist also ein Teilgebiet der Mathematik, das groÿe Auswirkungen aufandere Bereiche hat, und in dem noch viele Resultate bewiesen werden müssen.

12

6 Literatur

Grundlage ist das Buch �Eine Einführung in die Mathematik� herausgegeben von DierkSchleicher und Malte Lackmann, das Kapitel �45 Jahre Graphentheorie� von László Lo-vász (Seiten 87-98)

�Fermats letzter Satz� von Simon Singh, die Seiten 102-104.(Beweis KönigsbergerBrückenproblem)

http://page.math.tu-berlin.de/∼felsner/Lehre/GrTh05/Graphentheorie.pdf, S.17 (Hei-ratsproblem)

http://www.mathematik.uni-wuerzburg.de/∼ schwartz/Lehre/Graphentheorie/SkriptGraphentheorieSchwartz.pdf,S.4-5 (De�nition Graph, Grad eines Knoten), S.2 und S.61 (Heiratsproblem)

https://de.wikipedia.org/wiki/P-NP-Problem

1 http://www.mathematik.uni-wuerzburg.de/∼ schwartz/Lehre/Graphentheorie/SkriptGraphentheorieSchwartz.pdf,S.7

2 und 3 �Eine Einführung in die Mathematik�,S.89

Abb.1.1: http://www.friderizianer.de/enzyklopaedie/euler-bruecken/Abb.1.2:selbst gemachtAbb.3.1: Abb. 1.1 mit selbst eingefügten LinienAbb.3.2:selbst gemachtAbb.5.1:�Eine Einführung in die Mathematik�, S.98

13