Graphentheorie — Netzwerke, Wege und Optimierung

Einführung

Wie findet Google Maps den schnellsten Weg? Wie analysiert Facebook Freundschaftsbeziehungen? Wie optimiert ein Paketdienst seine Lieferrouten? All diese Probleme haben eine gemeinsame mathematische Struktur: Sie lassen sich als Graph modellieren. Die Graphentheorie ist eine der anwendungsreichsten Gebiete der modernen Mathematik — und wurde 1736 von Euler mit einer Frage über Brücken in Königsberg begründet.

Grundidee

Ein Graph ist ein abstraktes Modell für Verbindungen. Man stellt sich Objekte als Punkte (Knoten) vor und Verbindungen zwischen ihnen als Linien (Kanten). Ein Straßennetz, ein soziales Netzwerk, ein Schaltkreis, ein Stundenplan — all das ist ein Graph, sobald man abstrahiert.

Erklärung

Grundbegriffe

Ein Graph $G = (V, E)$ besteht aus:

• einer Menge $V$ von Knoten (engl. vertices)
• einer Menge $E$ von Kanten (engl. edges) — Paare von Knoten

Beispiel: $V = \{A, B, C, D\}$, $E = \{AB, BC, CD, AD, BD\}$

A ─── B
│  ╲  │
│   ╲ │
D ─── C

Grad eines Knotens: Anzahl der Kanten, die an ihm hängen. Im Beispiel: $\text{deg}(B) = 3$.

Handschlaglemma: Die Summe aller Knotengrade ist immer gerade (jede Kante zählt zweimal): $\sum_{v \in V} \text{deg}(v) = 2|E|$

Gerichtete und ungerichtete Graphen

In einem ungerichteten Graphen sind Kanten ohne Pfeilrichtung — Verbindungen gelten in beide Richtungen (z. B. Freundschaften auf Facebook).

In einem gerichteten Graphen (Digraph) haben Kanten eine Richtung — Pfeile statt Linien (z. B. Twitter-Follows, Einbahnstraßen). Eine Kante von $A$ nach $B$ bedeutet nicht, dass es auch eine von $B$ nach $A$ gibt.

Gewichteter Graph: Kanten tragen zusätzlich ein Gewicht (z. B. Entfernung, Kosten, Zeit).

Wege und Kreise

Ein Weg ist eine Folge von Knoten, bei der aufeinanderfolgende Knoten durch eine Kante verbunden sind, ohne Kante zu wiederholen. Ein Pfad wiederholt auch keinen Knoten.

Ein Kreis (Zyklus) ist ein Weg, der beim Startknoten endet.

Ein Graph ohne Kreise heißt azyklisch.

Euler-Wege — Das Königsberger Brückenproblem

1736 fragte Euler: Kann man alle sieben Brücken Königsbergs genau einmal überqueren und zum Startpunkt zurückkehren?

Ein Euler-Weg überquert jede Kante genau einmal. Ein Euler-Kreis ist ein Euler-Weg, der wieder zum Start zurückführt.

Eulers Satz:

• Ein Euler-Kreis existiert genau dann, wenn alle Knoten geraden Grad haben.
• Ein Euler-Weg (ohne Rückkehr) existiert genau dann, wenn genau 2 Knoten ungeraden Grad haben (Start und Ende).

Im Königsberger Problem hatten alle 4 Knoten ungeraden Grad — also war weder Euler-Weg noch Euler-Kreis möglich.

Bäume

Ein Baum ist ein zusammenhängender, kreisfreier Graph. Er hat genau $|V| - 1$ Kanten.

Bäume sind überall: Verzeichnisstrukturen, Stammbaum, Entscheidungsbaum, Syntaxbaum. Ein Wald ist eine Sammlung disjunkter Bäume.

Adjazenzmatrix

Die Adjazenzmatrix $A$ eines Graphen mit $n$ Knoten ist eine $n \times n$-Matrix:

$A_{ij} = \begin{cases} 1 & \text{falls Kante zwischen Knoten } i \text{ und } j \\ 0 & \text{sonst} \end{cases}$

Für den Graphen $V = \{1, 2, 3\}$, $E = \{12, 13, 23\}$ (vollständiger Graph $K_3$):

$A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix}$

Für ungerichtete Graphen ist $A$ symmetrisch. Das Matrizenprodukt $A^2$ verrät, wie viele Wege der Länge 2 zwischen je zwei Knoten existieren.

