Diskrete Mathematik I
Kombinatorik und Graphentheorie
Wintersemester 2009/2010
Ankündigungen
Die Klausureinsicht ist am Freitag, den 9.4. um 11:45 in Raum 202, A3.

Die Nachklausur wurde am Freitag, den 26.3.2010 von 10-12 im Hörsaal 001 in der Arnimallee 3 geschrieben.
Wenn Sie mitgeschrieben haben und der Veröffentlichung Ihrer Note auf dieser Seite zugestimmt haben, können Sie Ihr Ergebnis mit diesem Link abfragen. (Sowohl Benutzername als auch Passwort sind Ihre Matrikelnummer). Wenn Sie dem Aushang an meiner Bürotür zugestimmt haben, können Sie dort nachsehen.

Ich wünsche Ihnen einen guten Start ins neue Semester.
Wenn Sie weiterhin Interesse an Diskreter Mathematik haben, dann können Sie im nächsten Semester zwischen zwei Fortsetzungen zu dieser Vorlesung wählen:
  • Der Kurs Combinatorics von Tibor Szabo behandelt (nach einer kurzen Einführung) Ramseytheorie, extremale und strukturelle Graphentheorie und kombinatorische Methoden. Der Kurs wird auf Englisch gehalten und ist Teil des BMS-Vorlesungsangebots.
  • Ich werde eine Vorlesung Geometrie und Optimierung anbieten. In dieser Vorlesung werden wir uns mit Polyedertheorie, Dualität, linearer und ganzzahliger Optimierung, dem Simplexverfahren und Methoden zur ganzzahligen Optimierung sowie Anwendungen der Methoden in Graphentheorie und anderen Gebieten beschäftigen.
Inhalt
Die Vorlesung wird sich hauptsächlich mit Graphentheorie und abzählender Kombinatorik beschäftigen.

Wir werden uns am Anfang mit Graphentheorie beschäftigen. Bisher habe ich für die Vorlesung die folgenden Themen vorgesehen:
  • Graphen und gerichtete Graphen: Grundbegriffe
  • Bäume, aufspannende Bäume, kürzeste Wege
  • Ebene Graphen
  • Färbungen
  • Matchings
  • Netzwerke und Flüsse
Im zweiten Teil Konzentrieren wir uns auf Zählprinzipien.
  • Elementare Zählprinzipien
  • Erzeugende Funktionen
  • Rekurrenzen
  • Techniken: Summation, Inklusion-Exklusion
  • Polya-Theorie
Zwischendrin beschäftigen wir uns mit Matroiden, endlichen und linearen Codes oder Inzidenzstrukturen. Hier können auch von Seiten der Hörer Wünsche geäußert werden,
Vorlesungeszeiten
  • Vorlesung:
    • Dienstag 12.00 - 14.00, SR 31 (Arnimallee 6)
    • Donnerstag 13.40 - 14.40, SR 31 (Arnimallee 6)

  • Übungen:
    • Do 12.00 - 13.30
Sprechstunden
während des Semesters: Di 16 - 17, sont nach Vereinbarung
(Zimmer 103, Arnimallee 3).

Laszlo David
n.V.
().

