| Dokumente | |
|
Dokumentvorschau |
Graphentheorie |
Dokument-Nr.: F-AART |
|
|
Dokument-DownloadUm Zugriff auf dieses Dokument zu erhalten, musst Du Mitglied der UNIDOG Community sein. |
|
Inhalt / Beschreibung
Der komplette klausurrelevante Stoff der Vorlesung "Graphentheorie". Note des Autors: 1,7 Die Zusammenfassung wurde mit LaTeX erstellt. Inhalt: 0 Vorwort 1 Einführung in die Graphentheorie 1.1 Ungerichtete Graphen 1.2 Gerichtete Graphen 1.3 Bäume, Wälder und Gerüste 2 Eulertouren 3 Grundlegende Algorithmen und Komplexitätstheorie 3.1 Topologische Sortierung und Traversieren von Graphen 3.2 Einführung in die Komplexitätstheorie 4 Hamiltonkreise und Turniere 4.1 Hamiltonkreise 4.2 Turniere 5 Minimale Spannbäume, Matroide und Steinerbäume 5.1 Das Minimale Spannbaumproblem 5.2 Die Färbungsmethode von Tarjan 5.3 Steinerbäume 6 Matchings, Faktoren und Flüsse 6.1 Matchings 6.2 Faktoren 6.3 Flüsse 7 Färbungen, perfekte und planare Graphen 7.1 Färbungen 7.1.1 Knotenfärbungen 7.1.2 Kantenfärbungen 7.1.3 Listenfärbungen 7.2 Perfekte Graphen 7.2.1 Einführung in perfekte Graphen 7.2.2 Zerlegungsstrukturen perfekter Graphen 7.3 Planare Graphen 8 Ramseytheorie 9 Appendix I: Ausgewählte Probleme 9.1 XCOVER 9.2 SAT 9.3 3SAT 9.4 CLIQUE, VC, IS 9.5 SUBSETSUM 9.6 MST, MDST, MLST 9.7 3-COL 10 Appendix II: Ausgewählte Algorithmen 42 10.1 Eulertour 10.1.1 Algorithmus von Fleury 10.2 Kürzeste Wege in gewichteten Graphen 10.2.1 Algorithmus von Floyd-Warshall 10.2.2 Algorithmus von Dijkstra 10.2.3 Chinesisches Briefträgerproblem 10.3 Das Minimale Spannbaumproblem (MST) 10.3.1 Färbungsmethode von Tarjan 10.3.2 Algorithmus von Kruskal 10.3.3 Algorithmus von Prim 10.4 Knotenfärbung 10.4.1 Algorithmus von Brook Index |
|
Vorschau-Ausschnitte
|
|||||||
