Graphenalgorithmen: Einführung

Dieser Abschnitt legt die fundamentalen Begriffe für die Beschreibung von gerichteten Graphen (Digraphen) fest. Ein Digraph G wird als ein Paar (V, E) definiert, wobei V die Menge der Knoten und E die Menge der gerichteten Kanten darstellt. Eine Kante (a, b) ∈ E verbindet den Startknoten a mit dem Endknoten b. Die Inzidenz beschreibt die Beziehung zwischen einer Kante und ihren Knoten. Eine Kante der Form (a, a) wird als Schlinge bezeichnet. Der Ausgangsgrad eines Knotens a ist die Anzahl der Kanten, die von a ausgehen, während der Eingangsgrad eines Knotens b die Anzahl der Kanten ist, die in b enden. Ein (a, b)-Pfad der Länge k ist eine Folge von Knoten (v₀, ..., vₖ) mit (vᵢ, vᵢ₊₁) ∈ E, v₀ = a und vₖ = b. Ein Pfad ist ein Weg, wenn alle Knoten paarweise verschieden sind. Ein Zyklus ist ein Pfad mit a = b, und ein Kreis ist ein Zyklus, bei dem alle Knoten bis auf den letzten paarweise verschieden sind. Zyklen werden als gleich betrachtet, wenn sie durch zyklische Verschiebung der Knotenfolge ineinander überführbar sind. Eine Kante (a, b) gehört zu einem Pfad, wenn sie zwei aufeinanderfolgende Knoten des Pfades verbindet. Digraphen ohne Zyklen werden als azyklisch bezeichnet. Für ungewichtete Graphen wird der Grad eines Knotens als die Anzahl der inzidenten Kanten definiert. Ähnliche Definitionen für Pfade, Wege, Teilpfade, Zyklen und Kreise gelten analog für ungerichtete Graphen. Ein Graph ohne Zyklen ist ein Wald, ein zusammenhängender Wald ist ein Baum. Ein Teilgraph G eines Graphen G₀ besitzt Knoten- und Kantenmengen, die Teilmengen der entsprechenden Mengen von G₀ sind. Die unterschiedliche Terminologie in der Literatur (z.B. gerichteter Graph = Digraph, Knoten = Ecke, etc.) wird explizit erwähnt und die möglichen Variationen in den Definitionen werden hervorgehoben.

Ein wichtiger Aspekt der Arbeit mit Graphen ist ihre effiziente Repräsentation im Rechner. Der Text beschreibt die Speicherung von Digraphen mithilfe von Adjazenzlisten. Die Eingabe für einen Algorithmus besteht aus einem Digraphen G = (V, E) mit n Knoten und m Kanten, sowie einem Startknoten s ∈ V. Die Adjazenzliste N ist eine Liste von n Listen, wobei N[u] für jeden Knoten u ∈ V die Liste aller Knoten v enthält, für die (u, v) ∈ E gilt. Im theoretischen RAM-Modell benötigt die Speicherung von N O(m + n) Speichereinheiten. In einer praktischen Implementierung werden Zeiger verwendet, um die Adjazenzliste effizient zu verwalten. Der Vorteil von Adjazenzlisten gegenüber der Speicherung als Kantenliste besteht darin, dass der Zugriff auf die ausgehenden Kanten eines Knotens u direkt erfolgt, während bei der Kantenliste eine Iteration über alle m Kanten notwendig wäre. Diese Effizienzsteigerung ist besonders relevant, wenn der Ausgangsgrad der Knoten deutlich kleiner als die Gesamtzahl der Kanten ist. Die Verwendung der Kurzschreibweise ab := {a, b} für die Beschreibung von Kanten in ungerichteten Graphen wird erwähnt. Der Abschnitt betont die Unterschiede in der Terminologie und der Definition von Graphen und Digraphen in verschiedenen Quellen, und weist auf die Synonyme für die zentralen Begriffe hin (z.B. Knoten = Ecke, Kante = Bogen).

