Graphentheorie

Ein Graph besteht aus Knoten (Punkten) und Kanten (Linien), die je zwei Knoten verbinden. Mit einem Graphen beschreibst du, wer womit zusammenhängt: Haltestellen und Gleise, Personen und Freundschaften, Städte und Straßen. Die Graphentheorie untersucht solche Netze. Ob eine Linie gerade oder krumm ist und wo die Punkte liegen, spielt keine Rolle. Nur die Verbindungen zählen.

Mit dem Graphen einer Funktion hat das nichts zu tun. Dieselbe Bezeichnung steht hier für ein Netz aus Punkten und Linien. Die berühmteste Geschichte der Graphentheorie, das Königsberger Brückenproblem, steht ausführlich bei Leonhard Euler. Hier gibt es nur eine kurze Zusammenfassung.

Grundbegriffe

Die Knoten eines Graphen bekommen meist Namen oder Nummern. Zwei Knoten, die durch eine Kante verbunden sind, heißen Nachbarn. Der Grad eines Knotens ist die Zahl der Kanten, die an ihm enden. Im Bild haben $A$, $B$, $E$ und $F$ den Grad 2, die Knoten $C$ und $D$ den Grad 3.

Außerdem brauchst du diese Wörter:

• Weg: eine Folge von Kanten, bei der jede an der Stelle beginnt, an der die vorige endet. Von $A$ nach $F$ führt zum Beispiel der Weg $A,C,D,F$.
• Kreis: ein Weg, der am Startknoten endet und dabei keinen anderen Knoten zweimal besucht. Im Bild sind $A,B,C$ und $D,E,F$ jeweils ein Kreis.
• Zusammenhängend: Von jedem Knoten gibt es einen Weg zu jedem anderen. Der Graph im Bild ist zusammenhängend.
• Brücke: eine Kante, ohne die der Graph in zwei Teile zerfällt. Im Bild ist $CD$ eine Brücke.

Gerichtete Graphen und Graphen mit Gewichten behandeln wir weiter unten.

Das Handschlaglemma

Jede Kante hat zwei Enden, und jedes Ende zählt beim Grad eines Knotens mit. Zählst du die Grade aller Knoten zusammen, hast du also jede Kante zweimal gezählt:

Der Name kommt von einem Bild: Auf einer Feier schütteln sich Gäste die Hand. Jeder Handschlag hat zwei Beteiligte. Die Summe der Handschläge, die alle Gäste gezählt haben, ist doppelt so groß wie die Zahl der Handschläge. Im Bild oben ist die Gradsumme $2+2+3+3+2+2=14$ und die Kantenzahl 7.

Bäume

Ein Baum ist ein zusammenhängender Graph ohne Kreis. Ein Stammbaum, die Ordnerstruktur auf einem Computer oder ein Baumdiagramm in der Wahrscheinlichkeitsrechnung sind Bäume. Bäume haben besondere Eigenschaften:

• Ein Baum mit $n$ Knoten hat genau $n-1$ Kanten.
• Zwischen zwei Knoten gibt es genau einen Weg.
• Entfernst du eine Kante, zerfällt der Baum in zwei Teile. Jede Kante ist also eine Brücke.

Bäume sind die „billigsten“ Netze: Sie verbinden alle Knoten mit der kleinsten Zahl von Kanten. Wenn du zum Beispiel 12 Dörfer mit Leitungen verbindest, brauchst du mindestens 11 Leitungen, und mit 11 Leitungen genügt es, wenn sie keinen Kreis bilden.

Eulerwege und Eulerkreise

In Königsberg wollte man einen Spaziergang machen, der jede der sieben Brücken genau einmal benutzt. Euler übersetzte das Rätsel 1735 in einen Graphen: Die vier Landstücke wurden Knoten, die Brücken Kanten. Die Grade waren 5, 3, 3 und 3, alle ungerade, und der Spaziergang war unmöglich.

Allgemein heißt ein Weg, der jede Kante genau einmal enthält, Eulerweg. Kehrt er zum Startknoten zurück, ist es ein Eulerkreis. Das Argument von Euler: Wer einen Knoten unterwegs betritt, muss ihn wieder verlassen, und dafür braucht er zwei Kanten. Nur der Start und das Ziel dürfen einen ungeraden Grad haben.

