Graphentheorie SoSe 2003

Graphentheorie - Sommersemester 2003

Vorlesung: Di, Do 12:00 c.t., Arnimallee 2-6, Raum 031 (geändert !)
Übung: Fr 10-12, Hörsaal 005, Informatikgebäude
Übungsleitung: Anja Krech

Ankündigung [ps][pdf]

Abschlußklausur - Lösungen [ps]

Allgemeines

Die Übungsaufgaben werden in der Vorlesung bekannt gegeben. Es gibt keine Übungsblätter.
Übungsaufgaben die in der n-1.ten Woche am Donnerstag, und in der n.ten Woche am Dienstag gegeben wurden, sind am Donnerstag der n+1.ten Woche in der Vorlesung abzugeben.
Aufgrund der geringen Ausstattung mit Tutoren und Assistenten und der Teilnehmerzahl von 50 Personen gibt es ab sofort Doppelabgabe für die Übungszettel. Ferner wird es eine Klausur zum Semesterabschluß geben.
Die Übungsaufgaben können in Gruppen bearbeitet werden, müssen jedoch von jeder Zweiergruppe einzeln in eigenen Worten niedergeschrieben werden.
Der letzte offiziell in die Wertung eingehende Zettel ist am 10.7. abzugeben. Der darauffolgende Zettel ist freiwillig.
Die Scheinkriterien sind: mindestens 60 Prozent auf den Übungszetteln insgesamt, und Bestehen der Abschlußklausur.

Was geschah wann in der Vorlesung?

Datum	Themen	Aufgegebene Übungen	Abzugebende Übungen
15.4.2003	Graphen - erste Einsichten	1.-4.
17.4.2003	Bäume - Charakterisierungen	5.-8.
22.4.2003	Aufspannende Bäume, Bipartite Graphen und Matchings	9.
24.4.2003	Satz von Hall und Matchingzahl in bipartiten Graphen allgemein	10.,11.	1.-4.
29.4.2003	Min/Max-Theoreme für bipartite Graphen, Charakterisierung bipartiter Graphen	12.,13.
2.5.2003	---	---	5.-9. vor der Übung
6.5.2003	Der Satz von Tutte über perfekte Matchings, gerichtete Graphen, Wegeüberdeckungen	14.,15.
8.5.2003	---	---	10.-13.
13.5.2003	Der Satz über Wegeüberdeckungen, Dilworths Theorem	16.-18.
15.5.2003	Ebene und planare Graphen	19.,20.	14.,15.
20.5.2003	Zyklen- und Schnittraum eines Graphen	21.-23.
22.5.2003	Zyklen- und Schnittraum eines Graphen	24.-26.	16.-18.
27.5.2003	Der Satz von MacLane	27.,28.
30.5.2003	---	---	19.-23. vor der Übung
3.6.2003	k-Zusammenhang, Blockgraph, Ohrenzerlegung	29.-32.
5.6.2003	Mengers Theorem	33.	24.-28.
10.6.2003	Färbung von Graphen, 5-Farbensatz, Satz von Brooks	34.-37.
12.6.2003	Chromatische Zahl der Knesergraphen	38.,39.	29.-32.
17.6.2003	Perfekte Graphen, Lovasz Theorem	40.-42.
19.6.2003	Das chromatische Polynom	43.,44.	33.-37.
24.6.2003	Eigenwerte der Adjazenzmatrix und Graphenparameter	45.-47.
26.6.2003	Die Laplacematrix eines Graphen und das Matrix-Baum Theorem		38.-42.
1.7.2003	Joyals Bijektion für die aufspannenden Bäume des vollständigen Graphen. Einführung in die Probabilistische Methode	48.-51.
3.7.2003	Die Probabilistische Methode in Aktion		43.-47.
8.7.2003	Taillenweite und chromatische Zahl; Eigenschaften fast aller Graphen	52.-55.
10.7.2003	Die Kreuzungszahl, Zusammenfassung der Vorlesung, Fragestunde		48.-51.
15.7.2003	Abschlußklausur (Lösungen [ps])		52.-55.
17.7.2003	Letzte Einsichten und Scheinvergabe

Mark de Longueville

Last modified: Fri Feb 20 18:25:57 CET 2004