Die Breitensuche (BFS) ist ein Algorithmus zur systematischen Durchsuchung eines Graphen. Sie verwendet eine Warteschlange als Datenstruktur, um Knoten in der Reihenfolge ihrer Entfernung vom Startknoten zu besuchen. Der Algorithmus beginnt beim Startknoten und fügt ihn der Warteschlange hinzu. Solange die Warteschlange nicht leer ist, wird der erste Knoten aus der Warteschlange entfernt und seine Nachbarn untersucht. Sind diese Nachbarn noch nicht besucht, werden sie markiert und der Warteschlange hinzugefügt. Dieser Prozess wiederholt sich, bis alle von Startknoten aus erreichbaren Knoten besucht wurden. Die Breitensuche findet den kürzesten Pfad vom Startknoten zu allen erreichbaren Knoten im Graphen. Die Implementierung kann effizient mit Arrays der Länge n (Anzahl der Knoten) realisiert werden, da die maximale Größe der Warteschlange bekannt ist. Für Knoten u, v wird der Abstand δ(u, v) als minimale Länge eines (u, v)-Pfades definiert; existiert kein Pfad, ist δ(u, v) = ∞. In ungerichteten Graphen gilt δ(u, v) = δ(v, u). Die Korrektheit des Algorithmus wird durch die Invariante bewiesen, dass in jedem Schritt für alle Knoten v gilt: d[v] ≥ δ(s, v), wobei d[v] der berechnete und δ(s,v) der tatsächliche Abstand vom Startknoten s ist. Die Analyse der Laufzeit zeigt, dass jeder Knoten höchstens einmal in die Warteschlange aufgenommen wird, und die Anzahl der Operationen durch die Anzahl der Knoten und Kanten begrenzt ist. Eine spezielle Eigenschaft der Warteschlange Q während der Ausführung ist, dass die Liste der Distanzen der Knoten in Q aufsteigend sortiert ist und höchstens zwei verschiedene Werte enthält. Nach der Terminierung gilt d(v) = δ(s, v) für alle v ∈ V.

Die Tiefensuche (DFS) bietet eine alternative Strategie zur Graphdurchquerung. Im Gegensatz zur BFS, die zuerst alle Nachbarn eines Knotens besucht, bevor sie zu anderen Knoten übergeht, geht die DFS so tief wie möglich entlang eines Pfades, bevor sie zurückgeht und andere Pfade erkundet. Dies kann rekursiv oder iterativ (mit einem Stack anstelle der Warteschlange) implementiert werden. Die rekursive Implementierung ist intuitiv verständlicher, aber die iterative Version kann Vorteile bei der Vermeidung von Stack-Überläufen bieten. Eine Möglichkeit, die Pfade von einem Startknoten s zu allen erreichbaren Knoten zu berechnen, ist die Verwendung einer Vorgänger-Abbildung π. Diese Abbildung speichert für jeden Knoten v den Knoten u, von dem aus v entdeckt wurde (π[v] := u). Jeder (s, π[v])-Pfad kann durch Anhängen von v zu einem (s, v)-Pfad erweitert werden. Die iterative Implementierung der Pfadberechnung, analog zur Breitensuche, ist ebenfalls möglich. Der Text beschreibt ein induktives Argument zur Erreichbarkeit von Knoten: wenn alle Knoten u₁, ..., uⱼ₋₁ von s aus erreichbar sind, dann ist auch uⱼ erreichbar, wenn es eine Kante (uᵢ, uⱼ) gibt mit i ≤ j-1. Die Vorgänger-Abbildung ermöglicht die effiziente Rekonstruktion der Pfade nach der Suche.

