Prof. Vladimir Matveev (Institut für Mathematik)

 

 

 


Seminar (Proseminar, Seminar 1, Seminar 2)  Graphentheorie, WS 2024/25

Termin und Ort:     

An der ersten Sitzung,  am Di, 15.10.2024, 14:15—16:45,  Carl-Zeiß-Straße 3 / SR 130,            ist eine  nähere Besprechung der Themen und Verteilung der Literatur geplant.  

Spielregeln:
 
Der Vortrag soll frei an der Tafel gehalten werden. Spickzettel sind erlaubt, jedoch ist es nicht gestattet, von diesen direkt auf die Tafel abzuschreiben.
 
Folien und Beamer dürfen nur für Grafiken verwendet werden, Folienvorträge oder PowerPoint-Präsentationen sind verboten.
 
Die Präsentation soll wie ein mathematischer Vortrag aufgebaut und strukturiert sein: kurze Einführung, Definitionen, Sätze und Beweise.
 
 In jedem Vortrag sollen in der Regel zwei Beweise enthalten sein (oder ein komplexerer Beweis). Es ist nicht erlaubt, Teile aus dem Buch, wie Bilder oder Textabschnitte, direkt in die Präsentation zu kopieren. 
 
Es wird nicht erwartet, dass Sie neue Beweise entdecken, aber es ist wichtig, dass Sie den Vortrag eigenständig vorbereiten und durchdenken, anstatt lediglich das Buch laut vorzulesen.
 
Während des Vortrags werde ich, und möglicherweise auch Ihre Kommilitonen, mit Fragen eingreifen. Dies ist ein Teil der Übung: Sie sollten sich im Vorfeld überlegen, welche Fragen aufkommen könnten.
 
Typische Fragen sind zum Beispiel: „Wie definieren Sie das mathematische Objekt, das Sie verwendet haben?" oder „Formulieren Sie bitte die Aussage, die Sie verwendet haben, mathematisch korrekt." Auch kann nach einem Beispiel gefragt werden.
 
Sie verfolgen zwei Ziele: Erstens, einen inhaltlich abgeschlossenen, nicht trivialen Abschnitt der Mathematik, einschließlich der zugehörigen Beweise, zu verstehen. Zweitens, diesen Abschnitt Ihren Kommilitonen verständlich und mathematisch sauber zu vermitteln.
 
Es wird nicht erwartet, dass Sie die gesamte Doppelstunde ausschöpfen. Bei vielen Themen scheint mir ein Vortrag von etwa einer Stunde plus angemessen. Es soll auch genügend Zeit für Zwischenfragen und Diskussionen bleiben.
 
Nach dem Vortrag gebe ich Ihnen im Vier-Augen-Gespräch ein Feedback. Wir besprechen außerdem die schriftliche Ausarbeitung des Vortrags: Falls ich keine mathematischen Bedenken habe, kann die schriftliche Ausarbeitung sehr kurz ausfallen oder ganz entfallen.
 
Ich muss die Vorträge bewerten. Durschnittnote für einen Seminar ist relativ hoch. In der Regel bietet das Proseminar jedoch eine gute Möglichkeit, Ihre Durchschnittsnote zu verbessern. 
 
 
Sollte ich jedoch den Eindruck gewinnen, dass der Vortragende den Vortrag nicht ernsthaft vorbereitet oder im Wesentlichen nicht verstanden hat, gilt der Vortrag als nicht bestanden.
 
Die wesentliche Leistung ist der Vortrag, aber der Fairness halber wird auch erwartet, dass Sie sich für das Anhören und Verstehen der Vorträge der anderen Teilnehmer nach Möglichkeit zur Verfügung stellen.  
 
Jeder Teilnehmer soll ein „Seminarheft“ führen, in dem er die Definitionen und Hauptaussagen der Vorträge notiert. Eine Seite pro Vortrag reicht aus. 
 
Ich werde dieses Heft am Ende des Semesters kontrollieren, allerdings nicht prüfen, ob Sie die Beweise vollständig verstanden haben. Es handelt sich nicht um eine Prüfung, sondern ich möchte sehen, dass Sie sich bemüht haben, die Vorträge nachzuvollziehen.
 
Selbstverständlich können/sollen  Sie  Ihren Vortrag im Vorfeld mit mir besprechen und auch mathematische Hilfe von mir bekommen. Die Erfahrung vergangener Semester zeigt, dass es am besten ist, den Vortrag zweimal mit mir zu besprechen.
 
 Beim ersten Treffen stellen Sie einen Plan Ihres Vortrags vor und erhalten mathematische Unterstützung, falls es Verständnisschwierigkeiten gibt. Beim zweiten Treffen geht es um die Feinabstimmung Ihres Vortrags.
 
 
 
Wie halte ich einen Seminarvortrag? (von Manfred Lehn)
 
Wie halte ich einen gelungenen Seminarvortrag? (von Annete Werner)
 
 

Liste der Themen:

1  (22.10, B.S.)      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.    (29.10, A.S.) 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.   (Y.G., 05.11)        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.  (M.-F.N., 12.11)   Minimale aufgespannte Bäume (Existenz und Algorithmus für   kürzeste Wege).  

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

 

   5.    (V. O., 19.11)  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.  (J. R., 26.11) Fünf-Farben-Satz.   

 

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

Diestel S 139.

 

7.      (L.S.,  03.12)  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.     (L.V., 10.12)    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.   (F.P.,  17.12.)       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.  (M.P.,  14.01.)     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-Skript 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.   (J.M., 21.01.) 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.   (J.K., 21.01)    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

 

 

 

 



15 Okt 2024 Vladimir Matveev