Nächste Seite:
Überblick
Graphen und Netzwerke
Vorlesung, Wintersemester 2004
Johannes Waldmann, HTWK Leipzig
Überblick
Motivation
Inhalt
Organisation
Leistungsnachweise:
Literatur
GraphViz, die Dot-Notation
Definitionen, Bezeichnungen
Graphen
Beispiele
Standard-Bezeichungen
Graphen-Operationen
Isomorphien
Selbskomplementäre Graphen
Aufgaben zum Petersen-Graph
Graphen-Parameter, Färbungen
Teilgraphen
Einfache Graphen-Parameter
Knoten-Färbungen
Parameter-Abhängigkeiten
Greedy-Algorithmen
Greedy-Algorithmus zur Graphenfärbung
Eine Schranke für die chromatische Zahl
Darstellung von Graphen
Planare Graphen
Definitionen
Kreuzungszahl
Der Eulersche Polyedersatz
Folgerungen
Färbungen von planaren Graphen
Wege, Zusammenhang, Bäume
Wege
Wege -- Aufgaben
Zusammenhang, Komponenten
Mehrfacher Zusammenhang
Abstand, Durchmesser, Radius
Bäume
Botanik
Bäume
Gradsequenzen
Graceful Labelings
Graphen und Spiele: Havannah
Havannah--Theorie
Havannah--Challenge
Tiefensuche (rekursiv)
Tiefensuche (iterativ)
Tiefensuche (II)
Tiefensuche auf ungerichteten Graphen
Kreise finden
Zweifach zusammenhängende Komponenten
Zweifach zusammenhängende Komponenten (II)
Gerüste (spanning trees)
Shannon Switching Game
Shannons Heuristik: Widerstandsnetzwerk
Lehmanns exakte Lösung
Minimale Gerüste
MST-Algorithmus von Jarnik, Prim, Dijkstra
MST: Prim, Korrektheit
MST: Prim: Datenstrukturen
Binomial-Heaps: Definition
Binomial-Heaps: Operationen
Matchings und Faktoren
Matchings
Satz von Berge
Satz von Hall
Vertex Cover, Domination
Satz von König
Flüsse
Definitionen: Netzwerke
Definitionen: Flüsse
Das Maximalfluß-Problem
Schnitte
Kapazitäten von Schnitten und Flüssen
Flußvergrößernde Wege
Maximalflüsse
Algorithmus von Ford und Fulkerson
Verbesserungen
Komplexität
Motivation
Turingmaschinen
Beschränkte Maschinen
Komplexitätsklassen
die Klassen P und NP
Reduktion, Vollständigkeit
Beispiele für NPC
Vertex Cover etc.
3-Färbbarkeit
Chordale Graphen
Separatoren
Simpliziale Knoten
Perfect elimination schemes
Perfektion
partielle
k
-Bäume
Algorithmen für
k
-Bäume
Baumweite
Reihen-/Parallel-Graphen
Independent Set für
G
mit beschr. Baumweite
Algorithischer Nutzen der Baumweite
Über dieses Dokument ...
Johannes Waldmann 2005-01-25
