Prof. Vladimir Matveev (Institut für Mathematik)

 

 

 


Seminar (Proseminar, Seminar 1, Seminar 2)  Graphentheorie, WS 2023/24

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 Kommilitonen
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 kontrollieren.  
Ich werde nicht  kontrollieren, dass Sie auch die Beweise  verstehen; es ist keine Prüfung; 
ich will  lediglich dass Sie versuchen, die Vorträge  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        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.     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.          Wege auf den Graphen.   Satz von Menger (Zusammenhangszahl, Verbindungszahl).

Diestel S 71f. Aigner 2 S 55 und   Eulersche Wege/Kreise (Kriterium von Exitenz).  K. 6 Aigner1, K.7 Aigner2,   Diestel, Berge  


   4. Minimale aufgespannte Bäume (Existenz und Algorithmus für   kürzeste Wege).  

      Literatur:  K. 6 Aigner1, K.7 Aigner2,   Diestel, Berge  

 

   5.     Planare Graphen (ohne 5-Farben-Satz und ohne Kriterium von Plattbarkeit).  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. Fünf-Farben-Satz.   

 

Cameron S 304. Aigner 2 S 17f. Aigner 1 S 293f.

Diestel S 139.

 

7.        Die Museumswächter (Satz von Chvátal).

  Literatur:   Aigner 1 S 297

8.        Satz von Ramsey. Diestel S 215f. Cameron S 147f. Aigner 2 S 130.

DAS-Skript Satz 7.5.

9.      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.        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.    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.    Satz von Turán (extremale Graphen, Teilgraphen).

 

Aigner 1 S 301f. Diestel S 188.

 

Zusätzliche Themen:

 

 14.  Hamiltonsche Kreise 

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:
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.

·         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”.

 

 

Das Buch von Nitzsche würde ich jedem empfehlen, der sich vorher noch nicht mit Graphentheorie beschäftigt hat, um einen groben Überblick zubekommen (das Buch ist einfach zu lesen). Es eignet sich allerdings eher schlecht, um genaue Definitionen und Beweise nachzuschlagen. Dafür sinddann 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.

 

Die Bücher sind wie folgt zu finden:

 1.  Graphen für Einsteiger: Rund um das Haus vom Nikolaus, Manfred Nitzsche, 2009 Ist  unter dem folgenden Link im Universitätsnetz zugänglich. http://dx.doi.org/10.1007/978-3-8348-9968-2

2. Graphentheorie, Clark und Holton, 1994 unter der Signatur MAT:CC:1000:Cla::1994 im Freihandbestand entleihbar

3. Graphentheorie, Diestel, 2010  unter der Signatur MAT:CC:1000:Die::2010 im Freihandbestand entleihbar

unter der Signatur INF:CC:1000:Die::2012 ist der erste korrigierte Nachdruck 2012 im Freihandbestand entleihbar

4. Das BUCH der Beweise, Aigner und Ziegler .Die aktuelle 5. Auflage 2018 befindet sich als E-Book im Bestand und ist unter dem folgenden Link im Universitätsnetz zugänglich. https://doi.org/10.1007/978-3-662-57767-7

 

5. Graphentheorie, Aigner, 2015 unter der Signatur MAT:CC:1000:Aig::2015 im Freihandbestand entleihbar

 

6. Diskrete Mathematik, Aigner, 2009 unter der Signatur MAT:CC:1000:Aig::2006 im Freihandbestand entleihbar

 

7. Graph Theory, Gould, 1988 unter der Signatur MAT:CC:1000:Gou::1988 im Freihandbestand entleihbar

 

8. Combinatorics, Cameron, 1994  unter der Signatur MAT:CC:1000:Cam::1994 im Freihandbestand entleihbar

 

9. The theory of graphs, Claude Berge unter der Signatur 2011 NA 4594 im Magazin aufgestellt

 

 

 

 



10 Okt 2022 Vladimir Matveev