Graphentheorie
Punkte und Linien dazwischen: Mehr ist ein Graph nicht. Doch dasselbe Bild beschreibt eine Straßenkarte, einen Freundeskreis, ein Molekül und das Internet, und die Fragen, die man dazu stellen kann – von der Zahl der nötigen Farben bis dahin, ob er sich in einem Zug zeichnen lässt –, beschäftigen Mathematiker seit 1736.
Knoten und Kanten
Ein Graph besteht aus Knoten, auch Ecken genannt, und Kanten, die jeweils zwei Knoten verbinden. Wo die Knoten gezeichnet werden, spielt keine Rolle, nur welche Paare verbunden sind; derselbe Graph kann auf dem Papier also ganz verschieden aussehen. Die Graphen im Spielplatz sind einfach: keine Kante von einem Knoten zu sich selbst und höchstens eine Kante zwischen zwei Knoten. Bei n Knoten kann es höchstens n(n − 1) / 2 Kanten geben; ein Graph, der sie alle hat, heißt vollständig, und K5 ist der vollständige Graph mit fünf Knoten.
Grade und das Handschlaglemma
Der Grad eines Knotens ist die Anzahl der Kanten an ihm. Addiert man alle Grade, erhält man genau das Doppelte der Kantenzahl, denn jede Kante hat zwei Enden und wird an jedem einmal gezählt. Das ist das Handschlaglemma: In jeder Gruppe ergeben die Händedrücke, Person für Person gezählt, zusammen das Doppelte der Anzahl der Händedrücke. Daraus folgt auch, dass die Anzahl der Knoten mit ungeradem Grad immer gerade ist. Ein Graph, in dem jeder Knoten denselben Grad k hat, heißt k-regulär.
Zusammenhängende Graphen, Bäume und Kreise
Ein Graph ist zusammenhängend, wenn man von jedem Knoten entlang der Kanten zu jedem anderen gelangt; andernfalls zerfällt er in Teile, die Zusammenhangskomponenten. Ein Kreis ist ein Rundweg, der zu seinem Start zurückkehrt, ohne einen Knoten zweimal zu benutzen, und die Länge des kürzesten heißt Taillenweite. Ein zusammenhängender Graph ohne Kreis ist ein Baum, und ein Baum mit n Knoten hat immer genau n − 1 Kanten: eine weniger, und er zerfällt, eine mehr, und er enthält einen Kreis. Jeder zusammenhängende Graph enthält einen Spannbaum, also einen Baum, der jeden Knoten erreicht und dabei nur einen Teil der Kanten benutzt.
Bipartite Graphen und Färbung
Färben Sie die Knoten so, dass keine Kante zwei Knoten derselben Farbe verbindet. Die kleinste Anzahl von Farben, mit der das gelingt, ist die chromatische Zahl. Eine Farbe reicht nur, wenn es keine Kanten gibt. Zwei Farben reichen genau dann, wenn der Graph bipartit ist: Seine Knoten zerfallen in zwei Seiten, und jede Kante führt hinüber. Dénes Kőnig zeigte 1936, dass das gleichbedeutend damit ist, keinen Kreis ungerader Länge zu haben, denn in einem ungeraden Kreis können sich zwei Farben nicht abwechseln. Für drei oder mehr Farben ist kein so einfacher Test bekannt: Zu entscheiden, ob drei Farben reichen, ist NP-vollständig, deshalb suchen Programme – so wie der Spielplatz.
Ein Beispiel: der Petersen-Graph
Nehmen Sie ein Fünfeck A–B–C–D–E und darin einen fünfzackigen Stern F–H–J–G–I, und verbinden Sie jede Ecke des Fünfecks mit einer Spitze des Sterns: A–F, B–G, C–H, D–I und E–J. Das ist der Petersen-Graph, mit 10 Knoten und 15 Kanten. Jeder Knoten hat Grad 3, die Grade ergeben also zusammen 30, das Doppelte von 15. Sein kürzester Kreis hat die Länge 5, er enthält also kein Dreieck, aber das Fünfeck ist ein ungerader Kreis, also ist er nicht bipartit und braucht 3 Farben. Je zwei Knoten sind höchstens 2 Kanten voneinander entfernt, sein Durchmesser ist also 2. Alle zehn Grade sind ungerade, deshalb hat er keinen Eulerweg, und er lässt sich nicht ohne Kreuzungen zeichnen.
Eulerwege und die Brücken von Königsberg
Die Stadt Königsberg hatte sieben Brücken, die vier Landstücke verbanden, und man fragte sich, ob man über jede Brücke genau einmal gehen könne. 1736 zeigte Leonhard Euler, dass das nicht geht – und damit begann die Graphentheorie. Jedes Mal, wenn ein Spaziergang durch ein Landstück führt, benutzt er zwei Brücken, also dürfen nur Start und Ziel eine ungerade Zahl davon haben, doch alle vier Landstücke von Königsberg hatten eine ungerade Zahl. Ein Weg, der jede Kante einmal benutzt, heißt heute Eulerweg, oder Eulerkreis, wenn er endet, wo er begonnen hat. Carl Hierholzer bewies 1873, dass die Bedingung auch ausreicht: Wenn alle Kanten zusammenhängen und höchstens zwei Grade ungerade sind, existiert der Weg, und sein Verfahren, Rundwege aneinanderzufügen, findet ihn bis heute.
Abstand, Durchmesser und Komplement
Der Abstand zweier Knoten ist die kleinste Anzahl von Kanten auf einem Weg zwischen ihnen, und der Durchmesser ist der größte Abstand im Graphen; in einem nicht zusammenhängenden Graphen ist er unendlich. Soziale Netzwerke haben kleine Durchmesser – das ist die Idee dahinter, dass jeder jeden über sechs Ecken kennt. Das Komplement eines Graphen hat dieselben Knoten und verbindet genau die Paare, die nicht verbunden waren. Von einem Graphen und seinem Komplement ist immer mindestens einer zusammenhängend.
Probieren Sie es aus
Der Spielplatz öffnet mit dem Petersen-Graphen in drei Farben. Klicken Sie auf Grade und prüfen Sie das Handschlaglemma, klicken Sie auf Bipartit, um einen ungeraden Kreis zu sehen, laden Sie dann den Würfel und sehen Sie, wie die zwei Seiten erscheinen. Laden Sie das Haus vom Nikolaus und klicken Sie auf Eulerweg, um zu sehen, wo der Zug beginnen muss. Zeichnen Sie Ihren eigenen Graphen und fügen Sie Kante für Kante hinzu: Beobachten Sie, wie der kürzeste Kreis schrumpft, der Durchmesser sinkt und die chromatische Zahl steigt, sobald die letzte Kante eines K4 hinzukommt.
Häufig gestellte Fragen
Was ist der Unterschied zwischen Pfad, Kantenzug und Kantenfolge?
Eine Kantenfolge ist irgendeine Folge von Knoten, die durch Kanten verbunden sind, und darf beides wiederholen. Ein Kantenzug darf Knoten wiederholen, aber keine Kanten; deshalb kann ein Eulerweg, genau genommen ein Eulerzug, mehrmals durch denselben Knoten führen. Ein Pfad wiederholt weder Knoten noch Kanten.
Was ist der Vier-Farben-Satz?
Er besagt, dass sich jeder Graph, den man ohne Kantenkreuzungen auf Papier zeichnen kann, mit höchstens vier Farben färben lässt – jede Landkarte braucht also nicht mehr als vier. Bewiesen wurde er 1976 von Kenneth Appel und Wolfgang Haken mit Hilfe eines Computers, als erster großer Satz, der auf diese Weise bewiesen wurde.
Was ist ein Hamiltonkreis?
Ein Kreis, der jeden Knoten genau einmal besucht statt jede Kante. Das klingt wie die Euler-Frage, doch dafür ist kein einfacher Test bekannt: Zu entscheiden, ob ein Graph einen solchen Kreis hat, ist NP-vollständig. Der Petersen-Graph hat einen Hamiltonpfad, aber keinen Hamiltonkreis.
Wo wird Graphentheorie angewendet?
Routenplaner durchsuchen Straßengraphen, Suchmaschinen bewerten Webseiten nach ihren Links, Compiler färben Graphen, um Prozessorregister zu teilen, Stundenpläne vermeiden Überschneidungen durch das Färben eines Konfliktgraphen, Chemiker zählen Moleküle als Graphen, und Netze aus Computern, Stromleitungen und Freunden werden als Graphen untersucht.
Bereit, es auszuprobieren?
Öffnen Sie PictorX in Ihrem Browser – keine Installation, zum Starten ist keine Kreditkarte erforderlich.
Den Graphentheorie-Spielplatz öffnen