Auch ohne es zu wissen, hat der Lernende in der Vergangenheit einige Ordnungen gesehen. Zahlen werden durch <= geordnet. Ganzzahlen können teilweise durch die Beziehung "teilbar durch" geordnet werden. In der Genealogie werden Personen durch die Relation "A ist ein Vorfahre von B" geordnet. In diesem Modul werden partielle Ordnungen formell eingeführt und einige grundlegende und nicht-triviale Fakten über sie bewiesen.

Ein großer Teil der diskreten Mathematik dreht sich um das Zählen von Dingen. Ein klassisches Beispiel ist die Frage, wie viele verschiedene Wörter sich ergeben, wenn man die Buchstaben des Wortes Mississippi neu anordnet. Zählprobleme dieser Art gibt es in der diskreten Mathematik, der diskreten Wahrscheinlichkeitsrechnung und auch in der Analyse von Algorithmen zuhauf.

Der Binomialkoeffizient (n choose k) zählt die Anzahl der Möglichkeiten, k Elemente aus einer Menge der Größe n auszuwählen. Ein gutes Verständnis von (n choose k) ist auch für die Analyse von Algorithmen äußerst hilfreich.

Graphen sind wohl das wichtigste Objekt der diskreten Mathematik. Eine große Anzahl von Problemen aus der Informatik und der Kombinatorik kann in der Sprache der Graphen modelliert werden. Dieses Modul führt in die grundlegenden Begriffe der Graphentheorie ein - Graphen, Zyklen, Pfade, Grad, Isomorphie.

Wir fahren mit den Grundlagen der Graphentheorie fort. In diesem Modul stellen wir Bäume, eine wichtige Klasse von Graphen, und mehrere gleichwertige Charakterisierungen von Bäumen vor. Schließlich stellen wir einen effizienten Algorithmus vor, mit dem Sie feststellen können, ob zwei Bäume isomorph sind.

Ausgehend von dem bekannten Rätsel der "Brücken von Königsberg" beweisen wir die bekannte Charakterisierung von Eulerschen Graphen. Wir diskutieren Hamiltonsche Pfade und geben mit dem Dirac- und Ore-Theorem hinreichende Kriterien für ihre Existenz an.

Wir diskutieren aufspannende Bäume von Graphen. Insbesondere stellen wir den Algorithmus von Kruskal vor, um den minimalen aufspannenden Baum eines Graphen mit Kantenkosten zu finden. Wir beweisen die Cayley-Formel, die besagt, dass der vollständige Graph mit n Scheitelpunkten n^(n-2) Spannbäume hat.

In diesem Modul geht es um Flussnetzwerke und es hat einen ausgeprägten algorithmischen Charakter. Wir beweisen das Maximum-Flow-Minimum-Cut-Dualitäts-Theorem.

Wir beweisen das Hall'sche Theorem und das Kőnig'sche Theorem, zwei wichtige Ergebnisse über Übereinstimmungen in bipartiten Graphen. Mit der Maschinerie von Flussnetzwerken haben beide recht direkte Beweise. Schließlich haben partielle Ordnungen ihr Comeback mit dem Dilworth-Theorem, das einen überraschenden Beweis mit dem Kőnig-Theorem hat.