Elementare Graphenalgorithmen - Vorlesungsnotizen

Grundlagen und Definitionen von Graphen

• Bedeutung von Graphen: Graphen sind fundamentale Strukturen in der Informatik und finden Anwendung in:

  • (Computer-)Netzwerken.

  • Darstellung von topologischen Informationen (z. B. Landkarten).

  • Darstellung elektronischer Schaltungen.

  • Vorranggraphen (Precedence Graphs) und Ablaufplänen.

  • Semantischen Netzen (z. B. Entity-Relationship-Diagramme).

• Gerichteter Graph (Digraph):

  • Ein gerichteter Graph $G$ ist ein Paar $(V, E)$.

  • $V$: Eine Menge von Knoten (vertices).

  • $E \subseteq \{(u, v) | u, v \in V\}$: Eine Menge von gerichteten Kanten (edges).

• Ungerichteter Graph:

  • Ein ungerichteter Graph $G$ ist ein Paar $(V, E)$.

  • $V$: Eine Menge von Knoten (vertices).

  • $E \subseteq \{\{u, v\} | u, v \in V, u \neq v\}$: Eine Menge von ungerichteten Kanten.

  • Für ungerichtete Kanten wird oft ebenfalls die Notation $(u, v)$ verwendet, wobei die Reihenfolge keine Rolle spielt.

• Adjazenz: Ein Knoten $v \in V$ ist adjazent zu $u \in V$, wenn eine Kante $(u, v) \in E$ existiert.

Terminologie bei Graphen

• Teilgraph (Subgraph):

  • Ein Teilgraph $G' = (V', E')$ eines Graphen $G = (V, E)$ erfüllt:

    • $V' \subseteq V$

    • $E' \subseteq E$

    • $E' \subseteq V' \times V'$ (Grapheigenschaft).

  • Ein echter (proper) Teilgraph liegt vor, wenn $V' \subset V$ oder $E' \subset E$.

• Symmetrischer Digraph:

  • Ein Digraph $G$ heißt symmetrisch, wenn gilt: $(u, v) \in E \Rightarrow (v, u) \in E$.

  • Jedem ungerichteten Graphen entspricht ein symmetrischer Digraph.

• Vollständiger Graph: Ein Graph ist vollständig, wenn seine Kantenmenge maximal ist (d. h. jede mögliche Kante zwischen zwei Knoten existiert).

