Universität Wien

902416 VO Ausgew. Kapitel aus Graphentheorie (2005S)

Ausgewählte Kapitel aus Graphentheorie

0.00 ECTS (2.00 SWS), SPL 25 - Mathematik

Vorbesprechung am 3. März 2005

Details

Sprache: Deutsch

Prüfungstermine

Lehrende

Termine (iCal) - nächster Termin ist mit N markiert

  • Mittwoch 02.03. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 03.03. 13:00 - 14:00 Seminarraum
  • Mittwoch 09.03. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 10.03. 13:00 - 14:00 Seminarraum
  • Mittwoch 16.03. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 17.03. 13:00 - 14:00 Seminarraum
  • Mittwoch 06.04. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 07.04. 13:00 - 14:00 Seminarraum
  • Mittwoch 13.04. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 14.04. 13:00 - 14:00 Seminarraum
  • Mittwoch 20.04. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 21.04. 13:00 - 14:00 Seminarraum
  • Mittwoch 27.04. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 28.04. 13:00 - 14:00 Seminarraum
  • Mittwoch 04.05. 13:00 - 14:00 Büro Dipl./Diss.
  • Mittwoch 11.05. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 12.05. 13:00 - 14:00 Seminarraum
  • Mittwoch 18.05. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 19.05. 13:00 - 14:00 Seminarraum
  • Mittwoch 25.05. 13:00 - 14:00 Büro Dipl./Diss.
  • Mittwoch 01.06. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 02.06. 13:00 - 14:00 Seminarraum
  • Mittwoch 08.06. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 09.06. 13:00 - 14:00 Seminarraum
  • Mittwoch 15.06. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 16.06. 13:00 - 14:00 Seminarraum
  • Mittwoch 22.06. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 23.06. 13:00 - 14:00 Seminarraum
  • Mittwoch 29.06. 13:00 - 14:00 Büro Dipl./Diss.
  • Donnerstag 30.06. 13:00 - 14:00 Seminarraum

Information

Ziele, Inhalte und Methode der Lehrveranstaltung

Ich möchte die Matchingtheorie als Thema der Vorlesung wählen, weil sie innerhalb des
relativ jungen mathematischen Gebietes der Graphentheorie eine sehr ausgereifte Theorie
darstellt. Sie hat ihren Ursprung in folgender Beobachtung von Tait (1880):
"Der Vierfarbensatz ist äquivalent dazu, dass die Kanten jedes planaren 3-regulären Graphen
ohne Schnittkante in drei perfekte Matchings partitioniert werden kann."
Tait wollte basierend auf dieser Beobachtung den Vierfarbensatz beweisen. Dies gelang
letztendlich bis heute nicht, aber - wie so oft in der Mathematik - gab dieser Ansatz Anlass
für eine schöne eigenständige Theorie.

Ich werde zu Beginn der Vorlesung die Grundlagen der Matchingtheorie wiederholen, also den Satz von Hall (Heiratssatz), den Satz von Tutte und den Algorithmus von
Edmonds zur Bestimmung eines Matchings maximaler Grösse. Danach werden wir uns mit der Struktur des Polytops der perfekten Matchings beschäftigen, das sind die
Konvexkombinationen aller perfekten Matchings eines fixen Graphen in einem für jeden Graphen natürlich definierten Vektorraum. Schliesslich werden wir ähnliche Betrachtungen im sogenannten Matchinggitter, das ist die Menge der Z-Linearkombinationen von perfekten Machtings, anstellen.

Art der Leistungskontrolle und erlaubte Hilfsmittel

Mindestanforderungen und Beurteilungsmaßstab

Prüfungsstoff

Literatur

(1) L. Lovasz und M. D. Plummer, Matching Theory, North Holland, 1986.
(2) L. Lovasz, Matching structure and the matching lattice, J. Combin. Theory Ser. B, 43 (1987), 187 - 222.
(3) R. Diestel, Graphentheorie, 2. Auflage, Springer-Verlag, 2000.
http://www.math.uni-hamburg.de/home/diestel/books/graphentheorie/index.html
(4) J. A. Bondy und U. S. R. Murty, Graph Theory with Applications, North Holland, New York, 1976 http://www.ecp6.jussieu.fr/pageperso/bondy/bondy.html

Zuordnung im Vorlesungsverzeichnis

Letzte Änderung: Mo 07.09.2020 15:51