Algorithms and Complexity

Skriptum "Graphen und Algorithmen"

Wir freuen uns, eine vorläufige Fassung unseres Skriptums

[ca. 450 Seiten] online zur Verfügung stellen zu können, und hoffen auf zahlreiche Kommentare, Anregungen und Verbesserungsvorschläge.

Aufgrund der grossen Nachfrage sind die folgenden Files auch in gepackter Form über ftp vom ftp-Server lux.informatik.hu-berlin.de im Verzeichnis pub/C4/ga erhältlich (als UserName gebe man "anonymous" an, als Passwort seine E-mail-Adresse).

Es gibt eine interessante WWW-Seite mit Links zum Thema "Graphen".

Digitale Kopien oder Ausdrucke der hier zur Verfügung gestellten Dateien oder Teile davon sind kostenlos für den privaten Gebrauch oder die Lehre - nicht aber für kommerzielle Zwecke. Bei neuen Kopien muß das Copyright erkennbar sein. Auch auszugsweise Verwendung nur unter Angabe der Quelle.

---

Inhalt

Inhaltsverzeichnis

Vorwort

Notation

1 Einführung

(51 Seiten, 656kB)

1.1    Grundlegende Begriffe
1.1.1  Partite Graphen
1.1.2  Operationen auf Graphen
1.1.3  Bäume, Artikulationen, Schnitte
1.1.4  Zufällige Graphen
1.2    Die Komplexität von Algorithmen
1.2.1  Entscheidbarkeit
1.2.2  Die Klasse P oder: zugängliche Probleme
1.3    Algorithmische Prinzipien
1.3.1  Breiten- und Tiefensuche
1.3.2  Dynamisches Programmieren: das kürzeste-Wege-Problem
1.3.3  Greedy: minimale aufspannende Bäume
1.4    Die Klasse NP oder: polynomielle Verifizierbarkeit
1.4.1  NP-Vollständigkeit
1.4.2  NP-schwere Probleme und Optimierung
1.5    Zum Umgang mit NP-schweren Problemen: Algorithmen für Independent Set

2 Netzwerkflüsse und Zusammenhang

(22 Seiten, 569kB)

2.1    Der Markierungsalgorithmus von Ford und Fulkerson
2.2    Der Satz von Menger nebst Folgerungen
2.3    2-Zusammenhang, Blockstruktur und Tiefensuche
2.4    Die Zusammenhangszahlen

3 Durchlaufbarkeit

(13 Seiten, 323kB)

3.1    Eulersche Graphen
3.2    Hamiltonsche Graphen

4 Matching

(34 Seiten, 500kB)

4.1    Die Sätze von Berge und Gallai
4.2    Matching in bipartiten Graphen
4.3    Matching in allgemeinen Graphen

5 Färbung

(39 Seiten, 1076kB)

5.1    Die chromatische Zahl
5.2    Greedy-Färbung und der Satz von Brooks
5.3    Chromatische Zahl und Taillenweite
5.4    Die Komplexität des Färbungsproblems
5.5    Färbungsalgorithmen
5.6    Kantenfärbung: der Satz von Vizing
5.7    Kantenfärben in bipartiten Graphen

6 Topologische Graphentheorie

(58 Seiten, insgesamt 3.886kB, Teil 1, Teil 2, Teil 3, Teil 4)

6.1    Planare Graphen
6.1.1  Ebene Graphen
6.1.2  Die Eulersche Formel
6.1.3  Die Sätze von Kuratowski und Wagner
6.1.4  Dualität bei planaren Graphen
6.2    Ein Einbettungsalgorithmus [Fragment]
6.3    Die 4-Farben-Vermutung
6.4    Graphen höheren Geschlechts
6.5    Der 4-Farben-Satz und Komplexitätsfragen
6.6    Kreuzungszahl, Dicke, Arborizität und Buchdicke

7 Perfekte Graphen

(23 Seiten, 314kB)

7.1    Einleitung
7.2    Chordale Graphen
7.3    Vergleichbarkeitsgraphen
7.4    Intervallgraphen [Fragment]
7.5    Graphen mit perfekter Ordnung [Fragment]
7.6    Im Umfeld der Perfekte-Graphen-Vermutung [Fragment]
7.7    Optimierung auf perfekten Graphen [Fragment]

8 Separatoren

(22 Seiten, 569kB)

8.1    Einleitung
8.2    Separatoren in planaren Graphen
8.3    Independent Set auf planaren Graphen
8.4    Separatoren für andere Graphenklassen
8.5    Cliquenseparatoren

9 Baumweite

(10 Seiten, 206kB)

9.1    Baumweite und k-Bäume
9.2    Optimierung auf Graphen beschränkter Baumweite
9.3    Randomisierung I: Subgraph Isomorphismus [Fragment]

10 Approximationsalgorithmen

(42 Seiten, 1067kB)

10.1   Einleitung
10.2   Knotenüberdeckung
10.3   Steiner-Bäume
10.4   Das Traveling Salesman Problem
10.5   Das Zentrumsproblem
10.6   Randomisierung II: Max Cut und Max Sat
10.7   Lokale Verbesserung
10.8   Ein PAS für Planar Independent Set
10.9   Graph Coloring und Independent Set

11 Nicht-Approximierbarkeit

(2 Seiten, 86kB)

11.1   MAX-SNP und PCP [Fragment]
11.2   Clique [Fragment]
11.3   Graph Coloring [Fragment]

12 Überdeckungsprobleme

(29 Seiten, 427kB)

12.1   Cliquenüberdeckung und Schnittgraph-Darstellung
12.2   Erkennung von Linegraphen [Fragment]
12.3   Primal-dual Approximationsalgorithmen
12.3.1 Der primal-dual Algorithmus der Linearen Optimierung
12.3.2 Hitting Set, Node Cover und Dominating Set
12.3.3 Shortest Path
12.3.4 Das Generalized Steiner Tree Problem
12.3.5 Survivable Network Design mit Mehrfachkanten
12.4   Approximation von Set Cover und Dominating Set

13 Zufällige Graphen und probabilistische Algorithmen

(16 Seiten, 273kB)

13.1   Die Cliquenzahl
13.2   Die chromatische Zahl

14 Ein Blick in die extremale und asymptotische Graphentheorie

(14 Seiten, 669kB)

14.1   Die Sätze von Turan und von Erdös und Stone
14.2   Fast alle dreiecksfreien Graphen sind bipartit
14.3   Mehr über dreiecksfreie Graphen

A Anhang

(20 Seiten, 255kB)

A.1    Grundbegriffe der Wahrscheinlichkeitstheorie
A.2    Hinweise und Lösungen zu ausgewählten Übungen
A.3    Die Grenze zwischen P und NP-vollständig
A.4    Übersicht über Graphenparameter
A.5    Weiterführende Literatur

Literaturverzeichnis

(46 Seiten, 335kB)

---

last modified 10/26/05 (alkox-www)