Seminar
Graphentheorie online, WS 2021/22
Wie alles organisiert wird, was Sie machen müssen und
wie Ihre Leistung bewertet wird:
(0) In der ersten Sitzung, online, werden wir die
Einzelheiten besprechen bzw.
beantworte ich Ihre Fragen. Ich sende ein Link vorab via Fridolin.
(1) Die Verteilung
der Themen mache ich. Die Liste von
Themen steht unten. Sie bekommen das
Thema mehr oder weniger sofort (erste Vorlesungswoche oder ein bisschen später.)
(2) Sie müssen Ihr Thema perfekt verstehen und eine
Präsentation vorbereiten.
(3) Die Präsentation soll ein Video einer Länge von etwa
40-50 Minuten sein (Abweichungen sind
möglich; bitte aber nicht zu lang und nicht zu kurz).
Sie können selbst die Methode wählen, wie Sie das Video erstellen. Eine einfache Methode ist die Präsentation mit Hilfe von kostenlosen Software ``OBS Studio´´ zu machen. Damit können Sie Videos aufnehmen, aber nicht schneiden und zusammenkleben. Auch dafür geben es mehrere kostenlose Programme. Z. B. Windows und Mac OS Users können Windows Movie Maker verwenden.
(4)
Die Präsentation soll wie ein mathematischer Vortrag aufgebaut und strukturiert
sein. Kurze Einführung,
Definitionen/Sätze/Beweise. In jedem Video soll i.d.R. 2 Beweise
vorkommen (oder ein Beweis, welcher schwierig ist). Auf gar keinen Fall dürfen
Sie Teile aus dem Buch, etwa Bilder oder
Textabschnitte, in Ihre Präsentation direkt kopieren (selbstverständlich
müssen Sie keine neue Beweise entdecken; ich will bloß vermeiden, dass Sie den Vortrag
vorbereiten und über Vortrag nachdenken und nicht nur laut vorlesen, was im
Buch steht).
(5) Sie sollen vorher (voraussichtlich bis zum
14.11) an mir per Email oder via Cloud (Instruktionen kommen) einen
Plan Ihrer Präsentation senden;
wir besprechen ihn individuell per Zoom.
(6)
Die Präsentationen sollen vor 19.12.2021 abgegeben werden (ich sende die
Instruktionen wie). Wir werden sie dann
alle zusammen anschauen. In bestem
Fall (es können rechtliche Hindernisse geben)
bekommt jeder die Präsentationen der anderen und kann die Zeit für
Anschauen selbst wählen. Alle sollen zur
Präsentationen der anderen kurze Notizen
führen (etwa, die Definitionen, die wichtigsten Sätze; sowie die wichtigsten
Schritte des Beweises; eine Seite reicht). Die Notizen sind auch Teil der
Leistung, Sie müssen diese Notizen
einreichen, voraussichtlich bis 12.01.2022.
Die Notizen können auch Kritikpunkte zum Vortrag enthalten.
Diese werde ich sammeln und wenn nötig
anonymisiert an Vortragende weiterleiten.
(7)
Zu jeder Präsentation führe ich, wenn es nötig ist, mit dem Vortragenden ein Gespräch via Zoom.
Ich werde eventuell auch zu den Beweisen in Ihrem Vortrag mathematische
Fragen stellen.
(8)
Eventuell müssen Sie danach die Präsentation verbessern und noch einmal
einreichen; und/oder eine schriftliche Ausarbeitung des Vortrags an mich senden. Wenn ich keine mathematischen Fragen oder Bedenken habe, ist die schriftliche Ausarbeitung nicht nötig.
Nichtverbindliche
Hinweise zu Videoerstellung (wie oben erklärt können Sie eine beliebige Methode benutzen):
Ist
kostenlos, funktioniert unter
Windows/Linux/Mac. Man kann gleichzeitig mehrere Quellen
(etwa
sich selbst, ein .pdf-Datei und eine Whiteboard-Software) zusammen zeigen.
ist
ebenfalls kostenlos. Neuere Versionen erlauben mit der Mouse auf Dateien zu
schreiben.
LaTeX (etwa mit Beamer – documentclass)
liefert sehr gute Ergebnisse für die Vorlage.
Einführungsvideo (zu vorgeschlagener Software)
Rechtlicher Hinweis: Wenn Sie sich gegen unerlaubten Verbreiten von Ihren Präsentation schützen wollen, können Sie den folgenden Text am Anfang der Präsentation zeigen, z.B. auf der ersten Seite der .pdf oder .ppt Datei oder als Untertitel:
„Diese Präsentation enthält möglicherweise urheberrechtlich geschütztes Material. Jede Verwertung, z. B. durch Vervielfältigung oder Weitergabe, ist ohne meine Zustimmung unzulässig und kann Unterlassungs- und Schadensersatzansprüche auslösen.“
Alle Teilnehmer des Proseminars sollen alle Vorträge aktiv (d.h., Notizen führen) anschauen. Es wird einfacher, wenn alle Studierenden alle Präsentationen herunterladen könnten und selbst die Zeit auswählen, wenn Sie sie anschauen wollen. Dafür brauche ich eine Einverständniserklärung, etwa in der Form:
``Ich bin damit einverstanden, dass alle Teilnehmer des Seminars Graphentheorie meine Präsentation (Titel) herunterladen und anschauen. (Unterschrift)‘‘. Wir werden die Einverständniserklärung erst in November benötigen.
Wenn Sie keine Einverständniserklärung geben wollen, werden wir Ihre Präsentation alle zusammen über z.B. Zoom anschauen.
Nichterteilen der Einverständniserklärung bedeutet für Sie selbstverständlich keine Notenverminderung o.Ä.
In diesem Fall bitte ich Sie, mich per Email darüber zu informieren, damit ich eine Übersicht habe.
Liste der
Themen:
1 (D. Lou). Satz von Cayley: Anzahl der numerierten
Bäume mit $n$ Ecken ist $n^{n-2}$. (Auch Definitionen, die benötigt
werden: Graphen, Bäume, Wald; die
Aussage dass ein zusammenh. Graph genau dann ein Baum ist, wenn die
Anzahl von Ecken gleich Anzahl von Kanten plus 1).
Literatur: Aigner 1 S 247f. Aigner 3 S 125f.
Cameron
S 38f. DAS-Skript Satz 8.3, Satz 3.3.
2. (A.-L. Ernst) Heiratssatz bzw. Satz von Hall (Paarungen, bipartite Graphen, Matching).
Literatur: Aigner 1 S 226. Cameron S 88f. Diestel S
40f. DAS-Skript Satz 9.2--9.4;
3. (C. Lünse) Satz von Menger
(Zusammenhangszahl, Verbindungszahl).
Diestel S 71f. Aigner 2 S 55.
4. ( M. Keim)
Wege auf den Graphen. Eulersche Wege/Kreise (Kriterium von Exitenz).
und minimale aufgespannte Bäume
(Existenz und Algorithmus) (Evtl: kürzeste
Wege).
Literatur: K. 6 Aigner1, K.7
Aigner2, Diestel, Berge
5.
(M. Neues) Planare Graphen. Eulersche Polyederformel e - k + f = 2. Anwendung: zwei
Graphen, welche nicht Planar sind.
Aigner 1 S 93f. Aigner 2 S 9f.
Diestel S 103f.
6. (M. Tschelezek) Fünf-Farben-Satz.
Cameron S 304. Aigner 2 S
17f. Aigner 1 S 293f.
Diestel S 139.
7. (C. Klerner) Die
Museumswächter (Satz von Chvátal).
Literatur:
Aigner 1 S 297
8.
(L. Vogel) Satz von Ramsey. Diestel S 215f. Cameron S 147f. Aigner 2
S 130.
DAS-Skript
Satz 7.5.
9.
(A. Void)
Tourniergraphen und Paradox des Sportreporters
(Satz von Rédei, Satz 7.5, Satz 7.6, Satz 7.7 im Buch
von Clark). Clark S 271f. Gould S 284f. Satz 7.6 ist der Satz von Rédei. Clark/Holten "Graphentheorie" (siehe das Thema Tourniergraphen; die
relevante Sätze sind (7.5), 7.6, 7.7)
10. (L.
Hoffmann) Moore--Graphen . 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)
11. (P. Weck) Satz von Ford und Fulkerson
bzw. Max-flow-min-cut-Satz
(gerichtete
Graphen, Netzwerke, Flüsse). Evnt. Heiratssatz
als Korollar.
Diestel S 163. Clark S 296. Aigner 3 S 149. DAS-Skrip Satz
9.6;
12. Der
Hoffman—Singleton—Graph
S^n, innere
und äußere Automorphismen. Konstruktion des
Hoffman--Singleton--Graphs aus einem äußeren Automorphismus
der $S_6$. ; Gruppen--Skript Satz 29
über $ Out(S_6)$.
Literatur: Cameron 11.12 über Moore--Graphen;
paper von Manfred Junker ; Gruppen--Skript Satz 29
über $ Out(S_6)$.
13. (M. Wuller) Satz von Turán (extremale Graphen, Teilgraphen).
Aigner 1 S 301f.
Diestel S 188.
Zusätzliche Themen:
14. Hamiltonsche Kreise (Satz von Dirac).
Clark S 114. Diestel S 242. Aigner
2 S 124.
Polytopen
und Graphen:
15. Klassifikation von regulären
Polyeder über die Eulersche Polyederformel; Beschreibung aller regulären Polyeder
16. Der Starrkeitssatz
von Cauchy,
17. Satz von Balynski
Literatur: Aigner 1 und § 3.5 von
Lectures about polytopes
(von Ziegler)
Literatur (die Bücher stehen in
Semesterapparat (und mind. ein Examplar ist von der
Ausleihe gesperrt) in Teilbibliothek Naturwissenschaften
(Ernst-Abbe-Platz
2, 6. Etage, https://www.thulb.uni-jena.de/tb_natwi.html
):
1. Graphentheorie für Einsteiger, Nitzsche, 2009 (Nitzsche)
2. Graphentheorie, Clark und Holton, 1994 (Clark)
3. Graphentheorie, Diestel, 2010
(Diestel)
4. Das BUCH der Beweise, Aigner und
Ziegler, 2015 (Aigner 1)
5. Graphentheorie, Aigner, 2015
(Aigner 2)
6. Diskrete Mathematik, Aigner,
2009 (Aigner 3)
7. Graph Theory, Gould, 1988 (Gould)
8. Combinatorics, Cameron, 1994 (Cameron)
9. Claude Berge “The theory of graphs”.
10: Skripten DAS
(von Markus Junker), Gruppen
(von Markus Junker)
Das Buch von Nitzsche würde ich
jedem empfehlen, der sich vorher noch
nicht mit Graphentheorie
beschäftigt hat, um einen groben Überblick zu
bekommen (das Buch ist einfach zu
lesen). Es eignet sich allerdings eher
schlecht, um genaue Definitionen und
Beweise nachzuschlagen. Dafür sind
dann die anderen Bücher gedacht.
Gerne dürfen Sie Sich auch selber
nach weiterer Literatur umsehen (z.B. in der Bibliothek). Im Prinzip ist jedes
Buch über Graphentheorie geeignet.
25
Sept. 2021 Vladimir Matveev