Graphen und Bäume: die Struktur, auf der Suche und neuronale Netze stehen

Sei V eine endliche nichtleere Menge; ihre Elemente nennen wir Knoten.

1. Ein ungerichteter Graph ist ein Paar G = (V, E), wobei E ⊆ {{u, v} : u, v ∈ V, u ≠ v}; die Elemente von E sind die Kanten — zweielementige Teilmengen von V. Die Knoten u, v sind benachbart genau dann, wenn {u, v} ∈ E.
2. Ein gerichteter Graph ist ein Paar G = (V, E), wobei E ⊆ V × V; eine Kante ist ein geordnetes Paar (u, v) — ein Pfeil von u nach v. Ein gerichteter Graph ist also eine Relation auf V (siehe den Teil Mengen und Relationen).
3. Ein gewichteter Graph ist ein Tripel G = (V, E, w), wobei (V, E) ein Graph nach 1. oder 2. ist und w : E → ℝ eine Funktion, die jeder Kante e ∈ E ein Gewicht w(e) zuordnet (Länge, Kosten, Zeit).

Sofern nicht anders gesagt, ist ein Graph in diesem Teil ungerichtet.

Sei G = (V, E) ein ungerichteter Graph und v ∈ V. Der Grad des Knotens v ist die Anzahl der Kanten, die ihn enthalten (die von ihm ausgehen):

deg(v) = |{e ∈ E : v ∈ e}|.

Satz (Handschlaglemma). Sei G = (V, E) ein ungerichteter Graph. Dann gilt

∑_{v ∈ V} deg(v) = 2 |E|.

Insbesondere ist die Summe der Grade in jedem ungerichteten Graphen eine gerade Zahl.

Satz. Sei G = (V, E) ein ungerichteter Graph und L = {v ∈ V : deg(v) ist ungerade} die Menge seiner Knoten mit ungeradem Grad. Dann ist |L| eine gerade Zahl.

Beweis. Wir teilen die Summe der Grade in Knoten mit geradem und mit ungeradem Grad auf: ∑_{v ∈ V} deg(v) = ∑_{v ∈ V ∖ L} deg(v) + ∑_{v ∈ L} deg(v). Die linke Seite ist nach dem Handschlaglemma 2|E|, also gerade; die erste Summe rechts ist eine Summe gerader Zahlen, also gerade. Daher muss auch die zweite gerade sein — und eine Summe von |L| ungeraden Zahlen ist genau dann gerade, wenn |L| gerade ist. ∎

Deshalb lässt sich kein Graph mit fünf Knoten zeichnen, von denen jeder den Grad 3 hat: Die Summe 15 wäre ungerade.

Sei G = (V, E, w) ein gewichteter ungerichteter Graph mit von null verschiedenen Gewichten (w(e) ≠ 0 für alle e ∈ E) und n = |V| Knoten, die wir durchnummerieren: V = {v₁, …, v_n}. Die Adjazenzmatrix von G ist die quadratische Matrix A ∈ ℝ^n×n mit den Einträgen (für i, j = 1, …, n)

A_ij = w({v_i, v_j}), falls {v_i, v_j} ∈ E;   sonst A_ij = 0.

Die von null verschiedenen Gewichte braucht man, damit sich eine Kante von einer fehlenden Kante unterscheiden lässt. Bei einem ungewichteten Graphen schreibt man statt des Gewichts 1. Weil {v_i, v_j} = {v_j, v_i}, hat ein ungerichteter Graph A_ij = A_ji, also A = A^T.

Für v ∈ V bezeichne N(v) die Menge seiner Nachbarn:

N(v) = {u ∈ V : {u, v} ∈ E}.

Die Adjazenzliste ist die Abbildung, die jedem Knoten v ∈ V die Menge N(v) zuordnet, bei einem gewichteten Graphen samt Gewichten: {(u, w({u, v})) : u ∈ N(v)}. Es gilt |N(v)| = deg(v).

