Kartenfärbeproblem (optional)

Begriffe: Näherungsalgorithmus, Greedy-Verfahren, Unverträglichkeitsgraph, Backtracking, planarer Graph, Clique, bipartiter Graph

Das Map Coloring Problem ist ein weiteres NP-vollständiges Problem, das vom Bildungsplan als Alternative zur dominierenden Menge vorgeschlagen wird. Es kann als weitere Anwendung für einen Greedy-Algorithmus verwendet werden. Der Graph beschreibt hier Unverträglichkeiten zwischen den Knoten und der Algorithmus teilt die gesamte Knotenmenge in Teilmengen auf, bei denen es innerhalb der Teilmenge keine unverträglichen Knoten gibt. Da sich viele andere Problemstellungen (z.B. Schienenplanung in der Kursstufe) auf dieses Problem zurückführen lassen, lohnt es sich, das Map Coloring Problem im Unterricht zu behandeln.

Das Arbeitsblatt führt das Kartenfärbeproblem anhand der Bundesländer von Deutschland ein. Nachdem die Schüler selbst eine Färbung gefunden haben (nicht notwendigerweise die optimale) wird das Problem wie gewohnt in ein Graphenproblem überführt. An dieser Stelle kann schon die Betrachtung der Anzahl der Möglichkeiten, die Notwendigkeit eines Näherungsalgorithmus motivieren (weiterführende Fragen 3+4).

Bei diesem Algorithmus ist nicht so offensichtlich, was die "beste" Erweiterung der Teillösung (teilweise gefärbter Graph) sein soll. Daher bietet es sich an, den Schülerinnen und Schülern hier die Beschreibung des Algorithmus zu geben oder eines der unzähligen Videos zum Kartenfärbeproblem zu zeigen und den Algorithmus dann händisch nachvollziehen zu lassen.

Gegebenenfalls kann der Algorithmus auch implementiert werden, da er recht einfach ist.

Ergänzung 1: Der Vier-Farben-Satz (Four Color Theorem)

Der Bildungsplan schreibt nicht vor, den Vier-Farben-Satz zu behandeln. Die Schülerinnen und Schüler müssen also nicht erklären oder beweisen können, warum sich jeder planare Graph mit vier Farben einfärben lässt.

Das Video "The Four Color Map Theorem - Numberphile" (https://www.youtube.com/watch?v=NgbK43jB4rQ ) kann aber als Ausblick und Denkanstoß verwendet werden.

Ergänzung 2: Kolonialproblem

Diese Erweiterung vertieft die Erkenntnis, dass es sich bei normalen Karten um planare Graphen handelt. Diese Einschränkung fällt beim Kolonialproblem weg und verdeutlicht, dass sich die Knoten eines Graphen im Allgemeinen nicht in vier Teilmengen ohne Unverträglichkeiten aufteilen lassen.

Unterrichtsverlauf: Herunterladen [odt][298 KB]

Weiter zu Minimal spannende Bäume