Die Vorlesung Effiziente Graphenalgorithmen der Fernuni Hagen basiert auf dem Buch “CATBox: An Interactive Course in Combinatorial Optimization”. Das Buch ist in seiner Form sehr mathemathisch geschrieben, d.h. es basiert überwiegend auf einer Abfolge von Definitionen, Sätzen, Lemmata, Beweisen und Folgerungen.

Ohne eine eigene Struktur finde ich es dabei manchmal schwer, dem Verlauf des Textes und den gerade verfolgten Zielen zu folgen. Während man den Beweis studiert (was eine halbe Stunde oder mehr dauern kann), vergisst man für welches größere Ziel dieser kleine Teilbeweis nun eigentlich geführt werden musste.

Dies soll keine Kritik am Autor sein. Als Student eines wissenschaftlichen Fachs muss man lernen, sich selbst die für einen persönlich notwendigen Notizen zu erarbeiten, um einen stringent formulierten wissenschaftlichen Text verfolgen zu können.

Deshalb habe ich mir für die Vorlesung einen kleinen Leitfaden zusammengetragen, der mir die wichtigsten Themen des Buches auflistet. Im Groben orientiert er sich an den Kapitelüberschriften des Buches, weicht aber in der Reihenfolge der aufgelisteten Punkte davon ab. In der Struktur orientiere ich mich an meiner Denkreihenfolge: Ich habe ein Problem, das will ich lösen. Um es zu lösen brauche ich einen Algorithmus. Jetzt habe ich einen Algorithmus, aber warum funktioniert er überhaupt, was sind die theoretischen Grundlagen?

Einführung

  • Notation von Graphen
  • Graphen-Repräsentation in Algorithmen
  • Algorithmen:
    • Komponenten-Labeling-Algorithmus
    • Depth-First-Search
    • Breadth-First-Search

Minimum Spanning Trees

  • Probleme:
    • Minimum Connected Subgraph
    • Minimum Spanning Tree
  • Algorithmen:
    • Kruskals Algorithmus
    • Prims Algorithmus
  • Mathemathische Konzepte:
    • Matroide
  • Beweishilfsmittel:
    • Circuit Criterion
    • Cut Criterion

Dualität linearer Programme

In diesem Kapitel gibt es keine neuen Algorithmen oder Problemstellungen. Stattdessen führt es theoretische Grundlagen ein und überträgt die bereits bekannten Problemstellungen in die neue Domäne.

  • Theoretische Grundlagen:
    • Lineare Programme und Dualisierung
    • Lemma von Farkas
    • Dualität: Schwache Dualität, Starke Dualität
    • Complementary Slackness
  • Übertragungen:
    • Minimum Spanning Tree als Polytop: In diesem Kapitel wird das Problem MST in den geometrischen Raum überführt, genauer in ein konvexes Polyhedron (die Begriffe Polyhedron und Polytop werden in der Literatur verschieden verwendet). Dieses Polyhedron kann dann als Nebenbedingung zur Formulierung eines linearen Programms verwendet werden.
    • MST als Primal-Dualer Algorithmus: Für das rein primale Programm ist nicht sofort eine gültige Lösung ersichtlich. Durch Überführung des primalen in das duale Programm findet man leicht eine Anfangslösung und über gemeinsame Anwendung des primalen und dualen Programms (Primal-Duale Methode) findet man zur optimalen Lösung.

Kürzeste Pfade

  • Probleme:
    • Kürzeste Pfade:
      • Kürzester st-Pfad
      • Kürzeste s-Pfade (von s zu allen Knoten)
      • Kürzeste Distanzen zwischen allen Knotenpaaren
    • Finden negativer Kreise in einem Graphen (wird später bei Kostenminimalen Flüssen wiederverwendet)
  • Algorithmen:
    • s-Pfade:
      • Dijkstras Algorithmus + einfache Variationen
      • Bellman-Ford-Algorithmus
      • Unterschied Label-Setting- und Label-Correcting-Algorithmus
    • Distanz zwischen allen Knotenpaaren:
      • naive Implementierung
      • Floyd-Warshall-Algorithmus
  • Übertragungen:
    • Shortest Path als lineares Programm + Dualisierung

