Graphen, Grade und Eulerzüge
Definition und Geltungsbereich FAKT
Ein endlicher ungerichteter Multigraph G=(V,E) besteht aus einer endlichen Menge von Knoten V und einer endlichen Sammlung von Kanten E. Jede Kante verbindet zwei Knoten, ohne eine Durchlaufrichtung vorzugeben. Mehrere Kanten können dasselbe Knotenpaar verbinden; eine Schleife kann außerdem einen Knoten mit sich selbst verbinden. Ein schlichter Graph ist der Sonderfall ohne Schleifen und parallele Kanten.
Dieser Rahmen wurde gewählt, weil mehrere Brücken in Königsberg dieselben Landgebiete verbanden: Zu ihrer Darstellung sind parallele Kanten erforderlich. Der Artikel behandelt weder gerichtete Graphen, bei denen eine Kante eine Richtung besitzt, noch gewichtete Graphen, bei denen sie beispielsweise eine Entfernung oder Kosten trägt.
Der zugrunde liegende Multigraph bewahrt daher nur die Inzidenzbeziehung: welche Knoten jede Kante verbindet. Die gezeichneten Positionen, Längen und Winkel gehören nicht zu seiner Definition. Diese Daten können dem Modell hinzugefügt werden, wenn sie nützlich sind, für das hier untersuchte Problem sind sie jedoch nicht erforderlich.
Der grundlegende Wortschatz FAKT
| Begriff | Definition in einem ungerichteten Multigraphen |
|---|---|
| Grad eines Knotens | Anzahl der am Knoten inzidenten Kantenenden; eine Schleife zählt als 2 |
| Kantenfolge | Folge inzidenter Knoten und Kanten; Knoten und Kanten dürfen sich wiederholen |
| Kantenzug | Kantenfolge, die keine Kante wiederholt |
| Weg | Kantenfolge, die keinen Knoten wiederholt |
| Geschlossener Kantenzug | Kantenzug, bei dem Anfang und Ende übereinstimmen |
| Kreis | Geschlossener Kantenzug, der außer dem gemeinsamen Anfangs- und Endknoten keinen Knoten wiederholt |
| Zusammenhängend | Ein Weg verbindet jedes Knotenpaar |
Ein Eulerzug benutzt jede Kante genau einmal. Er ist offen, wenn seine Endpunkte verschieden sind, und wird zu einem Eulerkreis, wenn er zu seinem Anfangsknoten zurückkehrt. Das Wort „eulersch“ bezieht sich hier auf die Kanten, nicht auf die Knoten.
Das Handschlaglemma FAKT
Jede gewöhnliche Kante besitzt zwei Enden und erhöht den Grad jedes ihrer Knoten um 1. Auch eine Schleife besitzt zwei Enden, die beide am selben Knoten liegen, und erhöht dessen Grad daher um 2. Unter Berücksichtigung der Vielfachheit trägt jede Kante genau 2 zur Gesamtsumme bei:
v∈V∑deg(v)=2∣E∣
Die rechte Seite ist gerade. Knoten geraden Grades tragen eine gerade Summe bei; somit muss auch die Summe der ungeraden Grade gerade sein. Eine Summe ungerader ganzer Zahlen ist genau dann gerade, wenn sie eine gerade Anzahl von Summanden enthält. Daher gibt es stets eine gerade Anzahl von Knoten ungeraden Grades.
In einem schlichten Graphen, der eine Versammlung darstellt, bedeutet eine Kante, dass sich zwei Personen die Hand gegeben haben. Das Lemma besagt dann, dass die Anzahl der Personen, die an einer ungeraden Anzahl von Handschlägen beteiligt waren, gerade ist. Dieses Bild erklärt seinen Namen, der Beweis gilt mit der vorstehenden Gradkonvention jedoch ebenso für Multigraphen und Schleifen.
Die Brücken von Königsberg FAKT
Das historische Problem beschreibt vier Landgebiete, die durch sieben Brücken verbunden sind. Gesucht war ein Spaziergang, der jede Brücke genau einmal überquert, ohne zum Ausgangspunkt zurückkehren zu müssen.
Euler bezeichnete die Gebiete mit Buchstaben und stellte die aufeinanderfolgenden Überquerungen durch Buchstabenfolgen dar. In der modernen graphentheoretischen Neuformulierung wird jedes Gebiet zu einem Knoten und jede Brücke zu einer Kante. Der entstehende Multigraph besitzt vier Knoten mit den Graden 5, 3, 3 und 3. Ihre Summe beträgt 14, also zweimal die Anzahl der sieben Kanten, wie es dem Lemma entspricht.
In einem Eulerzug werden alle inzidenten Kanten benutzt. Jeder Durchgang durch einen Zwischenknoten verbraucht sie paarweise: eine zum Eintreten und eine zum Verlassen. Daher haben nur Anfang und Ende eines offenen Eulerzugs einen ungeraden Grad, während ein Eulerkreis keinen solchen Knoten besitzt.
Königsberg besitzt vier davon. Es gibt keinen Kantenzug, der jede der sieben Brücken genau einmal benutzt. Euler wies diese Unmöglichkeit nach und formulierte die allgemeinen Paritätsregeln; der moderne Satz liefert die vollständige Charakterisierung.
Der moderne eulersche Satz FAKT
Betrachten wir einen endlichen ungerichteten Multigraphen, in dem alle Knoten von Grad ungleich null derselben Zusammenhangskomponente angehören.
- Er besitzt genau dann einen Eulerkreis, wenn alle seine Knoten geraden Grad haben.
- Er besitzt genau dann einen offenen Eulerzug, wenn genau zwei Knoten ungeraden Grad haben; sie sind notwendigerweise sein Anfang und sein Ende.
Die Notwendigkeit folgt aus der Paarung von Eintritt und Austritt. Die Hinlänglichkeit ist konstruktiv. Sind alle Grade gerade, beginnt man an einem Knoten, der an einer Kante liegt, und folgt noch unbenutzten Kanten. An einem anderen Knoten kann man nicht stecken bleiben: Aufgrund der Parität lässt jede Ankunft dort eine unbenutzte Kante zum Weitergehen übrig. Der Kantenzug kehrt daher schließlich zum Ausgangspunkt zurück und bildet einen geschlossenen Kantenzug.
Bleiben Kanten übrig, garantiert der Zusammenhang, dass ein Knoten des geschlossenen Kantenzugs einen noch unbenutzten Teil berührt. Von diesem Knoten aus konstruiert man einen neuen geschlossenen Kantenzug und fügt ihn dann in den ersten ein. Durch Wiederholen dieses Vorgangs erhält man einen geschlossenen Kantenzug, der alle Kanten enthält: Dies ist das Prinzip des Algorithmus von Hierholzer.
Gibt es genau zwei Knoten ungeraden Grades, fügt man vorübergehend eine Kante zwischen ihnen hinzu. Dadurch werden alle Grade gerade; man konstruiert einen Eulerkreis und entfernt anschließend die hinzugefügte Kante. Der Kreis öffnet sich dann zu einem Eulerzug, dessen Endpunkte genau die beiden Knoten ungeraden Grades sind.
Modellierung verlangt die Wahl der richtigen Struktur FAKT
Straßen, Softwareabhängigkeiten, Moleküle und elektrische Schaltungen können alle durch Graphen dargestellt werden, jedoch nicht ohne nähere Bestimmung durch dasselbe Modell.
- Ein Straßennetz kann ungerichtet oder gerichtet sein und trägt häufig Entfernungen oder Fahrzeiten.
- Ein Abhängigkeitsgraph ist in der Regel gerichtet: Ein Kreis drückt darin eine zirkuläre Abhängigkeit aus.
- Ein Molekülgraph trägt Beschriftungen an Atomen und Bindungen.
- Ein elektrisches Netz ergänzt physikalische Größen und Gesetze, die in der bloßen Inzidenz nicht enthalten sind.
Der Nutzen der Abstraktion besteht also nicht darin, dass überall ein einziger Algorithmus geeignet wäre. Vielmehr trennt sie die gemeinsame Struktur — Knoten und Kanten — von den domänenspezifischen Informationen; anschließend wird ein Satz oder Algorithmus gewählt, dessen Voraussetzungen genau dem konstruierten Graphen entsprechen.
Zusammenfassung
In einem endlichen ungerichteten Multigraphen, dessen Kanten derselben Komponente angehören, entscheidet die Parität der Grade, ob jede Kante genau einmal durchlaufen werden kann: null Knoten ungeraden Grades für einen Eulerkreis, genau zwei für einen offenen Eulerzug.