Title: ADM26 / Graphen
Tags: DiskreteMathematik::Kapitel2

Hamilton'sche Linie

Kriterium für Hamilton'sche Linie

Q: Was ist ein Kantenzug in einem ungerichteten Graphen?
A: Antwort:
Ein Kantenzug ist eine Folge von Knoten \(v_1, v_2, \dotsc, v_k\),
sodass jedes Paar \((v_i, v_{i+1}) \in E\) ist (also eine Kante zwischen aufeinanderfolgenden Knoten existiert).
Länge: \(k-1\) (Anzahl der Kanten)
Beispiel:
v1 — v2 — v3 — v2 — v4
   ↑     ← Wiederholung erlaubt

Q: Was ist ein Pfad in einem ungerichteten Graphen?
A: Antwort:
Ein Pfad (auch: Weg) ist ein Kantenzug, bei dem kein Knoten mehrfach vorkommt.
\[\forall i \neq j: \quad v_i \neq v_j\]
Beispiel:
v1 — v2 — v3 — v4   ✔ Pfad
v1 — v2 — v3 — v2   ✘ kein Pfad (v2 doppelt)

Q: Was ist das Ziel des Dijkstra-Algorithmus?
A: Ziel:
Bestimme kürzeste Pfade von einem Startknoten \( s \) zu allen anderen Knoten in einem gerichteten Graphen mit nicht-negativen Kantengewichten.
Eingabe:
- Gewichteter, gerichteter Graph \( G = (V, E) \)
- Kantengewichte \( \ell_e \geq 0 \) für alle \( e \in E \)
- Startknoten \( s \in V \)
Ausgabe:
Für jeden Knoten \( v \in V \): die Länge \( d(v) \) des kürzesten \( s \)-\( v \)-Pfads.

Q: Was ist das Ziel der Algorithmen Kruskal und Prim?
A: Antwort:
Beide Algorithmen lösen das Minimum Spanning Tree (MST)-Problem:
Finde eine Teilmenge der Kanten \( T \subseteq E \), die:
- alle Knoten \( V \) verbindet
- keine Zyklen enthält
- und das Gesamtgewicht \( \sum_{e \in T} c_e \) minimiert
Das Ergebnis ist ein minimaler Spannbaum.

Q: Was ist ein Graph?
A: Antwort:
Ein Graph ist ein Paar \[G = (V, E)\] bestehend aus
- einer Knotenmenge \(V\)
- einer Kantenmenge \(E\)
Je nach Typ gilt:
- ungerichtet: \(E \subseteq \{\{u,v\} \mid u,v \in V\}\)
- gerichtet: \(E \subseteq V \times V\)
Interpretation:
Knoten sind Objekte, Kanten beschreiben Beziehungen zwischen ihnen.

Q: Was ist der Knotengrad eines Knotens?
A: Antwort:
Der Knotengrad eines Knotens \(v\) ist die Anzahl seiner Nachbarn: \[d(v) = |\Gamma(v)|\] Merksatz:
Der Grad zählt, wie viele Kanten an einem Knoten „anhängen“.

Q: Was sind Vorgänger, Nachfolger, Hin- und Weggrad in einem gerichteten Graphen?
A: Antwort:
Nachfolger: \[\Gamma^+(v) = \{w \in V(G) \mid (v,w) \in E(G)\}\] Vorgänger: \[\Gamma^-(v) = \{w \in V(G) \mid (w,v) \in E(G)\}\] Weggrad: \[d^+(v) = |\Gamma^+(v)|\] Hingrad: \[d^-(v) = |\Gamma^-(v)|\]

Q: Was besagt das Handschlaglemma?
A: Antwort:
In einem schlichten ungerichteten Graphen gilt: \[\sum_{v \in V(G)} d(v) = 2|E(G)|\] Begründung:
Jede Kante trägt genau 1 zum Grad von zwei Knoten bei und wird daher insgesamt zweimal gezählt. Erklärungssatz (intuitiv):
Zählt man alle Knotengrade zusammen, so zählt man jede Kante genau zweimal – einmal an jedem ihrer beiden Endknoten. Gerichteter Fall:
\[\sum_{v \in V(G)} d^+(v) = \sum_{v \in V(G)} d^-(v) = |E(G)|\] Merksatz:
Ungerichtet: jede Kante → zweimal gezählt.
Gerichtet: jede Kante → einmal als Hin-, einmal als Wegkante.