Maximale Flüsse

  • Probleme:
    • Maximaler Fluss
    • Minimaler Schnitt
  • Algorithmen:
    • Ford-Fulkerson-Algorithmus
    • Edmonds-Karp-Implementierung
    • Preflow-Push-Algorithmus (Goldberg-Tarjan)
    • FIFO-Implementierung des Preflow-Push
  • Definitionen:
    • Fluss mit seinen Bedingungen (Flow Conservation und Capacity Constraints)
    • Preflow mit seinen Bedingungen (Preflow Condition und Capacity Contraints)
  • Konzepte:
    • Max-Flow-Min-Cut-Dualität
    • “Zertifikat” für Optimalität (Eventuell wird das auch erst in einem späteren Kapitel so genannt, aber zum ersten Mal kommt es in diesem Kapitel vor. Ford-Fulkerson liefert nach Laufzeitende den minimalen Schnitt, welcher als Beweis für Optimalität gesehen werden kann, wenn die Größe des Schnitts gleich der größe des Flusses ist)
  • Übertragungen:
    • Max-Flow-Min-Cut als lineares Programm
    • Preflow-Push als dualer Algorithmus

Kostenminimale Flüsse

  • Probleme:
    • Kostenminimaler Fluss
  • Algorithmen:
  • Konzepte:
  • Beweishilfsmittel (vgl. auch Columbia University, S. 5-8)
    • Circuit Optimality
    • Reduced Cost Optimality
    • Complementarity
  • Übertragungen:
    • Primal-Dualer Algorithmus verwendet zur Lösung Maximalen Fluss im Netzwerk der Kanten mit reduzierten Kosten gleich Null
    • Kürzeste Wege Problem kann über das lineare Programm von Min-Cost-Flow gelöst werden, wenn man den Bedarf an Quelle auf -1 und am Ziel auf +1 setzt (Folien Studientag)
    • Max-Flow-Problem kann mit Min-Cost-Flow gelöst werden, wenn man alle Kosten auf 0 setzt, den Bedarf auf 0 und eine Kante von t nach s mit Kosten -1 und unendlicher Kapazität einführt (Folien Studientag)

Matching

  • Probleme:
    • Matching
    • Bipartites Matching
    • Minimum Vertex Cover
  • Algorithmen:
  • Konzepte:
    • M-augmentierende Pfade
    • System of Distinct Representatives
    • Hypomatchable Graphs
    • Blüten von Graphen
    • Dualität im bipartiten Fall: Matching / Vertex-Cover
    • Dualität für allgemeine Graphen: Matching / Gallai Edmonds Decomposition (Tutte-Berge Formula)
  • Beweishilfsmittel:
    • Satz von König (1931)
    • Hall-Theorem (1935)
    • Hochzeitstheorem von Frobenius (1917)
  • Übertragungen:
    • Maximales bipartites Matching als Maximaler Fluss

Gewichtetes Matching

  • Probleme:
    • Bipartites gewichtetes Matching
    • Inverse Minimum Spanning Tree
    • Nicht-bipartites gewichtetes Matching
    • Briefträgerproblem (Chinese Postman Problem)
  • Algorithmen:
    • WeightedBipartiteMatching
    • WeightedMatching
    • Ungarische Methode
  • Konzepte:
    • Gallai-Edmonds Decomposition
  • Übertragungen:
    • Bipartites Matching als lineares Programm (im Polyhedron)
    • Zusammenhang Successive Shortest Paths (Kostenminimale Flüsse) und bipartites Matching
    • Nicht-bipartites Matching als lineares Programm
I do not maintain a comments section. If you have any questions or comments regarding my posts, please do not hesitate to send me an e-mail to blog@stefan-koch.name.