"Perfekte Graphen 001.ps.gz" - читать интересную книгу автора

Graphenalgorithmen:

Perfekte Graphen

Teilnehmerskript zu einer Vorlesung

von Stefan Felsner im Wintersemester 1995/96 an der Freien Universit"at Berlin

3. April 1996

Dieses Skript wurde als "Ubung von den Teilnehmern der Vorlesung erstellt. Ich habe jedes Kapitel um einen Abschitt erweitert in dem die Quellen und weiterf"uhrende Literatur angegeben werden. Obwohl ich die Mitschriften korrekturgelesen habe sind sie h"ochstwahrscheinlich nicht v"ollig fehlerfrei. Wir hoffen, dass das Skript dem Leser trotz all seiner M"angel von Nutzen sein wird.

Stefan Felsner

Die Teilnehmer und die von ihnen betreuten Vorlesungen

Bernd Falkenberg 11, 19 Carola Wenk 5, 17 Carsten Ihlemann 9, 16 Christof Schultz 6, 18 Clemens Hendler 8, 15 Falk Haferkorn 3, 13 Helmut Weil 4, 14, 22 Johannes Schwarz 12, 21 Stefanie Gerke 2, 10 Susanne Gebauer 7, 20

INHALTSVERZEICHNIS 1 Inhaltsverzeichnis 1 Graphen und F"arbungen 3

1.1 Definitionen und Beispiele . . . . . . . . . . . . . . . . . . . . . 3 1.2 Drei Anwendungen von F"arbungen . . . . . . . . . . . . . . . . 6

2 Gerichtete Graphen und Ordnungen 9

2.1 Gerichtete Graphen . . . . . . . . . . . . . . . . . . . . . . . . . 9 2.2 Ordnungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 2.3 Intervallgraphen und Intervallordnungen . . . . . . . . . . . . . 13 2.4 Perfekte Graphen . . . . . . . . . . . . . . . . . . . . . . . . . . 16

3 Algorithmen und Graphen 17

3.1 Definitionen und ein Beispiel . . . . . . . . . . . . . . . . . . . . 17 3.2 Datenstrukturen f"ur allgemeine Graphen . . . . . . . . . . . . . 20 3.3 Depth-First-Search . . . . . . . . . . . . . . . . . . . . . . . . . 22 3.4 Eigenschaften von DFS . . . . . . . . . . . . . . . . . . . . . . . 27

4 Problemklassen und Komplexit"at 30

4.1 Die Problemklasse N P . . . . . . . . . . . . . . . . . . . . . . . 31 4.2 Polynomielle Transformationen . . . . . . . . . . . . . . . . . . 33 4.3 NP-vollst"andigkeit und das SAT Problem . . . . . . . . . . . . . 33 4.4 Das Vertex Cover Problem . . . . . . . . . . . . . . . . . . . . . 34

5 Einige Klassen O/-perfekter Graphen 39

5.1 Bipartite Graphen . . . . . . . . . . . . . . . . . . . . . . . . . 39 5.2 Komplemente von bipartiten Graphen . . . . . . . . . . . . . . 39 5.3 Line Graphen von bipartiten Graphen . . . . . . . . . . . . . . . 41 5.4 Komplemente von Line-Graphen bipartiter Graphen . . . . . . . 43