Das Haus vom Nikolaus

Das Haus vom Nikolaus („Das ist das Haus vom Ni-ko-laus“) ist ein Strichspiel: Du sollst es in einem Zug zeichnen, ohne eine Linie zweimal zu ziehen. Das Haus ist ein Graph mit 5 Knoten und 8 Kanten.

Die Grade sind 3, 3, 4, 4 und 2, die Summe ist 16, also doppelt so groß wie die 8 Kanten. Genau zwei Knoten haben ungeraden Grad, nämlich die unteren Ecken $A$ und $B$. Deshalb gibt es einen Eulerweg, aber keinen Eulerkreis. Du musst unten links oder unten rechts anfangen und am anderen unteren Eck enden. Ein Weg ist $A,D,E,C,D,B,C,A,B$. Wer in der Spitze $E$ beginnt, scheitert, denn $E$ hat geraden Grad.

Hamiltonkreise

Ein Hamiltonkreis besucht jeden Knoten genau einmal und kehrt zum Start zurück. Das klingt ähnlich wie Euler, ist aber ein ganz anderes Problem. Im Haus vom Nikolaus gibt es einen: $A,B,C,E,D,A$. Er benutzt nur fünf der acht Kanten.

Für den Eulerkreis gibt es ein einfaches Kriterium (alle Grade gerade). Für den Hamiltonkreis kennt man bis heute keines, und es gibt kein schnelles Verfahren, das ihn in jedem großen Graphen findet. Verwandt ist das Problem des Handlungsreisenden: Ein Reisender soll alle Städte besuchen und möglichst kurz fahren. Die Suche nach dem kürzesten Hamiltonkreis hängt mit der berühmten offenen Frage „P gegen NP“ zusammen (siehe Millenniumsprobleme). Ihren Namen hat die Aufgabe von William Rowan Hamilton, der 1857 ein Spiel dazu erfand.

Gerichtete und gewichtete Graphen

Bei einem gerichteten Graphen haben die Kanten eine Richtung, sie sind Pfeile. Das passt zu Einbahnstraßen oder zu Links von einer Webseite auf eine andere. Bei einem gewichteten Graphen trägt jede Kante eine Zahl, ihr Gewicht. Das kann eine Entfernung, eine Fahrzeit oder ein Preis sein. Die Länge eines Weges ist die Summe der Gewichte seiner Kanten.

Die Frage, die dabei am häufigsten gestellt wird: Wie komme ich am kürzesten von einem Knoten zu einem anderen?

Kürzeste Wege mit Dijkstra

Alle Wege durchzuprobieren dauert zu lange. Der Niederländer Edsger W. Dijkstra veröffentlichte 1959 ein Verfahren, das viel schneller ist. Der Dijkstra-Algorithmus berechnet die kürzeste Entfernung vom Startknoten zu allen anderen Knoten. Die Gewichte dürfen nicht negativ sein.

1. Gib dem Startknoten die Entfernung 0 und allen anderen die Entfernung „unendlich“.
2. Wähle unter den noch nicht abgeschlossenen Knoten den mit der kleinsten Entfernung. Er ist jetzt abgeschlossen: Seine Entfernung ist endgültig.
3. Prüfe alle Nachbarn dieses Knotens: Ist der Weg über ihn kürzer als die bisher bekannte Entfernung, trägst du die neue, kleinere Zahl ein.
4. Wiederhole ab Schritt 2, bis alle Knoten abgeschlossen sind.

Navigationsgeräte arbeiten nach diesem Prinzip. Das Straßennetz ist ein Graph, die Gewichte sind Fahrzeiten, und gesucht ist der kürzeste Weg. Mit dem Rechner für kürzeste Wege kannst du eigene Graphen ausprobieren.

Färbungen

Bei einer Knotenfärbung bekommen alle Knoten Farben so, dass benachbarte Knoten verschiedene Farben haben. Die kleinste dafür nötige Zahl von Farben heißt chromatische Zahl. Ein Dreieck braucht 3 Farben, ein Graph mit vier Knoten, von denen je zwei verbunden sind, braucht 4. Ein Baum kommt immer mit 2 Farben aus. Ein Kreis mit gerader Knotenzahl braucht 2, ein Kreis mit ungerader Knotenzahl 3.

