Lehrinhalte
Diese Vorlesung gibt eine grundlegende Einführung in die Kombinatorik und Graphentheorie.
Die Kombinatorik beschäftigt sich damit, wie wir (mathematische) Objekte nach bestimmten Regeln kombinieren können, auf wie viele Arten wir kombinieren können, ob es überhaupt eine solche Kombination gibt, und welche weiteren Eigenschaften solche Kombinationen vielleicht haben. Wenn wir eine Bewertung für unsere Kombinationen haben, können wir auch fragen, welche die in dieser Bewertung beste Auswahl ist. Eine einfache, aber typische Frage könnte hier sein, auf wieviele Arten man eine gegebene natürliche Zahl als Summe natürlicher Zahlen schreiben kann.
Kombinatorische Aufgaben kommen als Teilaufgabe häufig in Fragen aus ganz unterschiedlichen Gebieten der Mathematik vor, wie z.B. der Algebra, Wahrscheinlichkeitstheorie, Topologie, Geometrie oder Optimierung. Lange wurden solche Fragen innerhalb dieser Gebiete unanhängig untersucht, bevor in der zweiten Hälfte des letzten Jahrhunderts die Gemeinsamkeiten systematisch studiert und neue, mächtige Methoden entwickelt wurden, die die Kombinatorik zu einem eigenständigen mathematischen Gebiet werden liessen.
Graphentheorie ist eines der ältesten und größten Teilgebiete der Kombinatorik, in dem es um endliche Strukturen und Relationen zwischen ihren Elementen geht. Wir stellen Graphen oft durch eine endliche Menge von Knoten dar, und verbinden zwei Konten mit einer Linie, wenn sie in Relation sind. Auch hier stehen am Anfang Fragen danach, wieviele Graphen mit bestimmten Eigenschaften es gibt. Eine weitere typische Aufgabe ist das Färbungsproblem. Hier wollen wir Farben (so wenige wie möglich) so auf die Knoten verteilen, dass verbundene Knoten verschiedene Farben haben.
Wir werden uns voraussichtlich mit den folgenden Themen beschäftigen.
- Kombinieren und Zählen
- Erzeugende Funktionen und Rekursionen
- Partiell geordnete Mengen
- Graphentheorie, planare Graphen, Färbungen
- Polyeder
- Triangulierungen
- Zählen unter Symmetrie
- Probabilistische Methoden
- Designs
- Codes
Literatur
M. Aigner, Diskrete Mathematik, 5. Auflage, Vieweg, 2003.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Second edition, Addison-Wesley, Reading, MA, 1994.
W. Koepf, Hypergeometric Summation. An Algorithmic Approach to Summation and Special Function Identities, AMS, 1998.
J. Matouek, J. Neetril, Diskrete Mathematik. Eine Entdeckungsreise, Springer, 2002.
R.P. Stanley, Enumerative Combinatorics, Volume I, Cambridge 1997.
J.H. van Lint, R.M. Wilson: A Course in Combinatorics, Cambridge University Press, 2009.
Voraussetzungen
empfohlen: Algorithmic Discrete Mathematics
Online-Angebote
moodle
Diese Vorlesung gibt eine grundlegende Einführung in die Kombinatorik und Graphentheorie.
Die Kombinatorik beschäftigt sich damit, wie wir (mathematische) Objekte nach bestimmten Regeln kombinieren können, auf wie viele Arten wir kombinieren können, ob es überhaupt eine solche Kombination gibt, und welche weiteren Eigenschaften solche Kombinationen vielleicht haben. Wenn wir eine Bewertung für unsere Kombinationen haben, können wir auch fragen, welche die in dieser Bewertung beste Auswahl ist. Eine einfache, aber typische Frage könnte hier sein, auf wieviele Arten man eine gegebene natürliche Zahl als Summe natürlicher Zahlen schreiben kann.
Kombinatorische Aufgaben kommen als Teilaufgabe häufig in Fragen aus ganz unterschiedlichen Gebieten der Mathematik vor, wie z.B. der Algebra, Wahrscheinlichkeitstheorie, Topologie, Geometrie oder Optimierung. Lange wurden solche Fragen innerhalb dieser Gebiete unanhängig untersucht, bevor in der zweiten Hälfte des letzten Jahrhunderts die Gemeinsamkeiten systematisch studiert und neue, mächtige Methoden entwickelt wurden, die die Kombinatorik zu einem eigenständigen mathematischen Gebiet werden liessen.
Graphentheorie ist eines der ältesten und größten Teilgebiete der Kombinatorik, in dem es um endliche Strukturen und Relationen zwischen ihren Elementen geht. Wir stellen Graphen oft durch eine endliche Menge von Knoten dar, und verbinden zwei Konten mit einer Linie, wenn sie in Relation sind. Auch hier stehen am Anfang Fragen danach, wieviele Graphen mit bestimmten Eigenschaften es gibt. Eine weitere typische Aufgabe ist das Färbungsproblem. Hier wollen wir Farben (so wenige wie möglich) so auf die Knoten verteilen, dass verbundene Knoten verschiedene Farben haben.
Wir werden uns voraussichtlich mit den folgenden Themen beschäftigen.
- Kombinieren und Zählen
- Erzeugende Funktionen und Rekursionen
- Partiell geordnete Mengen
- Graphentheorie, planare Graphen, Färbungen
- Polyeder
- Triangulierungen
- Zählen unter Symmetrie
- Probabilistische Methoden
- Designs
- Codes
Literatur
M. Aigner, Diskrete Mathematik, 5. Auflage, Vieweg, 2003.
R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Second edition, Addison-Wesley, Reading, MA, 1994.
W. Koepf, Hypergeometric Summation. An Algorithmic Approach to Summation and Special Function Identities, AMS, 1998.
J. Matouek, J. Neetril, Diskrete Mathematik. Eine Entdeckungsreise, Springer, 2002.
R.P. Stanley, Enumerative Combinatorics, Volume I, Cambridge 1997.
J.H. van Lint, R.M. Wilson: A Course in Combinatorics, Cambridge University Press, 2009.
Voraussetzungen
empfohlen: Algorithmic Discrete Mathematics
Online-Angebote
moodle
- Lehrende: Andreas Paffenholz
Semester: WiSe 2022/23