Diskrete Mathematik I
Kombinatorik und Graphentheorie
Wintersemester 2009/2010
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:
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:
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
- Elementare Zählprinzipien
- Erzeugende Funktionen
- Rekurrenzen
- Techniken: Summation, Inklusion-Exklusion
- Polya-Theorie
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
- Do 12.00 - 13.30
Sprechstunden
während des Semesters: Di 16 - 17,
sont nach Vereinbarung
(Zimmer 103, Arnimallee 3).
(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.
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.