Graphen und Algorithmen

Knotenfaerbung, Satz von Brooks, Algorithmus von Welsh-Powell und Matula-Marble-Isaacson, Kritische Graphen, Satz von Dirac und Folgerungen, Cliquen, Satz von Mycielski

Vorlesung 7

Jan 23rd, 2008 1h 23m

Satz von Berge, Heiratsproblem, Heiratssatz von Hall, Matchings in bipartiten Graphen, Ungarische Methode, Algorithmus von Kuhn-Munkres, Loesung des chinesischen Postbotenproblems, 1/2-Approximationsalgorithmus fuer das TSP von Christofides

Vorlesung 6

Dec 19th, 2007 2h 21m

Satz von Euler und Hierholzer, Algorithmus von Fleury, Problem des chinesischen Brieftraegers, Satz von Dirac, Satz von Bondy-Chvatal, Satz von Grinberg, Problem des Handlungsreisenden

Vorlesung 5

Dec 12th, 2007 40m 8s

Bruecke, Zerlegungsknoten, mehrfacher Knoten- und Kantenzusammenhang, trennende Knoten- und Kantenmengen, Satz von Whitney, Satz von Menger (Knoten- und Kantenversion), verallgemeinerter Satz von Whitney (Knoten- und Kantenversion)

Vorlesung 4

Nov 28th, 2007 2h 4m

Flussnetze, Maximalfluss-Problem, Minimalschnitt-Problem, Max-Flow-Min-Cut-Theorem, Algorithmus von Ford-Fulkerson, Varianten von Edmonds-Karp und Dinits, Praefluesse, Algorithmus von Goldberg-Tarjan

Vorlesung 3

Nov 14th, 2007 1h 25m

Kuerzeste Wege, Algorithmus von Dijkstra, Algorithmus von Shimbel (Moore-Bellman-Ford), negative Kreise, Algorithmus von Floyd-Warshall, minimax-Wege, Steinerbaeume, Algorithmus von Lawler