Der Abschnitt definiert das Problem der kürzesten Pfade (PKP) in einem gewichteten Digraphen G = (V, E, w) mit nicht-negativen ganzzahligen Kantengewichten. Gegeben ist ein Startknoten s ∈ V, und das Ziel ist, für jeden Knoten v ∈ V den Abstand δ(s, v) zu berechnen, welcher die minimale Länge eines Pfades von s nach v darstellt. Existiert kein solcher Pfad, ist δ(s, v) = ∞. Die Eingabe wird durch eine Adjazenzliste repräsentiert, die für jeden Knoten u eine Liste N[u] aller Nachbarn v mit (u, v) ∈ E enthält. Die Kantengewichte sind Teil der Adjazenzlisteninformation. Die Effizienz der Adjazenzlisten-Darstellung wird im Vergleich zur Speicherung als Kantenliste hervorgehoben: Die Adjazenzliste erlaubt direkten Zugriff auf die ausgehenden Kanten eines Knotens, während die Kantenliste eine Iteration über alle Kanten erfordert. Die Speicherung der Adjazenzliste benötigt im RAM-Modell O(m + n) Speichereinheiten, wobei m die Anzahl der Kanten und n die Anzahl der Knoten ist. Der Abschnitt führt die Abkürzung PKP für das Problem der kürzesten Pfade ein und legt den Fokus auf die Berechnung der kürzesten Pfade von einem gegebenen Startknoten.

Der Bellman-Ford-Algorithmus (BFA) ist ein Algorithmus zur Lösung des PKP-Problems. Er funktioniert auch für Graphen mit negativen Kantengewichten, solange keine negativen Zyklen existieren. Der Algorithmus ist relativ einfach aufgebaut und besteht aus mehreren geschachtelten Schleifen. Seine Einfachheit wird als Vorteil hervorgehoben. Die Korrektheit des Algorithmus wird durch den Beweis der Invariante d[v] ≥ δ(s, v) für alle Knoten v zu jedem Zeitpunkt der Ausführung sichergestellt. Der Algorithmus berechnet die kürzesten Pfade iterativ, indem er die Distanzen zu allen Knoten aktualisiert, basierend auf den Entfernungen zu ihren Vorgängern und den Kantengewichten. Die Laufzeit kann durch vorherige Breitensuche oder Tiefensuche optimiert werden, um zuerst unerreichbare Knoten zu eliminieren und den BFA auf einem kleineren Graphen anzuwenden. Die Verwendung einer Vorgänger-Abbildung ermöglicht die Rekonstruktion der kürzesten Pfade. Die Einfachheit des Algorithmus wird im Vergleich zu anderen Algorithmen zur Lösung des PKP-Problems hervorgehoben, wobei er aus mehreren geschachtelten Schleifen besteht.

Der Dijkstra-Algorithmus (DA) ist ein weiterer Algorithmus zur Lösung des PKP-Problems, der jedoch nur für Graphen mit nicht-negativen Kantengewichten geeignet ist. Im Gegensatz zum BFA verwendet der DA eine Prioritätswarteschlange (z.B. implementiert mit Heaps), um effizient den Knoten mit dem kleinsten aktuellen Abstand zum Startknoten auszuwählen. Die Laufzeit des Algorithmus wird mit O((m + n) log n) angegeben, wenn die Warteschlange mit Heaps implementiert ist. Die Korrektheit wird ähnlich wie beim BFA durch eine Invariante bewiesen: d[v] ≥ δ(s, v) zu jedem Zeitpunkt. Es wird gezeigt, dass für jeden Knoten u, der aus der Warteschlange entfernt wurde, d[u] = δ(s, u) gilt. Ein Widerspruchsbeweis wird verwendet, um zu zeigen, dass falls für einen Knoten u, der aus der Warteschlange entfernt wird, d[u] > δ(s, u) gilt, ein Knoten mit kleinerer Distanz in der Warteschlange vorhanden sein muss, was einen Widerspruch darstellt. Auch beim DA kann eine Vorgänger-Abbildung zur Rekonstruktion der kürzesten Pfade verwendet werden.