Städtegraph: Die Matrix hat 7 · 7 = 49 Zellen, davon nur 24 von null verschieden (jede Straße zweimal, ober- und unterhalb der Diagonale). Die Adjazenzlisten haben zusammen ∑ deg(v) = 2 · 12 = 24 Einträge (Farben nach dem Handschlaglemma oben). Die Zeile B der Matrix ist (4, 0, 5, 3, 7, 0, 0) — vier von null verschiedene Zahlen, weil deg(B) = 4.

Ein Straßennetz mit einer Million Kreuzungen, von jeder gehen im Schnitt 3 Straßen aus: |E| = 10⁶ · 3/2 = 1,5 · 10⁶. Die Matrix hat (10⁶)² = 10¹² Zellen, die Listen nur 2 · 1,5 · 10⁶ = 3 · 10⁶ Einträge — über dreihunderttausendmal weniger.

Sei G = (V, E) ein ungerichteter Graph und u, v ∈ V.

1. Ein Weg von u nach v ist eine Folge von Knoten (v₀, v₁, …, v_k), k ≥ 0, sodass v₀ = u,   v_k = v,   v_i ≠ v_j für i ≠ j,   {v_i−1, v_i} ∈ E für i = 1, …, k. Seine Länge ist k (die Anzahl der Kanten); in einem gewichteten Graphen (V, E, w) ist es die Summe der Gewichte ∑_i=1^k w({v_i−1, v_i}).
2. Ein Kreis ist eine Folge von Knoten (v₀, v₁, …, v_k) mit k ≥ 3, in der v₀, …, v_k−1 paarweise verschieden sind, v_k = v₀ und {v_i−1, v_i} ∈ E für i = 1, …, k — ein Weg, der nach mindestens drei Kanten zu seinem Startknoten zurückkehrt.
3. G ist zusammenhängend genau dann, wenn ∀u, v ∈ V existiert ein Weg von u nach v.
4. Wir definieren die Relation ∼ auf V: u ∼ v genau dann, wenn ein Weg von u nach v existiert. Sie ist eine Äquivalenz (reflexiv dank des Weges der Länge 0, symmetrisch durch Umkehren des Weges, transitiv, weil sich aus der Verkettung zweier Wege ein Weg auswählen lässt). Ihre Äquivalenzklassen sind die Zusammenhangskomponenten von G; sie bilden also eine Zerlegung von V (siehe den Teil Mengen und Relationen).

Ein Graph ist also genau dann zusammenhängend, wenn er eine einzige Zusammenhangskomponente hat.

Sei G = (V, E, w) ein gewichteter ungerichteter Graph mit nichtnegativen Gewichten, w : E → [0, ∞), und u, v ∈ V. Für einen Weg π bezeichne w(π) = ∑_{e ∈ π} w(e) seine Länge (die Summe der Gewichte seiner Kanten). Der Abstand der Knoten u und v ist

d(u, v) = min {w(π) : π ist ein Weg von u nach v},   falls mindestens ein solcher Weg existiert; sonst d(u, v) = ∞.

Das Minimum existiert, weil es in einem endlichen Graphen nur endlich viele Wege gibt. Für einen ungewichteten Graphen nehmen wir w(e) = 1 für alle e ∈ E; der Abstand ist dann die kleinste Anzahl von Kanten eines Weges von u nach v.

Satz. Sei G = (V, E, w) ein gewichteter Graph mit nichtnegativen Gewichten, w : E → [0, ∞), start ∈ V der Startknoten und d[·] die Schätzungen des Dijkstra-Algorithmus, gestartet von start (Beschreibung oben). Dann gilt für jeden Knoten u in dem Moment, in dem der Algorithmus ihn abschließt,

d[u] = d(start, u).

Warum: Jeder andere Weg nach u muss die Menge der abgeschlossenen Knoten irgendwo zum ersten Mal verlassen, und zwar über einen Knoten x, dessen Schätzung ≥ d[u] ist (sonst hätten wir x gewählt, nicht u). Der Rest des Weges von x nach u hat eine nichtnegative Länge, also ist der ganze Weg nicht kürzer als d[u]. ∎

Mit einer negativen Kante fällt diese Überlegung — „der Rest des Weges“ könnte die Länge verkürzen. Für negative Gewichte braucht man daher einen anderen Algorithmus (Bellman–Ford).

Sei G = (V, E) ein ungerichteter Graph.

