Graphentheorie: Übungsaufgaben mit Schritt-für-Schritt-Lösungen

1Knoten, Kanten und Grade

Ein Graph besteht aus Knoten (Punkten) und Kanten (Linien zwischen zwei Knoten). In einem einfachen Graphen gibt es keine Schleifen und keine Mehrfachkanten.

Der Grad eines Knotens ist die Anzahl der Kanten, die an ihm enden. Jede Kante hat zwei Enden und erhöht daher den Grad jedes Endes um 1. Das ergibt das Handschlaglemma:

Zwei Folgerungen: Die Summe der Grade ist immer gerade, und auch die Anzahl der Knoten mit ungeradem Grad ist gerade.

• Der vollständige Graph K_n verbindet jedes Paar: n(n − 1)/2 Kanten.
• Der vollständige bipartite Graph K_m,n verbindet jeden Knoten der einen Seite mit jedem Knoten der anderen Seite: m·n Kanten.
• Ein k-regulärer Graph mit n Knoten hat n·k/2 Kanten.

Die Adjazenzmatrix hat an der Stelle (i, j) eine 1, wenn i und j verbunden sind. Für einen ungerichteten Graphen ist sie symmetrisch, eine Zeilensumme ist ein Grad, und der Eintrag (i, j) von Mᴸ zählt die Wege der Länge L von i nach j.

2Euler und Hamilton

Ein Euler-Kreis benutzt jede Kante genau einmal und kehrt zum Start zurück. Ein Euler-Weg benutzt jede Kante einmal, darf aber woanders enden. Für einen zusammenhängenden Graphen gilt:

• alle Grade gerade: Ein Euler-Kreis existiert;
• genau zwei ungerade Grade: Ein Euler-Weg existiert, von einem ungeraden Knoten zum anderen;
• mehr als zwei ungerade Grade: keines von beiden.

Ein Hamilton-Kreis besucht jeden Knoten genau einmal. Dafür gibt es keinen einfachen Gradtest. In K_n gibt es (n − 1)!/2 verschiedene Hamilton-Kreise: Lege den Start fest, ordne die übrigen n − 1 Knoten und teile durch 2 wegen der beiden Richtungen.

3Bäume

Ein Baum ist ein zusammenhängender Graph ohne Kreise. Jeder Baum mit n Knoten hat genau n − 1 Kanten. Fügt man irgendeine Kante hinzu, entsteht ein Kreis; entfernt man irgendeine Kante, zerfällt er.

Ein Wald aus c Bäumen mit n Knoten hat n − c Kanten. Ein zusammenhängender Graph mit m Kanten behält einen aufspannenden Baum, wenn man m − n + 1 Kanten entfernt.

Das Handschlaglemma zählt die Blätter: Σ deg = 2(n − 1). Eine Kurzform ist L = 2 + Σ (d − 2) über die Knoten mit Grad d ≥ 3. Ein Baum mit zwei Knoten vom Grad 3 und sonst nur Blättern hat 2 + 1 + 1 = 4 Blätter.

4Dijkstra und minimale aufspannende Bäume

Der Dijkstra-Algorithmus findet kürzeste Abstände von einem Startknoten in einem Graphen mit nichtnegativen Gewichten.

1. Gib dem Startknoten den Abstand 0 und allen anderen Knoten ∞.
2. Schließe den offenen Knoten mit dem kleinsten Abstand ab; sein Abstand ist nun endgültig.
3. Aktualisiere für jeden Nachbarn v: d(v) = min(d(v), d(u) + w(u, v)).
4. Wiederhole, bis der Zielknoten abgeschlossen ist.

Ein minimaler aufspannender Baum verbindet alle Knoten mit dem kleinsten Gesamtgewicht. Kruskal sortiert die Kanten von leicht nach schwer und nimmt jede, sofern sie keinen Kreis schließt. Prim lässt einen Baum von einem Startknoten aus wachsen und fügt immer die leichteste Kante hinzu, die aus ihm herausführt. Beide hören nach n − 1 Kanten auf.

5Häufige Fehler

• Vergessen, die Gradsumme durch 2 zu teilen, um die Kantenzahl zu erhalten.
• Auf einen Euler-Kreis testen, ohne zu prüfen, ob der Graph zusammenhängend ist.
• Einen Knoten bei Dijkstra abschließen, bevor er den kleinsten vorläufigen Abstand hat.
• Die n − 1 leichtesten Kanten nehmen, ohne auf Kreise zu achten.
• Hamilton-Kreise von K_n als n! statt als (n − 1)!/2 zählen.

6So sehen Prüfungsaufgaben aus

• Leicht: Grade und Kanten. Du verwendest das Handschlaglemma, zählst die Kanten von K_n, K_m,n, regulären Graphen und Bäumen, liest eine Adjazenzmatrix ab oder klickst den Knoten mit einem gegebenen Grad an.
• Mittel: Euler-Wege und Bäume. Du entscheidest, ob ein Graph einen Euler-Kreis oder -Weg hat, zählst die Blätter eines Baums, zählst die Kanten, die für einen aufspannenden Baum zu entfernen sind, oder zählst die Hamilton-Kreise in K_n.
• Schwer: kürzeste Wege und aufspannende Bäume. Du führst den Dijkstra-Algorithmus aus, findest den Knoten, der in einer bestimmten Runde abgeschlossen wird, bestimmst das Gewicht eines minimalen aufspannenden Baums, klickst die Kante an, die Kruskal oder Prim als Nächstes hinzufügt, oder zählst Wege mit der Adjazenzmatrix.