Dieser Abschnitt beschreibt die LU-Zerlegung einer regulären Matrix A als effizientes Verfahren zur Lösung linearer Gleichungssysteme Ax = b. Die LU-Zerlegung mit partieller Pivotsuche zerlegt die Matrix A in eine untere Dreiecksmatrix L, eine obere Dreiecksmatrix U und eine Permutationsmatrix P, so dass PA = LU gilt. Der Algorithmus basiert auf einem iterativen Verfahren, das ähnlich dem Gauß-Eliminationsverfahren arbeitet, aber anstatt Zeilen werden Spalten vertauscht (Pivot-Strategie). Zuerst wird eine Spalte mit einem nicht-null Element ausgewählt (das kleinste j mit A*,j ≠ 0). Nach einer Zeilenvertauschung (Pivot) kann mit Hilfe der ersten Zeile die j-te Spalte so transformiert werden, dass alle Einträge außer dem ersten Null sind. Dieses Verfahren wird dann rekursiv auf die verbleibende Untermatrix angewendet. Die Laufzeitkomplexität dieses Verfahrens beträgt O(n³), da n-1 Iterationen mit je O(n²) Operationen pro Iteration durchgeführt werden. Die geometrische Bedeutung der Konditionszahl κ(A) = ||A|| ||A⁻¹|| wird kurz erwähnt; sie beschreibt das Verhältnis von Umkugelradius zu Inkugelradius des durch A transformierten Einheitsballs. Die Ergebnisse gelten für allgemeine Normen auf Rⁿ.

Die Berechnung der LU-Zerlegung (L, U, P) einer Matrix A kann als Vorverarbeitungsschritt zur Lösung von Gleichungssystemen Ax = b mit verschiedenen rechten Seiten b verwendet werden. Die Lösung erfolgt dann durch die schrittweise Anwendung der inversen Matrizen P⁻¹, U⁻¹ und L⁻¹. Die Multiplikation mit L⁻¹ und U⁻¹ benötigt jeweils O(n²) Operationen, während die Multiplikation mit P⁻¹ lediglich ein Vertauschen von Komponenten darstellt und keine arithmetischen Operationen erfordert. Daher kann die Lösung von Ax = b nach der Vorverarbeitung in O(n²) erfolgen. Obwohl die direkte Berechnung der Inversen A⁻¹ ebenfalls mit O(n³) möglich ist, wird die LU-Zerlegung oft bevorzugt, da die in der O-Notation versteckte Konstante in der Praxis günstiger sein kann. Die LU-Zerlegung bietet also einen effizienten Weg, um mehrere Gleichungssysteme mit derselben Matrix A, aber unterschiedlichen rechten Seiten b, zu lösen, ohne die Matrixinversion für jedes System neu berechnen zu müssen.

Der Abschnitt beschreibt das Newton-Verfahren, ein iteratives Verfahren zur näherungsweisen Bestimmung der Nullstellen einer Funktion f: U → R. Gegeben ist eine Nullstelle x* ∈ U einer zweimal differenzierbaren Funktion f. Das Verfahren basiert auf der Idee, die Funktion in der Umgebung der aktuellen Näherung xₖ durch ihre Tangente zu approximieren. Die Nullstelle der Tangente liefert dann die nächste Näherung xₖ₊₁ nach der Formel: xₖ₊₁ = xₖ - f(xₖ)/f'(xₖ). Die Konvergenz des Verfahrens wird analysiert unter der Voraussetzung, dass die Funktion f in einer Umgebung I = (x* - ρ, x* + ρ) zweimal differenzierbar ist und die Ableitung f' in dieser Umgebung nicht verschwindet. Es wird eine Abschätzung der Konvergenzgeschwindigkeit angegeben: In jeder Iteration verdoppelt sich die Anzahl der korrekten Nachkommastellen annähernd. Das bedeutet, dass das Newton-Verfahren eine extrem schnelle Konvergenz aufweist, jedoch ist die Bedingung, dass der Startwert x₀ hinreichend nahe an der Nullstelle x* liegen muss, recht restriktiv. Die Konvergenzgeschwindigkeit wird als Ω(2ᵏ) beschrieben, was die exponentielle Verbesserung der Genauigkeit mit jeder Iteration unterstreicht.

