Prof. Dr. Roland Speicher
Tobias Mai
Vorlesung zur Kombinatorik und Graphentheorie
(Sommersemester 2015)Vorlesung
Di 12-14, SR 6 und Fr 10-12, HS IVDie Kombinatorik beschäftigt sich mit der Untersuchung von endlichen (manchmal auch von
abzählbar unendlichen) diskreten Strukturen. Historisch entstand sie aus Abzählproblemen,
wie sie zum Beispiel im 17. Jahrhundert bei der Wahrscheinlichkeitsanalyse von Glücksspielen
auftraten. Kennzeichnend für die dort auftretenden Probleme war, dass meist für jedes
Einzelproblem ad hoc neue Methoden ersonnen werden mussten. Lange Zeit spielte die Kombinatorik
deshalb eine Außenseiterrolle in der Mathematik, zusammenfassende Theorien ihrer Teilgebiete
entstanden erst im 20. Jahrhundert. Hier sind beispielsweise die Theorie der Möbiusinversion
(eine weitgehende Verallgemeinerung des Inklusions-Exklusions-Prinzips) oder die Rolle von
erzeugenden Funktionen zur Beschreibung von kombinatorischen Zahlenfolgen zu nennen.
Ein wesentliches Teilgebiet der Kombinatorik ist die Graphentheorie, bei der das grundlegende
mathematische Objekt ein Graph ist; typische Fragestellungen sind hierbei die nach Wegen im Graph
(mit gewissen Eigenschaften), Färbung von Graphen, Planarität von Graphen, Matchings (Heiratssatz)
oder auch Ramsey Theorie. Als Geburtsstunde der Graphentheorie gilt das Königsberger Brückenproblem
von Euler, um 1740.
In der Vorlesung werden grundlegende kombinatorische Probleme und Methoden vorgestellt.
Hauptaugenmerk liegt dabei auf der abzählenden Kombinatorik und Problemen aus der Graphentheorie.
Die Vorlesung ist 4-stündig und es wird eine Übung angeboten,
so dass 9 Leistungspunkte erworben werden können.
Ankündigung der Veranstaltung
Eintrag im KVV
Bei Fragen zur Vorlesung gerne an Tobias Mai wenden.
Skript
Kapitel 0Kapitel 1
Kapitel 2
Kapitel 3
Kapitel 4
Kapitel 5
Kapitel 6
Kapitel 7
Kapitel 8
Kapitel 9
Kapitel 10
Kapitel 11
Kapitel 12
Kapitel 13
Kapitel 14
Kapitel 15
Kapitel 16
Scheinvergabe
Durch regelmäßige Teilnahme an den Übungen und Erreichenvon mindestens 50% der Gesamtpunktzahl auf den Übungsblättern
wird die Zulassung zur Abschlussprüfung erworben.
Das Bestehen der Abschlussprüfung ist die Voraussetzung für den
Schein und die Grundlage der Note.
Übung
Übungsblatt 1Übungsblatt 2
Übungsblatt 3
Übungsblatt 4
Übungsblatt 5
Übungsblatt 6
Übungsblatt 7
Übungsblatt 8
Übungsblatt 9
Übungsblatt 10
Übungsblatt 11
Übungsblatt 12
Literatur
Wird in der Vorlesung angegeben.Aktualisiert am: 17. August 2015 Tobias Mai