1. G ist ein Wald genau dann, wenn er keinen Kreis enthält (jede seiner Zusammenhangskomponenten ist dann ein Baum).
2. G ist ein Baum genau dann, wenn er zusammenhängend ist und keinen Kreis enthält.

Satz. Sei G = (V, E) ein ungerichteter Graph mit n = |V| ≥ 1 Knoten. Dann sind die folgenden Aussagen äquivalent:

1. G ist ein Baum;
2. G ist zusammenhängend und |E| = n − 1;
3. G enthält keinen Kreis und |E| = n − 1;
4. ∀u, v ∈ V gibt es genau einen Weg von u nach v.

Ein Wurzelbaum ist ein Paar (T, r), wobei T = (V, E) ein Baum und r ∈ V ein ausgezeichneter Knoten ist, die Wurzel. Für v ∈ V:

1. die Tiefe h(v) ist die Länge (Anzahl der Kanten) des einzigen Weges von r nach v; insbesondere h(r) = 0;
2. die Kinder des Knotens v sind seine Nachbarn in Richtung weg von der Wurzel, d. h. die Knoten der Menge {u ∈ N(v) : h(u) = h(v) + 1}; v ist ihr Elternknoten;
3. v ist ein Blatt genau dann, wenn er keine Kinder hat.

Satz. Sei T = (V, E) ein Baum mit n = |V| ≥ 1 Knoten. Dann ist |E| = n − 1.

Lemma: Sei T ein Baum mit mindestens zwei Knoten. Dann hat T ein Blatt, d. h. einen Knoten vom Grad 1. Beweis des Lemmas: Wir nehmen einen längsten Weg im Baum; sein Endknoten kann keinen weiteren Nachbarn außerhalb des Weges haben (der Weg ließe sich verlängern) und auch keinen auf dem Weg (es entstünde ein Kreis) — er hat also den Grad 1.

Beweis des Satzes durch Induktion nach n. Induktionsanfang: Ein Baum mit 1 Knoten hat 0 Kanten. Induktionsschritt: In einem Baum mit n + 1 Knoten entfernen wir ein Blatt samt seiner einzigen Kante. Der Rest ist weiterhin zusammenhängend und ohne Kreise, also ein Baum mit n Knoten, und hat nach Induktionsvoraussetzung n − 1 Kanten. Der ursprüngliche Baum hatte eine mehr, n. ∎

Sei G = (V, E, w) ein zusammenhängender gewichteter ungerichteter Graph.

1. Ein Spannbaum von G ist ein Graph T = (V, F) mit F ⊆ E, der ein Baum ist — er enthält alle Knoten von G und nur einige seiner Kanten.
2. Das Gewicht des Spannbaums ist w(T) = ∑_{e ∈ F} w(e).
3. Ein Spannbaum T ist minimal genau dann, wenn w(T) ≤ w(T′) für jeden Spannbaum T′ von G.

Kruskal-Algorithmus.

• Eingabe: ein zusammenhängender gewichteter ungerichteter Graph G = (V, E, w) mit m = |E| Kanten.
• Ausgabe: eine Kantenmenge F ⊆ E, sodass (V, F) ein minimaler Spannbaum von G ist.

1. Sortiere die Kanten aufsteigend nach Gewicht: e₁, …, e_m mit w(e₁) ≤ … ≤ w(e_m).
2. Setze F := ∅.
3. Für i = 1, …, m: Enthält der Graph (V, F ∪ {e_i}) keinen Kreis, setze F := F ∪ {e_i}; sonst lass die Kante e_i aus.
4. Gib F zurück.

Abbruch: Der Algorithmus endet, nachdem er alle m Kanten durchgegangen ist (er darf früher enden, sobald |F| = |V| − 1). Es ist ein gieriger Algorithmus — in jedem Schritt nimmt er die leichteste zulässige Kante und ändert eine Entscheidung nie mehr — und trotzdem findet er immer einen minimalen Spannbaum (Satz unten).

Die Kanten nach Länge sortiert (angenommene fett): A–C (2), D–E (2), B–D (3), E–G (3), A–B (4), D–F (4), B–C (5), F–G (5), C–D (6), E–F (6), B–E (7), C–F (8).