Dijkstra-Algorithmus

Dijkstra findet den kürzesten Weg von einem Startknoten zu allen anderen Knoten in einem nicht-negativ gewichteten Graphen.

Idee: Halte für jeden Knoten den aktuell bekannten kürzesten Abstand zum Startknoten. Erweitere immer den Knoten mit dem kleinsten bekannten Abstand.

Beispiel: Finde den kürzesten Weg von $S$ aus:

    2      3
S ──── A ──── C
│      │      │
│4     │1     │2
│      │      │
└──── B ──── D
       5

Schritt	Besuchter Knoten	Abstände
Start	S	S=0, A=∞, B=∞, C=∞, D=∞
1	S	A=2, B=4
2	A	B=3 (via A), C=5
3	B	D=8
4	C	D=7 (via C)
5	D	fertig

Beispiel aus dem Alltag

Google Maps: Das Straßennetz ist ein gewichteter gerichteter Graph (Einbahnstraßen!). Kreuzungen sind Knoten, Straßenabschnitte sind gewichtete Kanten (Gewicht = Fahrtzeit). Dijkstra oder verwandte Algorithmen wie A* finden den schnellsten Weg.

Soziale Netzwerke: Auf Facebook ist jeder Nutzer ein Knoten, jede Freundschaft eine Kante. Algorithmen analysieren, wer die einflussreichsten Knoten sind (hoher Grad = viele Verbindungen), und empfehlen neue Freunde über kurze Wege.

Lieferketten: Ein Logistikunternehmen modelliert Lager und Kunden als Knoten, Transportrouten als Kanten mit Kosten. Das Traveling-Salesman-Problem (jeden Knoten genau einmal besuchen, Kosten minimieren) ist eines der berühmtesten ungelösten Optimierungsprobleme.

Anwendung

Aufgabe: Prüfe für den folgenden Graphen, ob ein Euler-Kreis oder Euler-Weg existiert:

$V = \{A, B, C, D, E\}$, $E = \{AB, AC, BC, BD, CD, DE\}$

Lösung:

• $\text{deg}(A) = 2$ (AB, AC) — gerade
• $\text{deg}(B) = 3$ (AB, BC, BD) — ungerade
• $\text{deg}(C) = 3$ (AC, BC, CD) — ungerade
• $\text{deg}(D) = 3$ (BD, CD, DE) — ungerade
• $\text{deg}(E) = 1$ (DE) — ungerade

Es gibt 4 Knoten mit ungeradem Grad. Weder Euler-Kreis (braucht 0 ungerade Knoten) noch Euler-Weg (braucht genau 2) ist möglich.

Typische Fehler

Weg vs. Pfad vs. Euler-Weg verwechseln: Ein Weg darf Knoten wiederholen (aber keine Kante), ein Pfad darf weder Kante noch Knoten wiederholen, ein Euler-Weg besucht jede Kante genau einmal (Knoten dürfen wiederholt werden).

Adjazenzmatrix für gerichtete Graphen: Bei gerichteten Graphen ist die Adjazenzmatrix nicht mehr symmetrisch. $A_{ij} = 1$ bedeutet: Kante von Knoten $i$ nach Knoten $j$.

Zusammenfassung

Merke dir:

• Graph $G = (V, E)$: Knoten $V$ und Kanten $E$ — abstrakt für jede Verbindungsstruktur
• Grad eines Knotens = Anzahl angrenzender Kanten; Summe aller Grade = $2|E|$
• Euler-Kreis: alle Grade gerade; Euler-Weg: genau 2 Knoten mit ungeradem Grad
• Baum: zusammenhängend, kreisfrei, $|V|-1$ Kanten
• Adjazenzmatrix: kompakte Darstellung für Algorithmen
• Dijkstra: kürzester Weg bei nicht-negativen Gewichten — Grundlage von Navigationssystemen

Quiz

Frage 1: Ein Graph hat 5 Knoten mit den Graden 3, 3, 2, 2, 2. Wie viele Kanten hat er?

Frage 2: Ist ein Euler-Kreis im vollständigen Graphen $K_4$ (4 Knoten, alle Paare verbunden) möglich?

Frage 3: Zeichne die Adjazenzmatrix für den Graphen $V = \{1, 2, 3, 4\}$, $E = \{12, 23, 34, 14\}$ (ein Viereck).

Frage 4: Warum ist Dijkstra nicht anwendbar, wenn ein Graph negative Kantengewichte hat?