Prof. Vladimir Matveev (Institut für Mathematik)

 

 

 



Seminar (Seminar 2)  Graphentheorie, WS 2019/20

Termin und Ort:     

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 nur 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 5 Vorträgen 
neben dem eigenen, egal zu welchem Termin, scheint mir jedenfalls  nicht zu viel verlangt.
 
Jeder  Teilnehmer  soll ein ``Seminarheft´´ führen, in welcher er die Definition und die Hauptaussagen,
 die im Vortrag vorkommen, aufschreiben soll. Ich werde am Ende des Semesters das Heft kontrolieren.  
Ich werde nicht  kontrolieren, dass Sie auch die Beweise  verstehen; es ist keine Prüfung; 
ich will  lediglich dass Sie versuchen, die Vortrage  zu verstehen. 
 
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)
 
Wie halte ich einen gelungenen Seminarvortrag? (von Annete Werner)
 
 

Liste der Themen:

     1.   (Kloß;  29.10)  Bäume und der Satz von Cayley   
          Definition von Graphen,  Bäumen, numerierten Bäumen. 
     Satz von Cayley: Anzahl der numerierten Bäume mit $n$ Ecken ist  n^{n-2}.      

    Literatur: Cameron 3.10 (S.38f), 4.5 (S.60f); DAS-Skript Satz 8.3, Satz 3.3; Aigner2 (S.132).

2.       (Fischer; 5.11)  Der Heiratssatz   , Bipartite Graphen. Halls "Heiratssatz" mit Beweis. Paarungszahl = minimale Mächtigkeit einer Eckenüberdeckung mit Beweis

Eventuell auch 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.      [  (a)   Wege auf den Graphen.   Eulersche Wege.  ]  Wird nicht vergeben
(b)       Kurzeste Wege und minimale aufgespannte Bäume. 

 

      Literatur: K. 6 Aigner1, K.7 Aigner2, Nitsche, Diestel, Berger 

     

    4.        (Nikolaschin, 19.11)   Planare Graphen.  Einbettung in Ebene oder auf Sphäre ist äquivalent. Eulersche Polyederformel mit Beweis. Zwei nichteinbettbare Graphen mit Beweis

   5.        (Bönisch,26.11)    Der Fünf--Farben—Satz mit Beweis.       Algorithmus am Beispiel ausführen.  

     
 

     Literatur:  Cameron S.300 + 18.7 (S.304);  Diestel,  Mathworld.

 (c )  (Schoof, 3.12)    Die Museumswächter  

  Literatur:   Das Buch der Beweise (Aigner, Ziegler)

 

6.      Der Satz von Ramsey  

     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.

   

 

7.    (Brauer, 10.12)       Paradoxon des  Sportreporters      Literatur:  Clark/Holten "Graphentheorie"   (siehe das Thema heisst Tourniergraphen; die relevante Sätze sind (7.5), 7.6, 7.7) .Diestel, Cameron 11.9 (S.173--176), + S.178;   Bitte nicht das Buch von  Nitzsche „Graphen für Einsteiger“ aus Hauptvorlage  benutzen, das Beweis drin ist fehlerhaft, man kann aber trotzdem die entsprechenden  Abschnitte   lesen .

 8.  (Lappert, 17.12)  Gerichtete Graphen. Flüsse in Netzwerken.   Satz von Ford--Fulkerson mit Beweis.  Algorithmus mit Beispiel. 
    Evnt. 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).

   9    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)

 

 

 

  10.    Der Hoffman—Singleton—Graph 
  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)$.

  11.   Polytopen und Graphen:    


(a)      (Krauße, 14.01)     Der Starrkeitssatz von Cauchy,

12.     Satz von Balynski     

   Literatur: Das Buch der Beweise (Aigner, Ziegler), Kap. 12. Ziegler,  Lectures about polytopes 3.5

 

Literatur:
Die Bücher  stehen im Semesterapparat in der Bibliothek, bitte nach  Möglichkeit die Bücher nicht oder nur kurz  Ausleihen damit die andere sie benutzen können.

  • Peter Cameron "Combinatorics" Cambridge University Press.
  • Martin Aigner1 „Graphentheorie: Eine Entwicklung aus dem $4$-Farben Problem
    Martin Aigner2 "Diskrete Mathematik" Vieweg.
  • 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




06 Okt 2019 Vladimir Matveev