Graph Theory (Graphentheorie)

Überall.

• Navi: "Finde den kürzesten Weg von A nach B". (Kürzester Pfad).
• Internet: "Wie kommen Daten von Berlin nach New York?" (Routing).
• Empfehlungen: "Nutzer A mag Film X. Nutzer B mag Film X und Y. Also empfehlen wir Nutzer A auch Film Y." (Social Graph).

1. Gerichtete vs. Ungerichtete Graphen

• Gerichtet (Directed): Einbahnstraße. A folgt B auf Twitter (aber B folgt A nicht zwingend). Pfeilspitze wichtig.
• Ungerichtet (Undirected): Freundschaft auf Facebook. Wenn A mit B befreundet ist, ist B auch mit A befreundet.

2. Das Königsberger Brückenproblem

Der Ursprung (1736 von Euler). Kann man einen Spaziergang durch Königsberg machen und jede der 7 Brücken genau einmal überqueren? Euler bewies: Nein. (Es geht nur, wenn maximal 2 Inseln eine ungerade Anzahl von Brücken haben). Das war die Geburtsstunde der Topologie.

1. Graph Traversierung: BFS vs. DFS unter der Haube

Während Level 1 Dijkstra bespricht, liegen Produktionssysteme meist auf puren Sucharchitekturen (Breitensuche BFS, Tiefensuche DFS). Technisch wird der feine Unterschied nur durch die genutzte Datenstruktur bei der Agenda-Expansion bestimmt. Nutzt der Algorithmus für die Vormerkung der "nächsten Kanten" eine Queue (FIFO), flutt das Programm sich in ringförmigen Wellen iterierend vom Ursprung weg (BFS). Nutzt man einen Stack (LIFO) (meist elegant als Rekursions-Callstack kaschiert), schießt DFS brutal geradlinig und speicherplatzsparend $\mathcal{O}(\text{depth})$ wie ein Strahl in den Keller der Baumstrukturen. Für Web-Crawler, die nah beim Index bleiben, rettet BFS, während Labyrinth-Hacker auf DFS schwören.

2. Algebraische Graphentheorie & Adjazenzmatrizen

Graphen existieren in CPUs nicht als bunte Bilder, sondern als Vektormatrizen. Statt in speicherfressender Pointer-Verkettung (Linked Node Lists) operiert man High-Performance Computing Graphen in Adjazenzmatrizen (ein quadratischer $N \times N$ Array aus Vektorzahlen). Matrix Zelle $[A, C] = 1$ impliziert eine Kante zwischen A und C. Das Brilliante daran: Wenn der Graphen-Algorithmus (z. B. "Gibt es Pfade der Länge 3 zwischen A und D?") anspringt, mutiert die Suche mathematisch zu stupider, algebraischer Matrix-Multiplikation ($A \times A \times A = A^3$). Dies erlaubt die brutale Ausbeutung von Tensor-Cores in modernen Nvidia-GPUs, welche Matrix-Kreuzprodukte parallel in millionenfacher Schallgeschwindigkeit crunchen können.

3. PageRank: Die Random-Surfer Markov Kette

Google gewann den Suchmaschinen-Krieg nicht wegen Suchpräzision, sondern mit PageRank, einem puren Graphentheorie-Hack von Larry Page (1998). Das Web ist ein gigantischer gerichteter Graph. Wie wichtet man ihn? Ein Knoten ist "wichtig", wenn viele Graphen auf ihn referenzieren (Eingehender Pfeil). Das Modell simulierte stochastisch einen Affen ("Random Surfer"). Der Affe klickt für alle Zeit unendlich zufällige Links. Die Mathematik eines Eigenvektors einer linkskonditionierten stochastischen Übergangsmatrix errechnet dabei die endgültige Wahrscheinlichkeit für jede Webseite. Der Algorithmus (Iterative Power Method) stabilisiert nach Milliarden Iterationen exakt beim stationären Verteilungsvektor. Dies destillierte absolute objektive Bedeutung aus reinster Topologie-Graphenverschlingung der Serverstruktur.