✏️ Übungen zu Kap. 10 · Kameras an Kreuzungen: Greedy ist nicht immer optimal
Freiwillig – such dir aus, was du üben willst.
Kameras im Gitter
Die Wege eines Parks bilden ein Gitter.
Übung 3: Wie viele Kameras hat die Greedy-Idee im Gitter gebraucht, wie viele deine beste Lösung? Spielt es eine Rolle, welche Kreuzung man bei Gleichstand wählt? Probiere es aus.
Landkarten färben
Beim Färben eines Graphen bekommt jeder Knoten eine Farbe, sodass benachbarte Knoten verschiedene Farben haben – möglichst wenige Farben insgesamt (siehe Vertiefung in Kapitel 9). Benachbarte Landkreise sollen auf einer Karte verschiedene Farben haben. Jeder Landkreis ist ein Knoten, gemeinsame Grenzen sind Kanten.
Die Greedy-Färbung (Vertiefung in Kapitel 9) gibt jedem Knoten in einer festen Reihenfolge die erste Farbe, die noch kein schon gefärbter Nachbar hat. In der Reihenfolge A, D, B, E, C, F braucht sie für dieses Sechseck 3 Farben.
Übung 5: Finde für das Sechseck eine Reihenfolge, in der das Greedy-Verfahren mit zwei Farben auskommt. Was fällt dir auf?
Wusstest du? Jede Landkarte lässt sich mit höchstens vier Farben färben (Vier-Farben-Satz). Bewiesen wurde das 1976 als einer der ersten mathematischen Sätze mit Computerhilfe – der Rechner prüfte fast 2000 Fälle durch.