✏️ Übungen zu Kap. 9 · Minimaler Spannbaum
Freiwillig – such dir aus, was du üben willst.
Vertiefung: Greedy beim Färben
Sechs Klassenarbeiten sollen geschrieben werden. Zwei Arbeiten dürfen nicht am selben Tag stattfinden, wenn mindestens eine Schülerin oder ein Schüler beide schreibt. Die Tabelle zeigt, wer welche Arbeiten schreibt. Wie viele Tage braucht man mindestens?
| Name | schreibt |
|---|---|
| Anna | Deutsch, Englisch, Mathe |
| Ben | Mathe, Französisch |
| Carla | Französisch, Biologie |
| David | Biologie, Chemie |
| Emil | Englisch, Chemie |
| Fatma | Deutsch, Chemie |
| Greta | Deutsch, Mathe |
| Hannes | Biologie |
D = Deutsch, E = Englisch, M = Mathe, F = Französisch, Bio = Biologie, Ch = Chemie
Übung 1: Stelle die Tabelle als Graphen dar. Die Arbeiten sind schon als Knoten platziert. Verbinde zwei Arbeiten mit einer Kante, wenn sie nicht am selben Tag stattfinden dürfen.
Übung 1: Stelle die Tabelle als Graphen dar. Die Arbeiten sind schon als Knoten platziert. Verbinde zwei Arbeiten mit einer Kante, wenn sie nicht am selben Tag stattfinden dürfen.
Merke
Beim Färben eines Graphen bekommt jeder Knoten eine Farbe. Eine Färbung ist zulässig, wenn benachbarte Knoten verschiedene Farben haben. Gesucht ist die optimale Färbung mit möglichst wenigen Farben. Hier steht jede Farbe für einen Tag.
Ein Greedy-Verfahren zum Färben
Für große Graphen (z. B. alle Klausuren einer Oberstufe) braucht man ein Verfahren. Wie Kruskal geht es Schritt für Schritt vor und nimmt jedes Mal die naheliegende Wahl, ohne sie später zu ändern: Gehe die Knoten in einer festen Reihenfolge durch und gib jedem die erste Farbe (Farbe 1, dann 2, …), die noch kein schon gefärbter Nachbar hat.
Anders als bei Kruskal führt die gierige Wahl hier also nicht immer zur besten Lösung. Was das bedeutet, zeigt das nächste Kapitel.