6. Graphenalgorithmen – OR Klausurvorbereitung

Auf einen Blick

Ein Graph \(G=(V,E)\) besteht aus Knotenmenge \(V\) und Kantenmenge \(E \subseteq V\times V\); Kanten können gerichtet oder ungerichtet, gewichtet oder ungewichtet sein.
Ein Baum ist ein zusammenhängender, kreisfreier, ungerichteter Graph – die Grundlage für Spannbäume.
Der Kruskal-Algorithmus findet einen minimalen Spannbaum, indem er Kanten aufsteigend nach Gewicht sortiert und kreis-frei einfügt.
Der Dijkstra-Algorithmus berechnet kürzeste Wege von einem Startknoten – nur bei nicht-negativen Kantengewichten korrekt.
Darstellungen: Adjazenzmatrix (n×n, gut für dichte Graphen) und Adjazenzliste (kompakter bei dünnen Graphen).

Kernkonzepte

Grundbegriffe

Ein Graph ist ein Paar \(G=(V,E)\) aus:

V – die endliche Knotenmenge (engl. vertices).
E – die Kantenmenge mit \(E \subseteq V \times V\) (engl. edges).

Gerichtet vs. ungerichtet

Bei einem gerichteten Graphen (Digraph) sind die Kanten geordnete Paare \((u,v)\) – die Richtung von \(u\) nach \(v\) ist relevant. Bei einem ungerichteten Graphen gilt \(\{u,v\}=\{v,u\}\); eine Kante verbindet zwei Knoten symmetrisch.

Weitere Begriffe

Kantenfolge: Abfolge von Knoten, verbunden durch Kanten – z. B. \(v_1 \to v_2 \to v_3\).
Zusammenhängend: Zwischen je zwei Knoten existiert eine Kantenfolge.
Kreis / Zyklus: Eine Kantenfolge, die am selben Knoten startet und endet, ohne dass eine Kante mehrfach verwendet wird.
Baum: Zusammenhängend + kreisfrei + ungerichtet. Für \(n\) Knoten hat ein Baum genau \(n-1\) Kanten.
Gewichteter Graph: Jeder Kante \(e\) ist ein Gewicht \(c(e) \in \mathbb{R}\) zugeordnet (z. B. Entfernung, Kosten, Zeit).

Merksatz: Ein Baum mit \(n\) Knoten hat immer genau \(n-1\) Kanten. Fügt man eine weitere Kante hinzu, entsteht zwangsläufig ein Kreis.

Darstellungen von Graphen

Adjazenzmatrix

Eine \(n \times n\)-Matrix \(A\) mit \(A_{ij} = 1\), wenn Kante \((i,j)\) existiert, sonst \(0\). Bei gewichteten Graphen: \(A_{ij} = c(i,j)\), sonst \(\infty\) oder \(0\).

A = [[0, 3, 0, 7],
     [3, 0, 2, 0],
     [0, 2, 0, 5],
     [7, 0, 5, 0]]

Vorteile: schneller Kanten-Check in \(O(1)\). Nachteil: Speicher \(O(n^2)\), auch bei wenigen Kanten.

Adjazenzliste

Für jeden Knoten wird eine Liste seiner Nachbarn geführt. Bei gewichteten Graphen inklusive Kantengewicht:

1 → [(2, 3), (4, 7)]
2 → [(1, 3), (3, 2)]
3 → [(2, 2), (4, 5)]
4 → [(1, 7), (3, 5)]

Vorteile: platzsparend bei dünnen Graphen \(O(|V|+|E|)\), schnelle Iteration über Nachbarn.

Faustregel: Dichte Graphen (viele Kanten) → Adjazenzmatrix. Dünne Graphen (wenige Kanten) → Adjazenzliste.

Minimaler Spannbaum

Ein Spannbaum eines zusammenhängenden Graphen \(G\) ist ein Teilgraph, der alle \(n\) Knoten enthält, zusammenhängend und kreisfrei ist – also selbst ein Baum mit \(n-1\) Kanten.

Der minimale Spannbaum (MST) ist derjenige Spannbaum, dessen Kantengewichts-Summe minimal ist:

minimiere \( \sum_{e \in E'} c(e) \) unter Bedingung: \(T=(V,E')\) ist Spannbaum.

