Graphentheorie, SS 2001

Im Gegensatz zur Ankündigung im KVV findet die Vorlesung 4-stündig statt, nicht 3-stündig.
 

Übungsaufgaben
Übersicht über Ziele und Inhalt der Vorlesung

Das Buch von R. Diestel, Graphentheorie, kann man auch on-line betrachten oder herunterladen (aber nicht ausdrucken, etwa 3MByte). Es gibt auch eine lokale Kopie an der FU Berlin (Stand 17. April 2001).

Inhalt

• 17. April 2001
  Übersicht, Begriffe und Definitionen, Grad, Isomorphie, Teilgraphen, induzierte Teilgraphen
• 19. April 2001
  Wege und Zusammenhang, Charakterisierung von Bäumen
• 24. April 2001
  Spannbäume, Eulersche Graphen, bipartite Graphen
  Begriffe: Durchmesser, Radius, zentrale Knoten, Umfang, Taillenweite
• 26. April 2001
  Charakterisierung bipartiter Graphen, Paarungen, Charakterisierung größter Paarungen (Satz von Berge), Knotenüberdeckungen, Satz von König
  Begriffe: regulär, kubische Graphen, Faktor
• 3. Mai 2001
  Heiratssatz
• 8. Mai 2001
  Satz von Tutte, Satz von Petersen über Paarungen in brückenlosen kubischen Graphen
• 10. Mai 2001
  Kantenfärbungen (Faktorisierung) von bipartiten Graphen, lateinische Quadrate, doppeltstochastische Matrizen
• 15. Mai 2001
  Mehrfacher Zusammenhang, Blöcke, Ohrenzerlegung, Satz von Menger
• 17. Mai 2001
  Der Satz von Menger und der Satz von König
• 22. Mai 2001
  Struktur 3-zusammenhängender Graphen. Planarität, Eulersche Polyederformel
• 29. Mai 2001
  Minoren, duale Graphen
  Charakterisierungen planarer Graphen durch Kuratowski und Wagner.
• 31. Mai 2001
  Kantenraum; orthogonale Zerlegung in Zyklen- und Schnittraum;
• 5. Juni 2001
  Inzidenz- und Adjazenzmatrix; schlichte Kreisbasen, Satz von MacLane; kombinatorische Dualität, Satz von Whitney;
• 7. Juni 2001
  maximale planare Graphen, Kreispackungen, Satz von Koebe-Andrejew-Thurston, Zeichnungen mir geraden Kanten
• 12. Juni 2001
  kombinatorische Einbettungen, Orientierbarkeit und Flächen höheren Geschlechts, Eulercharakteristik. Eindeutige Einbettung dreifach zusammenhängender Graphen (nur skizziert).
• 14. Juni 2001
  Färbungen, Satz von Heawood über eingebettete Graphen (nur obere Schranke)
  Greedy-Algorithmus zum Färben, Gradschranken, Bestimmung des maximalen Minimalgrades aller Untergraphen, Satz von Brooks
• 19. Juni 2001
  Fünffarbensatz für planare Graphen (Kempe-Ketten)
  Listenfärbungen, Listenfärbungen für planare Graphen (Satz von Thomassen)
  Konstruktion k-chromatischer Graphen: k-konstruierbare Graphen, Satz von Hajós
• 21. Juni 2001
  Kantenfärbungen, Kantenfärbungen in bipartiten Graphen (Satz von König), Satz von Vizing, chromatisches Polynom
• 26. Juni 2001
  Hadwiger-Vermutung, perfekte Graphen
• 28. Juni 2001
  Perfekte Graphen: Intervallgraphen, chordale Graphen, simpliziale Ecken, perfekte Eliminationsordnung.
• 3. Juli 2001
  Flüsse in Netzen, Kapazitäten, Max-Fluss-Min-Schnitt-Satz, Algorithmus von Ford und Fulkerson.
• 5. Juli 2001
  Rundflüsse (Zirkulationen), Schnittraum und Flussraum.
  Anwendung: Optimale Projektauswahl, Modellierung als Schnittproblem.
• 10. Juli 2001
  Graphen und Gelenkswerke; starr, infinitesimal starr, und kombinatorisch (generisch) starr. Isostatische Gelenkswerke.
  Überdeckung eines Multigraphen durch Bäume, Satz von Nash-Williams.
• 12. Juli 2001
  Isostatische Graphen: Äquivalenz der Dichtebedingung (Satz von Laman) mit den Henneberg-Konstruktionen.
  Starrheitsmatrix, Rang 2n-3, Notwendigkeit der Laman-Bedingungen.
• 17. Juli 2001
  Die Henneberg-Konstruktion liefert (generisch) starre Graphen. Starre Graphen im Raum.
• 19. Juli 2001
  Extremale Graphentheorie: Satz von Turán über K_r-freie Graphen, Satz von Kövári, Sós, und Turán über K_r,s-freie Graphen

ursprünglich geplanter Inhalt

• Flüsse und Schnitte
  • Rand und Korand, Anzahl der Eulerschen Teilgraphen
• Zusammenhang und Graphenzerlegung
  • Ohrenzerlegung, s-t-Nummerierung
• planare Graphen, Kreuzungszahl
  • Schnyder-Einbettungen
• Färbungen
  • Graphenhomomorphismen
  • Tutte-Polynom (Verallgemeinerung des chromatisches Polynoms)
• Minoren
• Hamiltonkreise
• Matrix-Baum-Satz
• elektrische Netze und Irrfahrten