Vorlesungsinhalt
Hier wird nach und nach eine stichwortartige Zusammenfassung der Vorlesungen erscheinen.
Datum Inhalt
13.10. Einführung
Termine, Übungen, Klausur
Definition von Graphen, Begriffe.
15.10. Termine, Übungen
Beispiele von Graphen: regulär, vollständig, (vollständig) biparit, Untergraphen
Wege, Pfade, Kreise, Zusammenhang
20.10. Wege, Kreise, Abstand
Löschen von Knoten, Kanten; Schnittknoten, Brücken
Vereinigung, Schnitt
allgemeinere Graphenklassen, gerichtete Graphen
Bäume
Wälder, Bäume, minimal zusammenhängend, maximal kreisfrei
Anzahl Kanten
22.10. Chrarakterisierung von Bäumen
aufspannende Bäume
Breitensuche
27.10. Breitensuche
Tiefensuche
minimal auspannende Bäume
Algorithmus von Kruskal für MST
29.10. Algorithmus von Kruskal für MST
Laufzeit
Satz von Cayley,Prüferfolgen
Ebene Graphen
Definitionen
Eulerformel
Lineare Kantenschranke
03.11. K3,3 und K5 sind nicht eben.
Satz von Kuratowski (ohne Beweis)
Polytopgraphen
Färbungen
chromatische Zahl
Cliquen, unabhängige Mengen
Approximationsalgorithmus für Färbungen
05.11. Schranken durch Maximalgrad
Satz von Brooks
10.11. Satz von Brooks
Färbungen von ebenen Graphen
Satz von Kempe/Heawood
Matchings
Definitionen, maximum/maximal/perfektes Matching,
alternierende, vergrößernde Pfade
Satz von Berge
12.11. Marriage Theorem
17.11. Theorem of König-Egervary
perfect matchings: Theorem of Dirac
perfect matchings: Theorem of Tutte
Networks
weight functions
shortest path problem
Dijkstra's algorithm
19.11. Flüsse
Schnitte
s-t-vergrößernde Pfade
24.11. MaxFlow-MinCut-Satz
ganzzahlige Flüsse und Pfadzerlegung
kantendisjunkte und kreuzungsfreie Wege
Satz von Menger: Kanten- und Knotenversion
k-facher (Kanten-)Zusammenhang
26.11. k-facher (Kanten-)Zusammenhang
Abzählen
Elementare Zählprinzipien, Schubfachprinzip
01.12. Elementare Zählprinzipien
Permutationen, Kombinationen
Partitionen, Stirlingzahlen zweiter Art
03.12. Elementare Zählprinzipien
Stirlingzahlen zweiter Art Partitionen
08.12. Zusammenfassung der Zählprinzipien
Identitäten
Inklusion-Exklusion
Formel für Stirlingzahlen
10.12. Eulersche φ-Funktion
Möbius-Funktion, Möbius-Inversion
15.12. Möbius-Funktion, Möbius-Inversion
Lemma von Burnside
Erzeugendenfunktionen Definition, Beispiel
17.12. Zählprobleme und Erzeugendenfunktionen
Rekursionen
05.01. Formale Potenzreihen, Ringstruktur, Eigenschaften
Beispiel: Rekursionen, Partitionen
07.01. Exponentielle Potenzreihen
Zählen von Permutationen
fixpunktfreie Permutationen
12.01. Partitionen
Rekursionen, Partitionen für kleines n
unterschiedliche Summanden
Satz von Euler
14.01. Erzeugendenfunktion
spezielle Partitionen
Beweise über Erzeugendenfunktion/ Identiäten
19.01. Catalanzahlen
Definition, Formel
Beispiele, Klammerungen, Gitterpfade
Erzeugendenfunktion
21.01. Polya-Theorie Gruppen und Gruppenwirkung
Beispiele von Gruppen
26.01. Orbiten, Muster, Fixpunktmengen
Lemma von Burnside
Zykelindex
28.01. Gewichtsfunktion, Mustererzeugendenfunktion (pattern inventory)
Satz von Polya
02.02. Satz von Polya,
Beispiele
Permutationen auf den Farben
04.02. Permutationen auf den Farben
Graphen zählen
Übungsaufgaben
Die Übungsaufgaben sollen in Zweier- oder Dreiergruppen bearbeitet und abgegeben werden. Sie müssen bis spätestens am auf die Ausgabe folgenden Dienstag vor der Vorlesung abgegeben werden (Ausnahme: ersten Blatt bis Donnerstag vor dem Tutorium).
Datum Thema
Abzugeben bis
15.10. Wege und Kreise in Graphen 22.10.
20.10. Bäume 27.10.
27.10. aufspannende Bäume, DFS, BFS 03.11.
3.11. minimal aufspannende Bäume, ebene Graphen 10.11.
10.11. Färbungen 17.11.
17.11. Matchings 24.11.
24.11. Zusammenhang 01.12.
01.12. Schubfachprinzip 08.12.
08.12. Zählen 15.12.
15.12. Zählen, Erzeugendenfunktionen 05.01.
05.01. Erzeugendenfunktionen 12.01.
12.01. Erzeugendenfunktionen 19.01.
19.01. Catalan- und andere Zählfunktionen 26.01.
26.01. Zählen unter Symmetrie 02.02.
02.02. Zusatzblatt 09.02.
Literatur
Ab Mitte Oktober können Sie eine kleine Auswahl an Büchern im Handapparat zur Vorlesung finden.
 
[Tu] Alan Tucker Applied Combinatorics, Wiley
[HHM] John Harris, Jeffry L. Hirst, and Michael J. Massinghoff Combinatorics and Graph Theory, Springer
[vLW] van Lint und Wilson A course in Combinatorics, Cambridge University Press
[Ste] Angelika Steger Diskrete Strukturen, Springer
[LPV] Lovasz, Pelikan, Vesztergombi Discrete Mathematics, Springer
ECTS-Kriterien
Um die ECTS-Punkte für diesen Kurs zu bekommen, müssen Sie
  • regelmäßig am Tutorium teilnehmen (was bedeutet, höchsten zweimal zu fehlen)
  • Korrekte Lösungen zu mindestens 50% der ausgegebenen Übungsaufgaben einreichen.
  • die Klausur am Ende des Semesters bestehen.