Q: Was ist ein Teilgraph und ein induzierter Teilgraph?
A: Antwort:
Ein Graph \(G'=(V',E')\) heißt Teilgraph von \(G=(V,E)\), wenn \[V' \subseteq V,\quad E' \subseteq E\] Ein induzierter Teilgraph entsteht, wenn
- \(V'\) vorgegeben ist
- \(E'\) alle Kanten aus \(E\) enthält, deren Endknoten in \(V'\) liegen

Q: Was ist eine Kantenfolge, ein Weg, ein Kreis und ein Zyklus?
A: Antwort:
Eine Kantenfolge ist eine Folge \[e_1, e_2, \dots, e_k\] mit passenden Anfangs- und Endknoten.
Weg: Knoten sind paarweise verschieden.
Geschlossene Kantenfolge: Anfangs- und Endknoten gleich.
Kreis (ungerichtet): geschlossener Weg ohne Mehrfachkanten.
Zyklus (gerichtet): geschlossene Kantenfolge mit verschiedenen Knoten.

Q: Wann heißt ein ungerichteter Graph zusammenhängend?
A: Ein ungerichteter Graph heißt zusammenhängend, wenn zwischen je zwei Knoten ein Weg existiert. Die maximalen zusammenhängenden Teilgraphen heißen Zusammenhangskomponenten.

Q: Wann heißt ein Graph zusammenhängend?
A: Antwort (ungerichteter Graph):
Ein ungerichteter Graph \( G = (V,E) \) heißt zusammenhängend, wenn für alle \[v,w \in V(G)\] eine Kantenfolge (ein Weg) von \(v\) nach \(w\) existiert, d.h. es gibt eine Folge \[e_1, e_2, \dots, e_k \in E(G)\] die \(v\) mit \(w\) verbindet. Notation (Buch):
Man sagt: \(w\) ist von \(v\) erreichbar.

Q: Was sind Zusammenhangskomponenten eines ungerichteten Graphen?
A: Antwort:
Die Zusammenhangskomponenten eines ungerichteten Graphen \(G\) sind die maximalen zusammenhängenden Teilgraphen von \(G\).

Q: Wann ist ein ungerichteter Graph zusammenhängend?
A: Antwort:
Ein ungerichteter Graph ist genau dann zusammenhängend, wenn er genau eine Zusammenhangskomponente besitzt.

Q: Was ist eine Kantenfolge in einem ungerichteten Graphen?
A: Antwort:
Eine Kantenfolge ist eine Folge von Kanten \[e_1, e_2, \dots, e_k\] bei der aufeinanderfolgende Kanten jeweils einen gemeinsamen Knoten besitzen.

Q: Was ist ein Weg in einem ungerichteten Graphen?
A: Antwort:
Ein Weg ist eine Kantenfolge, in der alle durchlaufenen Knoten paarweise verschieden sind.

Q: Welche Struktur genügt zur Definition des Zusammenhangs in einem ungerichteten Graphen?
A: Antwort:
Für den Zusammenhang genügt bereits die Existenz einer Kantenfolge zwischen zwei Knoten; ein Weg ist nicht erforderlich.

Q: Wann heißt ein gerichteter Graph stark zusammenhängend?
A: Antwort:
Ein gerichteter Graph heißt stark zusammenhängend, wenn für alle \[v,w \in V(G)\] eine gerichtete Kantenfolge (eine Bahn) von \(v\) nach \(w\) existiert.

Q: Wann heißt ein gerichteter Graph schwach zusammenhängend?
A: Antwort:
Ein gerichteter Graph heißt schwach zusammenhängend, wenn der zugrunde liegende ungerichtete Graph zusammenhängend ist.

Q: Was ist eine Bahn in einem gerichteten Graphen?
A: Antwort:
Eine Bahn ist eine Kantenfolge in einem gerichteten Graphen, bei der die Richtungen aller Kanten eingehalten werden.

Q: Wie unterscheidet sich Zusammenhang in ungerichteten und gerichteten Graphen?
A: Antwort:
Ungerichtet: Zusammenhang ⇔ zwischen allen Knoten existiert ein Weg.
Gerichtet: stark ⇔ gerichtete Bahnen in beide Richtungen,
schwach ⇔ Zusammenhang ohne Beachtung der Kantenrichtungen.

Q: Was ist ein Baum und ein Wald?
A: Antwort:
Ein Wald ist ein schlichter ungerichteter Graph ohne Kreise.
Ein Baum ist ein zusammenhängender Wald. Eigenschaft:
Zwischen zwei Knoten im Baum gibt es genau einen Weg.

Q: Welche Beziehung gilt zwischen Knoten und Kanten in einem Baum?
A: Antwort:
Für einen Baum \(T\) gilt: \[\alpha_0(T) = \alpha_1(T) + 1\] Erklärung der Variablen:
- \(T\): ein Baum, also ein zusammenhängender, kreisfreier ungerichteter Graph
- \(\alpha_0(T)\): Anzahl der Knoten von \(T\)
- \(\alpha_1(T)\): Anzahl der Kanten von \(T\)
Bedeutung:
Ein Baum besitzt immer genau eine Kante weniger als Knoten.
Erweiterung auf Wälder:
Für einen Wald \(W\) mit \(k\) Zusammenhangskomponenten gilt: \[\alpha_0(W) = \alpha_1(W) + k\] Erklärung der zusätzlichen Variable:
- \(W\): ein Wald, also ein kreisfreier ungerichteter Graph
- \(k\): Anzahl der Zusammenhangskomponenten von \(W\) (jede Komponente ist ein Baum)
Merksatz (prüfungstauglich):
Jede Zusammenhangskomponente erhöht die Knotenzahl gegenüber der Kantenzahl um genau 1.

Q: Wann besitzt ein Graph eine Euler’sche Linie?
A: Antwort:
Ein ungerichteter Graph besitzt
- eine geschlossene Euler-Linie ⇔ zusammenhängend und alle Grade gerade
- eine offene Euler-Linie ⇔ genau zwei Knoten ungeraden Grad

Q: Was ist eine Euler’sche Linie?
A: Antwort:
Eine Euler’sche Linie ist eine Kantenfolge in einem Graphen, die
- jede Kante des Graphen
- genau einmal
enthält. Unterscheidung:
- geschlossen: Anfangs- und Endknoten sind gleich (Euler-Kreis)
- offen: Anfangs- und Endknoten sind verschieden
Hinweis:
Knoten dürfen mehrfach besucht werden, Kanten jedoch nicht.

Q: Was ist eine Hamilton’sche Linie?
A: Antwort:
Eine Hamilton’sche Linie ist eine Kantenfolge, die jeden Knoten genau einmal enthält. Unterschied zu Euler:
Euler: alle Kanten genau einmal
Hamilton: alle Knoten genau einmal

Q: Wann heißt ein Graph planar?
A: Antwort:
Ein Graph heißt planar, wenn er kreuzungsfrei in der Ebene dargestellt werden kann.

Q: Was besagt die Euler’sche Polyederformel?
A: Antwort:
Für einen zusammenhängenden planaren Graphen \(G\) gilt: \[\alpha_0(G) - \alpha_1(G) + \alpha_2(G) = 2\] Erklärung der Größen:
- \(\alpha_0(G)\): Anzahl der Knoten des Graphen
- \(\alpha_1(G)\): Anzahl der Kanten des Graphen
- \(\alpha_2(G)\): Anzahl der Gebiete (Flächen) der planaren Zeichnung, inklusive des Außengebiets
Anschauliche Erklärung:
Zeichnet man einen zusammenhängenden Graphen kreuzungsfrei in der Ebene, so zerlegen die Kanten die Ebene in mehrere Gebiete. Die Euler’sche Polyederformel sagt aus, dass sich aus der Anzahl von Knoten und Kanten die Anzahl der entstehenden Gebiete eindeutig ergibt. Warum steht dort die 2?
Die Zahl 2 entspricht der Euler-Charakteristik der Ebene. Unabhängig davon, wie komplex der zusammenhängende planare Graph ist, bleibt der Wert \[\alpha_0 - \alpha_1 + \alpha_2\] immer konstant gleich 2. Wichtiger Hinweis (Prüfung):
Die Formel gilt nur für
- planare Graphen
- zusammenhängende Graphen
- eine feste planare Einbettung

Q: Wann ist ein Graph nicht planar?
A: Antwort:
Ein Graph ist genau dann nicht planar, wenn er einen Teilgraphen enthält, der aus
- \(K_5\) oder
- \(K_{3,3}\)
durch Unterteilung entsteht.

Q: Was ist die Aufgabe des Kruskal-Algorithmus?
A: Antwort:
Der Kruskal-Algorithmus berechnet ein minimales Gerüst (einen minimalen spannenden Baum) eines bewerteten, schlichten, ungerichteten, zusammenhängenden Graphen. Ziel:
Alle Knoten verbinden, ohne Kreise zu erzeugen, sodass die Summe der Kantengewichte minimal ist.

Q: Was ist die Grundidee des Kruskal-Algorithmus?
A: Antwort:
Man wählt die Kanten der Reihe nach nach steigendem Gewicht und fügt sie genau dann hinzu, wenn dadurch kein Kreis entsteht. Intuition:
„Nimm immer die billigste verfügbare Kante, solange sie nichts kaputt macht.“

Q: Wie funktioniert der Kruskal-Algorithmus Schritt für Schritt?
A: Antwort:
1. Sortiere alle Kanten nach aufsteigendem Gewicht.
2. Starte mit leerer Kantenmenge \(E' := \emptyset\).
3. Gehe die Kanten der Reihe nach durch:
   – Füge eine Kante hinzu, falls kein Kreis entsteht.
4. Stoppe, sobald \[|E'| = |V| - 1\] gilt. Dann ist \(W = (V, E')\) ein minimales Gerüst.

Q: Wie läuft Kruskal an einem einfachen Beispiel ab?
A: Antwort:
Gegeben sei ein Graph mit Kantengewichten:
A --1-- B
|       |
4       2
|       |
C --3-- D
Sortierte Kanten:
(A,B):1
(B,D):2
(C,D):3
(A,C):4
Auswahl:
- (A,B) ✔
- (B,D) ✔
- (C,D) ✔
Ergebnis:
Minimales Gerüst mit Gewicht \(1+2+3=6\).

Q: Was ist die Aufgabe des Dijkstra-Algorithmus?
A: Antwort:
Der Dijkstra-Algorithmus berechnet in einem bewerteten Netzwerk mit nichtnegativen Kantengewichten die kürzesten Wege von einem Startknoten \(v_0\) zu allen erreichbaren Knoten.

Q: Was ist die Grundidee des Dijkstra-Algorithmus?
A: Antwort:
Man baut die kürzesten Distanzen schrittweise von innen nach außen auf:
- Beginne beim Startknoten
- Fixiere immer den aktuell nächstgelegenen Knoten
- Verbessere von dort aus die Distanzen der Nachbarn
Merksatz:
„Der nächste sicher richtige Knoten wird fixiert.“

Q: Wie funktioniert der Dijkstra-Algorithmus Schritt für Schritt?
A: Antwort:
1. Initialisiere: \[l(v_0)=0,\quad l(v)=\infty\ (v\neq v_0),\quad U=\emptyset\] 2. Wähle einen Knoten \(u\) mit minimalem \(l(u)\) außerhalb von \(U\).
3. Füge \(u\) zu \(U\) hinzu.
4. Aktualisiere für alle Nachbarn \(v\): \[l(v) := \min(l(v),\, l(u)+w(u,v))\] 5. Wiederhole, bis keine Knoten mehr erreichbar sind.

Q: Wie sieht Dijkstra tabellarisch aus?
A: Antwort:
Beispiel Startknoten \(v_0\):
Schritt | fixiert | l(v1) l(v2) l(v3)
-----------------------------------
0       | v0      | 2     5     ∞
1       | v1      | 2     4     6
2       | v2      | 2     4     5
3       | v3      | 2     4     5
Ergebnis:
Die finalen \(l(v)\) sind die kürzesten Distanzen von \(v_0\).