Proseminar Graphentheorie, WS 2011/12
Termin und Ort:
Mo. 12:00 bis 14:00 Ernst-Abbe-Platz 2 - R 3517
Am der erste Sitzung ist
nähere Besprechung der Themen und Verteilung der Literatur geplant.
Spielregeln:
Der Vortrag soll frei an der Tafel gehalten werden. Spickzettel sind erlaubt,
aber es darf nicht von Zetteln auf die Tafel abgeschrieben werden.
Auch Folien und Beamer sind nur für Graphiken erlaubt, Folienvorträge oder
Powerpointpräsentationen sind verboten.
Das Ziel und die Schwierigkeit der Übung bestehen darin, Ihren Komilitonen
etwas verständlich zu machen und nicht etwa mich zu überzeugen, daß Sie
Ihr Kapitel mehr oder weniger verstanden haben.
Es wird nicht erwartet, daß Sie Ihre Doppelstunde voll ausschöpfen. Bei
vielen Themen scheint mir ein Vortrag von etwa einer Stunde viel eher
angemessen. Es soll ja auch noch Zeit für Zwischenfragen und Diskussion bleiben.
Ich muß die Vortage benoten. Regt ein Vortrag überhaupt keine Fragen
oder Diskussionen an, so wird es mir schwerfallen, ihn besser als mit
2,0 zu benoten. Gewinne ich den Eindruck, dass der Vortragende den Vortrag
nicht ernsthaft vorbereitet hat oder im Wesentlichen nicht
verstanden hat, so sind Sie durchgefallen. In der Regel ist aber Proseminar eine gute Möglichkeit, die
Durschnittnote zu verbessern
Die wesentliche Leistung ist der Vortrag, aber die Fairness gebietet, daß Sie sich auch
als Versuchskarnickel zum Anhören und Verstehen von Vorträgen zur Verfügung stellen.
Ich will hier kein formales Quorum aufstellen, aber der Besuch von mindestens zehn Vorträgen
neben dem eigenen, egal zu welchem Termin, scheint mir jedenfalls nicht zu viel verlangt.
Selbstverständlich können Sie Ihr Vortrag vorher mit mir besprechen; bzw. von mir die
mathematische Hilfe bekommen.
Wie halte ich einen Seminarvortrag? (von Manfred Lehn)
Liste
der Themen:
1. (ein Vortrag) Bäume und der Satz von Cayley (Vortragende: Frank Nussbaum)
Definition von Graphen, Bäumen, numerierten
Bäumen.
Satz von Cayley:
Anzahl der numerierten Bäume mit $n$ Ecken ist n^{n-2}.
Beweis über „Wirbeltiere“.
Literatur: Cameron 3.10 (S.38f), 4.5
(S.60f); DAS-Skript Satz 8.3, Satz 3.3; Aigner2
(S.132).
2. (zwei
Vorträge) Der Heiratssatz (Vortragende:
Oliver Siebert)
Bipartite Graphen. Halls "Heiratssatz" mit
Beweis. Paarungszahl = minimale Mächtigkeit einer Eckenüberdeckung mit Beweis.
Anwendungen: Konstruktion lateinischer Quadrate; gemeinsame Transversale in
Gruppen, Auswahlfunktionen, etc. Anzahl
paarweise orthogonaler lat. Quadrate:
Literatur: Cameron Abschnitt 6.6, insb. 6.6.1--6.6.4.
Cameron 6.1--6.3 (S.97--91), 14.8
(S.243); DAS-Skript Satz 9.2--9.4; Aigner2 7.1 (S.120f).
3. (zwei
Vorträge) Wege auf den Graphen. (Vortragenden: Ilka Wirgenings
und Sabine Stück)
Eulersche Wege. Kurtzeste
Wege und minimale aufgespannte Bäume.
Das Problem des Handlungsreisenden.
Literatur: K. 6 Aigner1, K.7 Aigner2, Nitsche, Diestel, Berger
4. (ein Vortrag; eventuell 2
Vorträge) Der Satz von Ramsey (Vortragende: Selma Metzner)
Ramseys Satz für zweigefärbte endliche
vollständige Graphen mit Beweis.
Induktion auf beliebig viele Farben.
Eventuell einige konkrete Zahlen
oder eine Abschätzung. Eventuell
Anwendungen (Satz von Schur) Unendliche
Version erwähnen
(eventuell mit Anwendung)
Literatur: Cameron 10.2--10.5 (S.149ff); DAS-Skript Satz 7.5.
5.
(drei Vorträge) Der Fünf--Farben--Satz und Plattbarkeit
(Vortragende: Stefan Engelhardt)
Planare Graphen
(Einbettung in Ebene oder auf Sphäre ist äquivalent). Eulersche Polyederformel mit Beweis.
Fünf--Farben--Satz mit Beweis. Algorithmus am Beispiel ausführen. Zweifärbbarkeit = bipartit.
Eventuell Dreifarbensatz. (alles ein
Vortrag)
Plättbarkeit:
der Satz von Kuratowski mit Beweis (zwei
Vorträge) .
Literatur:
Cameron S.300 + 18.7 (S.304); Diestel, Mathworld.
5´. Die
Museumswächter und 3-Farben Satz . (Vortragende: Jannis Koberstein)
Literatur:
Das Buch der Beweise (Aigner,
Ziegler)
6. (zwei Vorträge) Gerichtete Graphen.
Flüsse in Netzwerken. (Vortragenden: Nina Bartelmeß und Jula McGibbon)
Paradoxon des Sportreporters. Satz von Ford--Fulkerson
mit Beweis. Algorithmus mit Beispiel.
Heiratssatz als Korollar.
Literatur: Nitzsche,
Diestel, Cameron 11.9 (S.173--176), + S.178; DAS-Skrip
Satz 9.6; Aigner 7.3 (S.130--134).
7.
(ein Vortrag) Moore--Graphen (Vortragende:
Stefan Neumann)
Reguläre Graphen, Durchmesser,
Moore--Graphen.
Beispiele der bekannten Moore--Graphen
bis auf Hoffman--Singleton.
Beweis, daß
für Durchmesser 2 nur die Verzweigungsgrade 2,3,7,57 möglich sind.
Literatur: Gesondertes
Blatt; Artikel von Hoffman \& Singleton, Cameron 11.12 (S.181--184)
8. Der Hoffman—Singleton—Graph
(Vortragende: Melchior Wirth)
S^n, innere
und äußere Automorphismen. Konstruktion des
Hoffman--Singleton--Graphs aus einem äußeren Automorphismus
der $S_6$.
Literatur: Cameron 11.12 über Moore--Graphen;
paper von Manfred Junker; Gruppen--Skript Satz 29 über
$ Out(S_6)$.
9. (zwei Vorträge) Polytopen
und Graphen: (Vortragenden: Aaron Puchert)
Der Starrkeitssatz
von Cauchy, Satz von Balynski
Literatur: Das Buch der Beweise (Aigner,
Ziegler), Kap. 12. Ziegler, Lectures about polytopes 3.5
Literatur:
Die Bücher (außer „Der Buch der Beweise“ und Berge) stehen im Semesterapparat in der Bibliothek,
d.h., sie sind von der Ausleihe gesperrt.
- Peter Cameron "Combinatorics"
Cambridge University Press.
- Martin Aigner1 „Graphentheorie: Eine Entwicklung aus dem $4$-Farben
Problem “
Martin Aigner2 "Diskrete Mathematik" Vieweg.
- Manfred Nitzsche „Graphen für Einsteiger“ (zurzeit
als google-book verfügbar)
- Reinhard Diestel „Graphentheorie“
Springer-Lehrbuch
- Skripten DAS
(von Markus Junker), Gruppen
(von Markus Junker)
- Claude Berge “The
theory of graphs”.
- Alle möglichen anderen
Bücher über Graphentheorie,
Kombinatorik oder diskrete Mathematik; internet
22. Sept 2011 Vladimir Matveev