Die ersten sechs Kanten werden angenommen: A–C und D–E verbinden Paare, B–D fügt B zu D–E hinzu, E–G fügt G hinzu, und A–B verbindet die Gruppe {A, C} mit der Gruppe {B, D, E, G}. D–F schließt den letzten Knoten F an. Jetzt liegen alle Knoten in einer Komponente, also würde jede weitere Kante zwei Knoten derselben Komponente verbinden — sie würde einen Kreis schließen, und der Algorithmus lehnt sie ab.

Länge des Spannbaums: 2 + 2 + 3 + 3 + 4 + 4 = 18.

Sei G = (V, E, w) ein zusammenhängender gewichteter ungerichteter Graph. Ein Schnitt ist eine Aufteilung der Knoten in zwei nichtleere Teile S und V ∖ S, wobei ∅ ≠ S ⊊ V. Eine Kante {u, v} ∈ E kreuzt den Schnitt genau dann, wenn |{u, v} ∩ S| = 1 (ein Ende in S, das andere außerhalb).

Satz. Sei (S, V ∖ S) ein Schnitt von G und e eine Kante, die den Schnitt kreuzt und unter allen Kanten, die diesen Schnitt kreuzen, das kleinste Gewicht hat. Dann gibt es einen minimalen Spannbaum von G, der die Kante e enthält.

Beweis: Nehmen wir einen beliebigen minimalen Spannbaum T; enthält er e, sind wir fertig. Andernfalls betrachten wir T ohne e. Durch Hinzufügen von e entsteht ein Kreis, und der muss den Schnitt noch ein weiteres Mal kreuzen, über eine Kante f. Durch Entfernen von f erhalten wir wieder einen Spannbaum, mit dem Gewicht w(T) + w(e) − w(f) ≤ w(T), weil w(e) ≤ w(f). Er ist also ebenfalls minimal und enthält e. ∎

Kruskal nimmt eine Kante nur dann an, wenn sie zwei verschiedene Komponenten verbindet — und sie ist die leichteste Kante über den Schnitt „eine dieser Komponenten gegen den Rest“, weil er alle leichteren schon verarbeitet hat.

Sei G = (V, E) ein gerichteter Graph, E ⊆ V × V, mit n = |V| Knoten.

1. Ein gerichteter Kreis ist eine Folge von Knoten (v₀, v₁, …, v_k), k ≥ 1, sodass (v_i−1, v_i) ∈ E für i = 1, …, k und v_k = v₀ — entlang der Pfeile kommt man zum Startknoten zurück.
2. G ist ein gerichteter azyklischer Graph (DAG) genau dann, wenn er keinen gerichteten Kreis enthält.
3. Eine topologische Sortierung von G ist eine Bijektion π : V → {1, …, n} (eine Reihenfolge der Knoten), sodass ∀(u, v) ∈ E : π(u) < π(v), d. h. jede Kante führt von links nach rechts — u steht in der Reihenfolge vor v.

Satz. Sei G = (V, E) ein gerichteter Graph. Dann hat G genau dann eine topologische Sortierung, wenn er azyklisch ist.

Eingaben x = 2, w = 0,5, b = −1, richtige Antwort y = 1, Verlust L = (ŷ − y)², σ(z) = 1/1 + e^−z.

Vorwärts (in topologischer Reihenfolge): w · x = 1; z = 1 + (−1) = 0; ŷ = σ(0) = 0,5; L = (0,5 − 1)² = 0,25.

Rückwärts (in umgekehrter Reihenfolge; Farben nach der Aufschlüsselung der Kettenregel unten): ∂L/∂ŷ = 2(ŷ − y) = −1; ∂ŷ/∂z = σ(z)(1 − σ(z)) = 0,25; ∂L/∂z = −1 · 0,25 = −0,25; ∂L/∂b = ∂L/∂z · 1 = −0,25; ∂L/∂w = ∂L/∂z · ∂z/∂w = −0,25 · 2 = −0,5 (∂z/∂w = x = 2).

Beide Ableitungen sind negativ: Durch Vergrößern von w wie auch b wird der Verlust kleiner — das Netz rückt näher an die Antwort 1.