Die berühmteste Frage dazu: Wie viele Farben braucht eine Landkarte, wenn Länder mit gemeinsamer Grenze verschiedene Farben bekommen? Jede Karte ist ein planarer Graph, die Länder sind die Knoten. Der Vierfarbensatz sagt: Vier Farben genügen immer. Bewiesen haben das 1976 Kenneth Appel und Wolfgang Haken mit Hilfe eines Computers. Die Geschichte steht im Magazin unter Der Vierfarbensatz.

Planare Graphen und die Eulersche Formel

Ein Graph heißt planar, wenn du ihn so in die Ebene zeichnen kannst, dass sich keine zwei Kanten überkreuzen. Die Linien zerlegen die Ebene in Flächen, auch die unbegrenzte Außenfläche zählt dazu.

Beim Würfel mit 8 Ecken, 12 Kanten und 6 Flächen ist $8-12+6=2$. Aus der Formel folgt auch, dass nicht jeder Graph planar ist. Ein planarer Graph mit mindestens drei Knoten hat höchstens $3n-6$ Kanten. Der Graph mit fünf Knoten, von denen je zwei verbunden sind, hat $m=10$ Kanten, erlaubt wären aber nur $3·5-6=9$. Er lässt sich also nicht kreuzungsfrei zeichnen. Das berühmte Rätsel „drei Häuser, drei Brunnen“ führt auf einen zweiten nicht planaren Graphen. Nach dem Satz von Kuratowski sind diese beiden Graphen die Grundbausteine aller nicht planaren Graphen.

Wo Graphen vorkommen

• Navigation und Verkehr: Straßen- und Bahnnetze, kürzeste Wege, Verkehrsflüsse.
• Soziale Netzwerke: Personen sind Knoten, Freundschaften sind Kanten. Die Erdős-Zahl zählt, über wie viele gemeinsame Veröffentlichungen ein Mathematiker mit Paul Erdős verbunden ist.
• Internet und Computer: Rechner und Leitungen, Links zwischen Webseiten. Auch die Zustände eines Automaten, wie bei der Turingmaschine von Alan Turing, zeichnet man als Graph.
• Chemie und Planung: Moleküle sind Graphen aus Atomen und Bindungen. Stundenpläne lassen sich als Färbungsproblem schreiben.
• Kombinatorik: Viele Zählprobleme lassen sich mit Graphen darstellen. Anzahlen rechnest du mit dem Kombinatorik-Rechner nach.

Typische Fehler

Übungen

Geschichte: von Königsberg bis Dijkstra

Die Anfänge der Graphentheorie gehen auf Leonhard Euler zurück, der 1735 das Königsberger Brückenproblem löste (gedruckt 1741). Den vollständigen Beweis des Eulerschen Kriteriums lieferte später Carl Hierholzer (1873). William Rowan Hamilton erfand 1857 sein Spiel, bei dem ein Rundweg über alle 20 Ecken eines Dodekaeders gesucht wurde. Den Begriff „Graph“ benutzte als Erster der Mathematiker James Joseph Sylvester im Jahr 1878, in Anlehnung an die zeichnerische Darstellung chemischer Formeln.

Das erste Lehrbuch zur Graphentheorie schrieb 1936 der Ungar Dénes Kőnig. Ihren Aufschwung nahm das Fach mit den Computern: Dijkstra veröffentlichte 1959 seinen Algorithmus, und 1976 bewiesen Appel und Haken den Vierfarbensatz. Heute stecken Graphen in Navigationssystemen, in der Chemie und überall dort, wo es um Netze geht.

Häufige Fragen

Quellen und weiterführende Literatur

• Wikipedia: Graphentheorie
• Wikipedia: Handschlaglemma
• Wikipedia: Haus vom Nikolaus
• Wikipedia: Dijkstra-Algorithmus
• Edsger W. Dijkstra: A note on two problems in connexion with graphs. Numerische Mathematik, Band 1, 1959, S. 269 bis 271 (DOI 10.1007/BF01386390)
• Leonhard Euler: Solutio problematis ad geometriam situs pertinentis. Commentarii academiae scientiarum Petropolitanae, Band 8, 1741, S. 128 bis 140