Dieser Abschnitt legt die Grundlage für die Diskussion der NP-Vollständigkeit. Er beginnt mit der formalen Definition einer Rechenaufgabe als binäre Relation R ⊆ {0, 1}* × {0, 1}, wobei {0, 1} die Menge aller möglichen Bitstrings darstellt. Ein Bitstring x repräsentiert die Eingabe, und ein Bitstring y repräsentiert ein mögliches Ergebnis. Die Zugehörigkeit (x, y) ∈ R bedeutet, dass y ein gültiges Ergebnis für die Eingabe x ist. Der Begriff einer Sprache L wird eingeführt als eine Menge von Bitstrings, die eine bestimmte Eigenschaft erfüllen. Ein Algorithmus A entscheidet eine Sprache L, wenn er für jede Eingabe x ∈ {0, 1}* korrekt bestimmt, ob x ∈ L gilt oder nicht. Als Beispiel wird die Frage genannt, ob ein gegebener Graph zusammenhängend ist. Um dieses Problem formal zu beschreiben, muss eine Kodierung von Graphen als Bitstrings definiert werden. Die Klasse NP wird informell als die Klasse von Entscheidungsproblemen eingeführt, für die eine positive Antwort durch ein 'Zertifikat' in Polynomialzeit verifiziert werden kann. Ein Zertifikat ist eine zusätzliche Information, die die Richtigkeit der positiven Antwort beweist. Die asymmetrische Natur solcher Ja/Nein-Fragen wird hervorgehoben: Eine positive Antwort ist oft leichter zu verifizieren als eine negative Antwort.

Der Abschnitt führt den Begriff der NP-Vollständigkeit ein. Eine Sprache L heißt NP-schwer, wenn jede Sprache aus NP in Polynomialzeit auf L reduziert werden kann. Eine NP-schwere Sprache, die selbst in NP liegt, heißt NP-vollständig. Informell sind NP-vollständige Probleme die 'schwersten' Probleme in NP. Der Satz von Cook-Levin wird erwähnt, der die Existenz von NP-vollständigen Problemen beweist. Boolesche Formeln werden eingeführt, einschließlich Literalen (Variable oder Negation), Konjunktionstermen, Disjunktionstermen, der disjunktiven Normalform (DNF) und der konjunktiven Normalform (KNF). Eine boolesche Formel φ ist erfüllbar, wenn es eine Belegung der Variablen gibt, die φ zu 1 evaluiert. Das Erfüllbarkeitsproblem (SAT) besteht darin, zu entscheiden, ob eine gegebene boolesche Formel erfüllbar ist. Die Reduktion von Problemen auf einander wird durch die Polynomialzeit-Reduktion ≤ₚ beschrieben: Eine Funktion f ist eine Polynomialzeit-Reduktion von L₀ auf L, wenn f in Polynomialzeit berechenbar ist und x ∈ L₀ genau dann gilt, wenn f(x) ∈ L gilt. Die Relation ≤ₚ ist eine Teilordnung auf der Menge aller Sprachen über dem Alphabet {0, 1}.

Der Abschnitt zeigt die NP-Schwere des Erfüllbarkeitsproblems (SAT) und des 3SAT-Problems. Es wird erläutert, wie die Erfüllbarkeit einer KNF-Formel als ganzzahlige Lösbarkeit eines linearen Ungleichungssystems umformuliert werden kann. Diese Umformulierung ist in Polynomialzeit durchführbar. Der Beweis der NP-Vollständigkeit von 3SAT beinhaltet die Konstruktion einer Polynomialzeit-Reduktion von SAT auf 3SAT. Es wird gezeigt, wie man eine beliebige Klausel (x₁ ∨ ... ∨ xₘ) in eine äquivalente 3SAT-Formel umwandeln kann, indem man zusätzliche Variablen einführt und Implikationen verwendet. Die Äquivalenz (x → y) ∨ z = x ∨ y ∨ z wird genutzt, um Implikationen durch zusätzliche Klauseln zu ersetzen. Durch diese Umwandlung kann jede SAT-Instanz in eine äquivalente 3SAT-Instanz transformiert werden, was die NP-Vollständigkeit von 3SAT beweist, da SAT ein NP-vollständiges Problem ist. Die Laufzeit der Umwandlung ist polynomiell in der Größe der ursprünglichen Formel.