Kartenfärbung & 4-Farben-Satz

Karte:

Max. Farben: 4

Verfahren:

🐢 🐇 50

Eingefärbt: 0 / 0 Benutzte Farben: 0 / 4 In Bearbeitung

Graphen-Modell

Geografische Karte

🎨 Werkzeugkasten

Klicke manuell in die Karte.

📊 Algorithmus-Statistik

Mögliche Kombinationen (cⁿ)

Probierte Zuweisungen

Laufzeit

⚙️ Algorithmen-Theorie

A. Greedy-Verfahren

Geht Knoten nacheinander durch. Nimmt die erstbeste freie Farbe.

function greedy(Graph G, Farben C): for each Knoten v in G: belegteNachbarFarben ← getNachbarFarben(v) for each Farbe c in C: if c not in belegteNachbarFarben: v.farbe ← c // Erste freie nehmen break return Färbung

B. Heuristik (Grad-sortiert)

Wie Greedy, aber sortiert Knoten nach Knotengrad (Fail-First).

function heuristik(Graph G, Farben C): sortiere G.knoten absteigend nach Grad // Engpässe zuerst! for each Knoten v in sortierteListe: belegteNachbarFarben ← getNachbarFarben(v) for each Farbe c in C: if c not in belegteNachbarFarben: v.farbe ← c break return Färbung

C. Backtracking

Tiefensuche mit Rücksetzen bei Sackgassen.

Worst-Case: O(cⁿ) — bricht nach 500.000 Schritten ab.

function backtrack(knotenIndex): if knotenIndex == AnzahlKnoten: return true // Alle gefärbt! for each Farbe c in C: if istGültig(knotenIndex, c): knoten[knotenIndex].farbe ← c if backtrack(knotenIndex + 1): return true knoten[knotenIndex].farbe ← leer // ← BACKTRACK! return false // Sackgasse

🗺️ Der Vier-Farben-Satz

📜 Geschichte

💻 Der erste Computer-Beweis

📐 Von der Karte zum Graphen

⚠️ Regeln