Wir werden zusammenhängende Komponenten eines Graphen betrachten und sehen, wie sie zur Implementierung eines einfachen Programms zur Lösung des Guarini-Rätsels und zum Nachweis der Optimalität eines bestimmten Protokolls verwendet werden können. Wir werden sehen, wie man eine gültige Reihenfolge einer Aufgabenliste oder eines Graphen mit Projektabhängigkeiten findet. Schließlich werden wir den dramatischen Unterschied zwischen scheinbar ähnlichen Euler'schen Zyklen und Hamilton'schen Zyklen herausfinden und sehen, wie sie bei der Genomassemblierung eingesetzt werden!

In dieser Woche werden wir drei Hauptklassen von Graphen untersuchen: Bäume, zweiseitige Graphen und planare Graphen. Wir werden minimale überspannende Bäume definieren und dann einen Algorithmus entwickeln, der den billigsten Weg findet, beliebige Städte zu verbinden. Wir untersuchen Übereinstimmungen in zweiseitigen Graphen und sehen, wann eine Reihe von Stellen mit Bewerbern besetzt werden kann. Wir werden auch lernen, was planare Graphen sind, und sehen, wann U-Bahn-Stationen ohne Kreuzungen verbunden werden können. Bleiben Sie dran für weitere interaktive Rätsel!

Wir werden uns auf die Diagrammparameter und die damit verbundenen Probleme konzentrieren. Zunächst definieren wir die Färbung von Graphen und sehen, warum politische Karten in nur vier Farben gefärbt werden können. Dann werden wir sehen, wie Cliquen und unabhängige Mengen in Graphen zusammenhängen. Anhand dieser Begriffe werden wir das Ramsey-Theorem beweisen, das besagt, dass in einem großen System vollständige Unordnung unmöglich ist! Schließlich werden wir uns mit Vertex Cover beschäftigen und lernen, wie man die minimale Anzahl von Computern findet, die alle Netzwerkverbindungen kontrollieren.

Diese Woche werden wir einen Algorithmus entwickeln, der die maximale Wassermenge findet, die in einem gegebenen Wasserversorgungsnetz geleitet werden kann. Dieser Algorithmus wird in der Praxis auch zur Optimierung des Straßenverkehrs und der Flugplanung eingesetzt. Wir werden sehen, wie Flüsse in Netzwerken mit Übereinstimmungen in zweiseitigen Graphen zusammenhängen. Anschließend werden wir einen Algorithmus entwickeln, der stabile Übereinstimmungen in zweiseitigen Graphen findet. Dieser Algorithmus löst das Problem der Zuordnung von Studenten zu Schulen, von Ärzten zu Krankenhäusern und von Organspendern zu Patienten. Am Ende dieser Woche werden wir einen Algorithmus implementieren, der den Nobelpreis für Wirtschaft gewonnen hat!