Typische Anwendung: kostengünstigstes Netzwerk (Leitungen, Straßen), das alle Standorte verbindet.

Kruskal-Algorithmus

Findet einen minimalen Spannbaum durch gieriges (greedy) Hinzufügen der jeweils leichtesten Kante, die keinen Kreis erzeugt.

Ablauf

Sortiere alle Kanten aufsteigend nach ihrem Gewicht.
Initialisiere den Spannbaum \(T\) mit \(E' = \emptyset\).
Für \(i = 1, \dots, m\): Prüfe Kante \(e_i\). Falls das Hinzufügen zu \(E'\) keinen Kreis erzeugt, füge sie hinzu.
Abbruch, sobald \(|E'| = n-1\) – der Spannbaum ist vollständig.

Warum sortieren? Der Greedy-Ansatz muss die günstigsten Kanten zuerst betrachten, um garantiert das globale Minimum zu erreichen. Ohne Sortierung könnte eine teure Kante fälschlich in den Baum aufgenommen werden.

Beispiel

Gegeben ein Graph mit Kanten (Gewichten): (A,B)=1, (B,C)=2, (A,C)=3, (C,D)=4, (A,D)=5.

Sortiert: (A,B)=1, (B,C)=2, (A,C)=3, (C,D)=4, (A,D)=5.
Nimm (A,B) – kein Kreis. \(E' = \{(A,B)\}\).
Nimm (B,C) – kein Kreis. \(E' = \{(A,B),(B,C)\}\).
Verwerfe (A,C) – würde Kreis A-B-C-A erzeugen.
Nimm (C,D) – kein Kreis. \(E' = \{(A,B),(B,C),(C,D)\}\). Jetzt \(|E'| = n-1 = 3\). Stopp.

Gesamtgewicht: \(1+2+4 = 7\).

Dijkstra-Algorithmus

Findet die kürzesten Wege von einem Startknoten \(S\) zu allen anderen Knoten in einem gewichteten Graphen. Wichtige Voraussetzung: Alle Kantengewichte sind nicht-negativ (\(c(e) \geq 0\)).

Variablen

\(D[i]\): bisher gefundene kürzeste Entfernung von \(S\) zu Knoten \(i\).
\(R[i]\): Vorgänger von \(i\) auf dem kürzesten Weg (zur Rekonstruktion des Pfades).
\(MK\): Menge der aktuell markierten, noch zu bearbeitenden Knoten.

Ablauf

Initialisierung: \(MK = \{S\}\), \(D[S] = 0\), \(D[i] = \infty\) für \(i \neq S\), \(R[i]\) undefiniert.
Iteration solange \(MK \neq \emptyset\):
1. Wähle \(h \in MK\) mit \(D[h] = \min_{i \in MK} D[i]\).
2. Für jeden Nachbarn \(j\) von \(h\): setze \(D[j] = \min(D[j],\, D[h] + c(h,j))\). Falls \(D[j]\) verbessert wurde, setze \(R[j] = h\) und füge \(j\) zu \(MK\) hinzu.
3. Entferne \(h\) aus \(MK\) (Knoten ist final abgearbeitet).

Warum das minimale \(D[h]\)? Weil kein späterer Umweg über andere Knoten mit größerem \(D\) den Weg zu \(h\) mehr verkürzen kann – vorausgesetzt, alle Kantengewichte sind nicht-negativ. Damit ist \(D[h]\) endgültig.

Warum keine negativen Gewichte? Bei negativen Kanten könnte ein bereits als "fertig" markierter Knoten später doch noch günstiger erreicht werden. Die Greedy-Auswahl ist dann nicht mehr korrekt. Für negative Gewichte verwendet man stattdessen den Bellman-Ford-Algorithmus.

Bedeutung von R[i]

\(R[i]\) speichert den unmittelbaren Vorgänger von \(i\) auf dem kürzesten Weg von \(S\). Um den kompletten Pfad zu rekonstruieren, folgt man rückwärts: \(i \to R[i] \to R[R[i]] \to \dots \to S\).

Merksätze

Baum-Eigenschaft: Zusammenhängend + kreisfrei + ungerichtet + \(n-1\) Kanten für \(n\) Knoten. Diese vier Bedingungen sind untrennbar.

Kruskal-Stopp: Der Algorithmus stoppt, sobald \(n-1\) Kanten aufgenommen wurden – der Spannbaum ist dann komplett, und weitere Kanten würden nur Kreise erzeugen.

Dijkstra-Voraussetzung: Alle Kantengewichte müssen \(\geq 0\) sein. Ist eine einzige Kante negativ, kann das Ergebnis falsch werden.

Adjazenzmatrix vs. Adjazenzliste: Matrix = \(O(n^2)\) Speicher, aber \(O(1)\) für Kanten-Test. Liste = \(O(|V|+|E|)\) Speicher, aber \(O(\deg(v))\) für Kanten-Test.

Greedy funktioniert bei MST: Kruskal ist ein klassisches Greedy-Verfahren. Es liefert das globale Optimum, weil das Ersetzen einer aufgenommenen Kante durch eine leichtere immer entweder identisch oder gerade nicht kreisfrei bleibt.

🧮 Rechenaufgaben mit Lösung 6 Aufgaben

Klausur-typische Rechenaufgaben. Klick auf eine Aufgabe, um den vollständigen Lösungsweg zu sehen.

Aufgabe 1: Adjazenzmatrix → Graph zeichnen

Aufgabe: Gegeben ist die Adjazenzmatrix eines ungerichteten Graphen:

     v1  v2  v3  v4
v1 [  0   1   1   0 ]
v2 [  1   0   1   1 ]
v3 [  1   1   0   1 ]
v4 [  0   1   1   0 ]

Zeichne den Graphen und liste alle Kanten sowie die Knotengrade auf.

Lösung

Schritt 1: Prüfe Symmetrie. \(A_{ij} = A_{ji}\) für alle Paare ⇒ ungerichteter Graph. ✓

Schritt 2: Lese Einträge \(A_{ij} = 1\) mit \(i < j\) (jede Kante nur einmal):

\(A_{12} = 1\) ⇒ Kante {v1, v2}
\(A_{13} = 1\) ⇒ Kante {v1, v3}
\(A_{23} = 1\) ⇒ Kante {v2, v3}
\(A_{24} = 1\) ⇒ Kante {v2, v4}
\(A_{34} = 1\) ⇒ Kante {v3, v4}

Schritt 3: Knotengrade – zähle Einsen je Zeile:

Knoten	Zeilensumme	Grad
v1	0+1+1+0	2
v2	1+0+1+1	3
v3	1+1+0+1	3
v4	0+1+1+0	2

Skizze: v1 verbunden mit v2 und v3; v2, v3 und v4 bilden ein Dreieck; v4 ist über v2 und v3 mit dem Rest verknüpft.

Ergebnis: 5 Kanten {v1-v2, v1-v3, v2-v3, v2-v4, v3-v4}. Grade: v1=2, v2=3, v3=3, v4=2. Summe der Grade = 10 = 2·5 (Handshake-Lemma bestätigt).

Aufgabe 2: Kruskal-Algorithmus – minimaler Spannbaum

Aufgabe: Gegeben ist ein ungerichteter, gewichteter Graph mit 5 Knoten {A, B, C, D, E} und den Kanten:

(A-B: 4), (A-C: 2), (B-C: 1), (B-D: 5), (C-D: 8), (C-E: 10), (D-E: 3)

Bestimme mit Kruskal einen minimalen Spannbaum und gib das Gesamtgewicht an.

Schritt 1: Kanten aufsteigend sortieren

Nr.	Kante	Gewicht
1	B-C	1
2	A-C	2
3	D-E	3
4	A-B	4
5	B-D	5
6	C-D	8
7	C-E	10

Schritt 2: Greedy-Iteration (Abbruch bei |E'| = n − 1 = 4)

Schritt	Kante	Kreis?	Aktion	Spannbaum T
1	B-C (1)	nein	aufnehmen ✓	{B-C}
2	A-C (2)	nein	aufnehmen ✓	{B-C, A-C}
3	D-E (3)	nein	aufnehmen ✓	{B-C, A-C, D-E}
4	A-B (4)	ja: A-B-C-A	verwerfen ✗	unverändert
5	B-D (5)	nein	aufnehmen ✓	{B-C, A-C, D-E, B-D}

Nach Schritt 5: |E'| = 4 = n − 1 → Stopp.

Schritt 3: Gesamtgewicht

\(\text{Gewicht}(T) = 1 + 2 + 3 + 5 = 11\).

Ergebnis: MST = {B-C, A-C, D-E, B-D} mit Gesamtgewicht 11.

Aufgabe 3: Dijkstra-Algorithmus – kürzeste Wege

Aufgabe: Gegeben ist ein gerichteter, gewichteter Graph mit Startknoten \(S = A\) und den Kanten:

A→B: 4, A→C: 2, B→C: 1, B→D: 5, C→B: 1, C→D: 8, C→E: 10, D→E: 3

Bestimme mit Dijkstra für jeden Knoten den kürzesten Weg von A aus (Distanz \(D[i]\) und Vorgänger \(R[i]\)).

Initialisierung

\(D[A] = 0\), \(D[B] = D[C] = D[D] = D[E] = \infty\); \(MK = \{A\}\); alle \(R[i]\) undefiniert.

Iteration 1: h = A (D[A] = 0)

Kante A→B (Gewicht 4): \(D[B] = \min(\infty, 0+4) = 4\), \(R[B] = A\), \(MK \leftarrow MK \cup \{B\}\).
Kante A→C (Gewicht 2): \(D[C] = \min(\infty, 0+2) = 2\), \(R[C] = A\), \(MK \leftarrow MK \cup \{C\}\).

Entferne A aus \(MK\). Neuer Stand: \(MK = \{B, C\}\), \(D[B] = 4\), \(D[C] = 2\).

Iteration 2: min in MK ist D[C] = 2 ⇒ h = C

Kante C→B (1): \(D[B] = \min(4, 2+1) = 3\), Update, \(R[B] = C\).
Kante C→D (8): \(D[D] = \min(\infty, 2+8) = 10\), \(R[D] = C\), \(MK \leftarrow MK \cup \{D\}\).
Kante C→E (10): \(D[E] = \min(\infty, 2+10) = 12\), \(R[E] = C\), \(MK \leftarrow MK \cup \{E\}\).

Entferne C. Neuer Stand: \(MK = \{B, D, E\}\), \(D[B] = 3, D[D] = 10, D[E] = 12\).

Iteration 3: min in MK ist D[B] = 3 ⇒ h = B

Kante B→C: C ist bereits entfernt, keine Aktualisierung nötig.
Kante B→D (5): \(D[D] = \min(10, 3+5) = 8\), Update, \(R[D] = B\).

Entferne B. Neuer Stand: \(MK = \{D, E\}\), \(D[D] = 8, D[E] = 12\).

Iteration 4: min in MK ist D[D] = 8 ⇒ h = D

Kante D→E (3): \(D[E] = \min(12, 8+3) = 11\), Update, \(R[E] = D\).

Entferne D. Neuer Stand: \(MK = \{E\}\), \(D[E] = 11\).

Iteration 5: h = E

E hat keine ausgehenden Kanten. Entferne E. \(MK = \emptyset\) → Ende.

Endergebnis-Tabelle

Knoten	D[i]	R[i]	Kürzester Weg
A	0	–	A
B	3	C	A → C → B
C	2	A	A → C
D	8	B	A → C → B → D
E	11	D	A → C → B → D → E

Ergebnis: D[A]=0, D[B]=3, D[C]=2, D[D]=8, D[E]=11. Der Weg A → C → B → D → E ist mit Länge 11 der längste dieser kürzesten Wege.

Aufgabe 4: Baum-Eigenschaften prüfen

Aufgabe: Ein ungerichteter Graph hat 6 Knoten und 5 Kanten und ist zusammenhängend. Handelt es sich um einen Baum? Begründe formal.

Schritt 1: Baum-Kriterium erinnern

Ein ungerichteter Graph \(G = (V, E)\) ist genau dann ein Baum, wenn er zusammenhängend, kreisfrei und \(|E| = |V| - 1\) hat. Aus zwei beliebigen dieser drei Eigenschaften folgt die dritte automatisch.

Schritt 2: Werte einsetzen

Hier gilt: \(|V| = 6\), also müsste ein Baum genau \(|V| - 1 = 5\) Kanten haben. Vorgabe: \(|E| = 5\). ✓

Schritt 3: Zusammenhang + Kantenzahl ⇒ kreisfrei

Ist ein zusammenhängender Graph mit \(n\) Knoten und genau \(n-1\) Kanten gegeben, muss er kreisfrei sein. Andernfalls: Ein Kreis würde bedeuten, dass eine Kante entfernt werden kann, ohne den Zusammenhang zu verlieren – dann bliebe ein zusammenhängender Graph mit \(n-2\) Kanten übrig, was für \(n\) Knoten unmöglich ist (minimum sind \(n-1\)).

Somit sind alle drei Baum-Eigenschaften erfüllt.

Ergebnis: Ja, der Graph ist ein Baum. Begründung: |V| = 6 ∧ |E| = 5 = |V|−1 ∧ zusammenhängend ⇒ kreisfrei ⇒ Baum.

Aufgabe 5: Adjazenzliste aus Adjazenzmatrix erstellen

Aufgabe: Erstelle die Adjazenzliste zum Graphen aus Aufgabe 1 (Adjazenzmatrix mit v1-v4). Erkläre kurz, wann die Adjazenzliste einer Adjazenzmatrix vorzuziehen ist.

Schritt 1: Zeile für Zeile durchgehen

Für jede Zeile \(i\) alle Spalten \(j\) mit \(A_{ij} = 1\) sammeln:

Zeile v1: [0, 1, 1, 0] → Nachbarn v2, v3.
Zeile v2: [1, 0, 1, 1] → Nachbarn v1, v3, v4.
Zeile v3: [1, 1, 0, 1] → Nachbarn v1, v2, v4.
Zeile v4: [0, 1, 1, 0] → Nachbarn v2, v3.

Schritt 2: Adjazenzliste notieren

v1 → [v2, v3]
v2 → [v1, v3, v4]
v3 → [v1, v2, v4]
v4 → [v2, v3]

Schritt 3: Wann ist die Liste besser?

Speicher: Matrix belegt immer \(O(n^2) = 16\) Zellen, die Liste hier nur \(O(|V| + |E|) = 4 + 2 \cdot 5 = 14\) Einträge (Kanten doppelt, da ungerichtet). Bei dünnen Graphen (wenige Kanten pro Knoten) wächst die Liste linear, während die Matrix quadratisch wächst – die Liste ist dann klar effizienter.

Ergebnis: 4 verkettete Listen (v1 → 2, v2 → 3, v3 → 3, v4 → 2 Nachbarn). Adjazenzliste vorzuziehen bei dünnen Graphen und häufiger Nachbar-Iteration.

Aufgabe 6: Warum scheitert Dijkstra bei negativen Kanten?

Aufgabe: Betrachte den gerichteten Graphen mit 3 Knoten S, A, B und Kanten:

S→A: 2, S→B: 5, A→B: −4

Führe Dijkstra Schritt für Schritt aus und zeige, warum das Verfahren bei negativen Kantengewichten kein zuverlässiges Ergebnis mehr liefert.

Schritt 1: Dijkstra am gegebenen Graphen durchspielen

Initialisierung: \(D[S] = 0\), \(D[A] = D[B] = \infty\), \(MK = \{S\}\).

Iteration 1: h = S.

S→A (2): \(D[A] = \min(\infty, 0+2) = 2\), \(R[A] = S\), \(MK \leftarrow MK \cup \{A\}\).
S→B (5): \(D[B] = \min(\infty, 0+5) = 5\), \(R[B] = S\), \(MK \leftarrow MK \cup \{B\}\).

Entferne S. Stand: \(MK = \{A, B\}\), \(D[A] = 2, D[B] = 5\).

Iteration 2: min ist D[A] = 2 ⇒ h = A.

A→B (−4): \(D[B] = \min(5, 2 + (-4)) = 1\), \(R[B] = A\).

Entferne A. Stand: \(MK = \{B\}\), \(D[B] = 1\).

Iteration 3: h = B. Keine ausgehenden Kanten. Entferne B. Ende.

Schritt 2: Warum ist das trotzdem problematisch?

In diesem Mini-Beispiel wird zufällig noch das richtige Ergebnis \(D[B] = 1\) gefunden, weil B nach der Aktualisierung durch A entfernt wurde. Die entscheidende Eigenschaft von Dijkstra lautet aber: „Ein aus MK entfernter Knoten wird nie wieder aktualisiert." Diese Zusicherung basiert auf nicht-negativen Gewichten.

Schritt 3: Klassisches Gegenbeispiel konstruieren

Erweitere den Graphen so, dass Dijkstra einen negativen Umweg zu spät entdeckt: 3 Knoten S, A, B mit Kanten

S→A: 4, S→B: 2, B→A: −3

Ablauf:

Init: \(D[S] = 0, D[A] = D[B] = \infty\), \(MK = \{S\}\).
h = S: \(D[A] = 4, D[B] = 2\). \(MK = \{A, B\}\), S entfernt.
min ist D[B] = 2 ⇒ h = B. Update B→A: \(D[A] = \min(4, 2 + (-3)) = -1\). Ok, funktioniert hier noch.
Entferne B. \(MK = \{A\}\), \(D[A] = -1\). h = A, keine ausgehenden Kanten, Ende.

Bei nur diesen 3 Knoten funktioniert es weiterhin. Der wirkliche Fehler tritt in größeren Graphen auf, in denen A schon abgearbeitet und aus MK entfernt worden wäre, bevor die negative Kante B→A überhaupt betrachtet wird. Dann bleibt \(D[A]\) fälschlich auf dem alten Wert 4 stehen – der optimale Wert −1 wird nie mehr gefunden.

Schritt 4: Fazit

Die Greedy-Auswahl „nimm den kleinsten unfertigen Knoten und markiere ihn als final" ist nur korrekt, solange alle Kantengewichte \(\geq 0\) sind. Bei negativen Kanten muss ein Verfahren verwendet werden, das jede Kante mehrfach relaxieren kann, z. B. Bellman-Ford.

Ergebnis: Dijkstra setzt nicht-negative Kantengewichte voraus. Sobald negative Kanten existieren, ist nicht mehr garantiert, dass ein aus MK entfernter Knoten seinen finalen Wert hat – daher inkorrekte kürzeste Wege möglich. Alternative: Bellman-Ford.

Übungsfragen

1. Was unterscheidet einen gerichteten von einem ungerichteten Graphen?

Bei einem gerichteten Graphen (Digraph) sind die Kanten geordnete Paare \((u,v)\) – eine Kante von \(u\) nach \(v\) impliziert nicht, dass es auch eine Kante von \(v\) nach \(u\) gibt. Man kann sich das als Einbahnstraßen vorstellen. Bei einem ungerichteten Graphen ist die Kante symmetrisch: \(\{u,v\} = \{v,u\}\), also wie eine zweispurige Straße. In der Adjazenzmatrix zeigt sich das: eine ungerichtete Matrix ist symmetrisch (\(A_{ij} = A_{ji}\)), eine gerichtete Matrix im Allgemeinen nicht.

2. Wann ist ein Graph ein Baum?

Ein Graph ist genau dann ein Baum, wenn er zusammenhängend, kreisfrei und ungerichtet ist. Aus diesen drei Eigenschaften folgt automatisch: Ein Baum mit \(n\) Knoten hat genau \(n-1\) Kanten. Weniger Kanten wären nicht mehr zusammenhängend, mehr Kanten würden zwangsläufig einen Kreis erzeugen. Ein Baum ist also die "minimale zusammenhängende Struktur" auf \(n\) Knoten.

3. Wie zeichnet man den Graphen zu einer gegebenen Adjazenzmatrix?

Vorgehen Schritt für Schritt:

Zähle die Zeilen/Spalten der Matrix – das ist die Knotenzahl \(n\). Zeichne \(n\) Knoten mit Beschriftungen (z. B. 1, 2, …, n).
Prüfe zunächst, ob die Matrix symmetrisch ist. Symmetrisch → ungerichteter Graph, sonst gerichtet.
Für jeden Eintrag \(A_{ij} \neq 0\): Zeichne eine Kante von Knoten \(i\) nach Knoten \(j\). Bei einem ungerichteten Graphen nur einmal je Knotenpaar; bei einem gerichteten Graphen mit Pfeilspitze in Richtung \(j\).
Ist \(A_{ij}\) ein Wert > 1, handelt es sich um ein Kantengewicht – trage es an die Kante.

Beispiel: Für \(A_{12}=3\) und \(A_{21}=3\) zeichne eine ungerichtete Kante zwischen Knoten 1 und 2 mit Gewicht 3.

4. Warum verwendet Kruskal die sortierte Kantenliste? Wann stoppt der Algorithmus?

Warum sortiert? Kruskal ist ein Greedy-Verfahren: In jeder Runde wird die aktuell günstigste Kante gewählt, die noch keinen Kreis erzeugt. Nur wenn die Kanten aufsteigend sortiert sind, garantiert die Greedy-Auswahl das globale Optimum. Würde man ungeordnet vorgehen, könnte man teure Kanten aufnehmen und den optimalen Weg verbauen.

Wann stoppt der Algorithmus? Sobald der Spannbaum \(n-1\) Kanten enthält (bei \(n\) Knoten). Weitere Kanten würden zwangsläufig einen Kreis erzeugen und den Baum verlassen. Alternativ: sobald alle Kanten verarbeitet sind (bei einem nicht zusammenhängenden Graphen entsteht dann ein "minimaler Spannwald").

5. Erkläre den Dijkstra-Schritt: Warum wählt man h mit minimalem D[h]?

In jedem Iterationsschritt wählt Dijkstra unter den markierten Knoten \(MK\) denjenigen mit dem kleinsten aktuellen Distanzwert \(D[h]\) aus. Der Grund: Bei nicht-negativen Kantengewichten kann kein späterer Umweg über einen anderen markierten Knoten den Weg zu \(h\) noch verkürzen. Denn jeder Umweg müsste zusätzliche Kanten mit Gewicht \(\geq 0\) durchlaufen und wäre daher mindestens so lang wie \(D[h]\). Damit ist \(D[h]\) final und \(h\) kann als "abgearbeitet" markiert (aus \(MK\) entfernt) werden. Diese Eigenschaft ist die Grundlage für die Korrektheit des Algorithmus.

6. Warum funktioniert Dijkstra nicht bei negativen Kantengewichten?

Die Kernannahme von Dijkstra – "der Knoten mit minimalem \(D[h]\) ist final" – bricht bei negativen Kantengewichten zusammen. Beispiel: Angenommen, wir haben Knoten S, A, B mit Kanten S→A (Gewicht 2), S→B (Gewicht 4), A→B (Gewicht −3).

Nach der Initialisierung: \(D[S]=0, D[A]=\infty, D[B]=\infty\).
Wähle S: aktualisiere \(D[A]=2, D[B]=4\). Entferne S.
Wähle A (min): \(D[B]\) wird zu \(2 + (-3) = -1\). Entferne A.
Aber: B war zwischenzeitlich auch schon einmal mit \(D[B]=4\) gehandelt worden. Dijkstra prüft das nicht neu – bei einem größeren Graphen, in dem B vor A endgültig gewählt worden wäre, hätte man einen falschen finalen Wert.

Für negative Gewichte verwendet man daher Bellman-Ford (funktioniert solange kein negativer Kreis existiert).

7. Zeichne die Adjazenzliste zu einer gegebenen Adjazenzmatrix.

Vorgehen: Für jede Zeile \(i\) der Matrix eine Liste anlegen, die alle Spalten \(j\) mit \(A_{ij} \neq 0\) enthält.

Beispiel-Matrix (ungewichtet):

A = [[0, 1, 1, 0],
     [1, 0, 0, 1],
     [1, 0, 0, 1],
     [0, 1, 1, 0]]

Adjazenzliste:

1 → [2, 3]
2 → [1, 4]
3 → [1, 4]
4 → [2, 3]

Bei gewichteten Graphen speichert man Tupel \((j, c(i,j))\), z. B. 1 → [(2, 3), (3, 5)].

8. Was ist die Bedeutung von R[i] im Dijkstra-Algorithmus?

\(R[i]\) speichert den direkten Vorgänger von Knoten \(i\) auf dem kürzesten Weg vom Startknoten \(S\) aus. Während \(D[i]\) nur die Länge des kürzesten Weges angibt, ermöglicht \(R[i]\) die Rekonstruktion des tatsächlichen Pfades: Startend bei einem Zielknoten \(z\) verfolgt man \(z \to R[z] \to R[R[z]] \to \dots \to S\). Ohne \(R[i]\) wüsste man nur, wie lang der kürzeste Weg ist, nicht aber, über welche Zwischenknoten er verläuft.

9. Warum ist die Voraussetzung "zusammenhängend" für einen Spannbaum wichtig?

Ein Spannbaum muss alle Knoten des Graphen enthalten und sie miteinander verbinden. Ist der ursprüngliche Graph nicht zusammenhängend, existiert kein einzelner Spannbaum – man kann höchstens einen Spannwald (mehrere disjunkte Bäume, einer je Zusammenhangskomponente) bilden. Kruskal würde in diesem Fall nach dem letzten Durchlauf weniger als \(n-1\) Kanten aufgenommen haben.

10. Angenommen, Kruskal betrachtet als nächste Kante (u,v). Wie prüft man, ob dadurch ein Kreis entstünde?

Ein Kreis entsteht genau dann, wenn \(u\) und \(v\) bereits über die bisher aufgenommenen Kanten miteinander verbunden sind – d. h. wenn sie zur selben Zusammenhangskomponente des aktuellen Spannbaum-Zwischenergebnisses gehören. Praktische Prüfung: Startend bei \(u\) einer Kantenfolge folgen und schauen, ob man \(v\) erreicht. Effizienter: Union-Find-Datenstruktur, die zu jedem Knoten die Komponenten-ID speichert. Sind die IDs gleich → Kreis, verwerfe. Sonst → Kanten aufnehmen und Komponenten vereinigen.

11. Kruskal auf einem Graphen ausführen: Was passiert, wenn zwei Kanten das gleiche Gewicht haben?

Bei gleich schweren Kanten ist die Reihenfolge beliebig – man kann eine der beiden Kanten zuerst aufnehmen. Konsequenz: Der minimale Spannbaum ist nicht immer eindeutig. Verschiedene Reihenfolgen können zu unterschiedlichen Spannbäumen führen, aber alle haben die gleiche minimale Gesamtsumme der Kantengewichte. In einer Klausur-Aufgabe reicht es also, einen möglichen Spannbaum zu zeigen und die Gewichtssumme korrekt anzugeben.

12. Was passiert im Dijkstra-Algorithmus, wenn ein Knoten unerreichbar ist?

Ein Knoten \(i\) ist unerreichbar vom Startknoten \(S\), wenn keine Kantenfolge von \(S\) zu \(i\) existiert. Sein Distanzwert bleibt am Ende \(D[i] = \infty\) und \(R[i]\) bleibt undefiniert. Der Algorithmus terminiert trotzdem regulär, sobald \(MK\) leer ist – nur werden solche Knoten nie zu \(MK\) hinzugefügt oder verbessert. Interpretation: "Es gibt keinen Weg von \(S\) zu \(i\)."

13. Was ist der Unterschied zwischen "minimaler Spannbaum" und "kürzester Weg"?

Zwei fundamental unterschiedliche Probleme:

Minimaler Spannbaum (Kruskal): Wähle die günstigste Menge an Kanten, um alle Knoten zu verbinden. Es geht um die Struktur des gesamten Netzwerks.
Kürzester Weg (Dijkstra): Finde den günstigsten Pfad von einem Startknoten zu allen anderen. Es geht um die optimalen Einzelverbindungen, nicht um das Gesamtnetzwerk.

Beispiel: In einem Straßennetz ist der MST das Baumnetz mit minimalen Baukosten aller Straßen. Der kürzeste Weg ist die schnellste Route für einen einzelnen Autofahrer von A nach B – diese Route ist im MST oft nicht enthalten, weil der MST womöglich Umwege macht, um Baukosten zu sparen.

14. Wie interpretiert man ein D[i] = ∞ am Ende von Dijkstra?

\(D[i] = \infty\) bedeutet, dass der Algorithmus keinen Weg von \(S\) zu \(i\) finden konnte. Zwei mögliche Ursachen: (a) Der Graph ist nicht zusammenhängend – \(i\) liegt in einer anderen Zusammenhangskomponente. (b) Bei gerichteten Graphen: Alle Wege zu \(i\) laufen entgegen der Kantenrichtung, d. h. \(i\) ist von \(S\) aus nicht erreichbar. Konsequenz für die Anwendung: In einem Routenplaner heißt es "keine Route möglich", in einem Netzwerk "kein Signalweg vorhanden".