• Transponieren eines Digraphen:

  • Das Transponierte eines Digraphen $G = (V, E)$ ist der Graph $G^T = (V, E')$ mit $(v, u) \in E'$ genau dann, wenn $(u, v) \in E$.

  • In $G^T$ ist die Richtung aller Kanten von $G$ umgedreht.

• Pfade (Wege):

  • Ein Pfad der Länge $k$ von $u$ nach $w$ ist eine Folge $v_0, v_1, \dots, v_k$ mit $v_0 = u$, $v_k = w$ und $(v_i, v_{i+1}) \in E$

  • Die Länge ist die Anzahl der Kanten.

  • Leerer Pfad: Pfad der Länge $0$.

  • Einfacher Pfad: Ein Pfad, bei dem alle Knoten $v_i \neq v_j$ für alle $i \neq j$ verschieden sind.

  • Erreichbarkeit: Knoten $w$ ist von $u$ erreichbar, wenn ein Pfad von $u$ nach $w$ existiert.

• Zyklen:

  • In gerichteten Graphen: Ein nicht-leerer Pfad, bei dem Start- und Endknoten gleich sind. Eine Schlinge (self-loop) ist ein Zyklus der Länge $1$. Ein Zyklus ist einfach, wenn alle Knoten außer Start/Ende paarweise verschieden sind.

  • In ungerichteten Graphen: Ein Pfad $v_0 \dots v_k$ mit $k \ge 3$, $v_0 = v_k$ und $v_1, \dots, v_k$ paarweise verschieden.

  • Ein Graph ist azyklisch, wenn er keine Zyklen enthält.

Fragen & Diskussion (Zusammenhang und Bäume)

• Frage: Wie viele Kanten hat ein Baum (zusammenhängender azyklischer Graph) mit $n$ Knoten?

  • Antwort: $n - 1$.

• Frage: Kann ein ungerichteter Graph mit $n$ Knoten und $n - 1$ Kanten zusammenhängend sein?

  • Antwort: Ja.

• Frage: Kann ein ungerichteter Graph mit $n$ Knoten und $n - 2$ Kanten zusammenhängend sein?

  • Antwort: Nein.

• Frage: Kann ein ungerichteter Graph mit $n$ Knoten und $n$ Kanten azyklisch sein?

  • Antwort: Nein.

Repräsentation von Graphen

Gegeben sei $G = (V, E)$ mit $|V| = n$ und $|E| = m$.

• Adjazenzmatrix:

  • Eine $n \times n$-Matrix $A$.

  • $A(i, j) = 1$, falls $(v_i, v_j) \in E$, sonst $0$.

  • Bei ungerichteten Graphen ist $A$ symmetrisch ($A = A^T$).

  • Platzbedarf: $\Theta(n^2)$.

• Adjazenzliste:

  • Ein Array der Größe $n$ enthält für jeden Knoten eine verkettete Liste aller ausgehenden Kanten.

  • Bei ungerichteten Graphen werden Kanten doppelt gespeichert (einmal für jeden Endknoten).

  • Platzbedarf: $\Theta(n + m)$.

Graphendurchlauf-Strategien

Graphendurchläufe besuchen jeden Knoten und jede Kante genau einmal. Bei zyklischen Graphen müssen bereits besuchte Knoten markiert werden (Farben: WHITE = nicht gefunden, GRAY = gefunden/in Verarbeitung, BLACK = abgeschlossen).

Breitensuche (Breadth-First Search, BFS)

• Strategie: Erforscht den Graphen schichtweise. Zuerst alle Nachbarn des Startknotens, dann deren Nachbarn usw.

• Eigenschaften:

  • Besucht Knoten in der Reihenfolge zunehmender Kantendistanz zum Startknoten.

  • Verwendet eine FIFO-Warteschlange (Queue).

  • Zeitkomplexität: $O(|V| + |E|)$.

  • Platzbedarf: $\Theta(|V|)$.

Tiefensuche (Depth-First Search, DFS)

• Strategie: Geht so tief wie möglich in einen Pfad hinein, bevor Backtracking (Rückzug) stattfindet.

• Implementierung: Erfolgt meist rekursiv (nutzt den impliziten LIFO-Stack).

• Eigenschaften:

  • Wird für Erreichbarkeitsanalysen, Zusammenhangskomponenten und topologische Sortierung genutzt.

  • Zeitkomplexität: $O(|V| + |E|)$.

  • Platzbedarf: $\Theta(|V|)$.

Zusammenhangskomponenten (CCs und SCCs)

• Ungerichtete Graphen:

  • Zusammenhängend: Jeder Knoten ist von jedem anderen erreichbar.

  • Zusammenhangskomponente (Connected Component, CC): Ein maximaler zusammenhängender Teilgraph.

  • Lösung: Wiederholte Anwendung von BFS oder DFS findet alle CCs in $O(|V| + |E|)$.

• Gerichtete Graphen:

  • Stark zusammenhängend: Jeder Knoten ist von jedem anderen erreichbar.

  • Schwach zusammenhängend: Der zugrunde liegende ungerichtete Graph ist zusammenhängend.

  • Starke Zusammenhangskomponente (Strongly Connected Component, SCC): Ein maximaler stark zusammenhängender Teilgraph.

• Sharir's Algorithmus für SCCs:

  1. Führe DFS auf $G$ aus. Speichere Knoten beim Abschluss (BLACK) auf einem Stack $S$.

  2. Transponiere den Graphen zu $G^T$.

  3. Solange $S$ nicht leer ist:

     • Nimm obersten weißen Knoten $v$ von $S$.

     • Starte DFS auf $G^T$ von $v$ aus. Alle dabei erreichten Knoten bilden eine SCC mit dem Leiter $v$.

  • Komplexität: Zeit $\Theta(|V| + |E|)$, Platz $\Theta(|V|)$.

Gerichtete azyklische Graphen (DAGs)

• Definition: Ein Digraph ohne Zyklen.

• Bedeutung: Entspricht einer partiellen Ordnung. Viele Probleme sind auf DAGs effizienter lösbar als auf allgemeinen Digraphen.

• Kondensationsgraph: Ein Graph, dessen Knoten die SCCs eines Digraphen sind. Der Kondensationsgraph ist immer ein DAG.

Topologische Sortierung

• Definition: Eine Zuordnung $topo: V \rightarrow \{1, \dots, n\}$, sodass für jede Kante $(v, w) \in E$ gilt: topo(v) > topo(w). (Hinweis: Je nach Definition kann auch topo(v) < topo(w) gelten; hier wird die Abschluss-Reihenfolge der DFS genutzt).

• Eigenschaften:

  • Existiert genau dann, wenn der Graph ein DAG ist.

  • Algorithmus: Nutzt DFS. Die topoNum wird beim Abschluss eines Knotens zugewiesen.

  • Zeitkomplexität: $O(|V| + |E|)$.

Gewichtete Graphen und Kritische-Pfad-Analyse

• Gewichtsfunktionen:

  • Knotengewichtet: $W: V \rightarrow \mathbb{R}$.

  • Kantengewichtet: $W: E \rightarrow \mathbb{R}$.

  • Ein knotengewichteter Graph kann in einen kantengewichteten transformiert werden, indem $W'(e = (v, \cdot)) = W(v)$ gesetzt wird.

• Das Kritische-Pfad-Problem:

  • Gesucht ist der längste Pfad in einem gewichteten DAG.

  • Earliest Start Time (est(v)): Das Maximum der frühesten Endzeitpunkte aller Abhängigkeiten von $v$. Ist $0$, wenn keine Abhängigkeiten existieren.

  • Earliest Finish Time (eft(v)): $eft(v) = est(v) + \text{Dauer}(v)$.

  • Kritischer Pfad: Eine Folge von Aufgaben, bei denen jede Verzögerung direkt die gesamte Projektdauer (maximales $eft$) verlängert.

• Beispiel (Zeitplan):

  • Aufgaben: I (Aufwachen), A (Kleidung wählen), H (Duschen), B (Anziehen), E (Kaffee kochen), F (Toast machen), G (Saft einschenken), C (Frühstücken), D (Haus verlassen).

  • Pfadberechnung: $eft = 1 + 6.5 + 8.5 + 0 = 16$ (basierend auf den Beispiel-Dauern im Zeitplan).