Der Vierfarbensatz gilt heute als bewiesen, wenn auch nur mittels massivem Computereinsatz. Es ist aber aufwändig, und für beliebig, grosse Graphen sogar unmöglich "Lösungen", also gültige Flächen-Vierfärbungen oder gleichwertige Kanten-Dreifärbungen zu finden. Ausser dem Durchprobieren aller möglichen Kombinationen auf dem Computer ist kein Verfahren bekannt. Dazu gibt es aber verschiedene Ansätze und es gilt die effizienteste mit der geringsten Laufzeit zu finden. Die aufwändigste wäre das Durchprobieren aller vier Flächenfarben auf f Flächen des Graphen. Das ergibt 4^f Möglichkeiten. Bei f=10 wäre das ca. 1Mio. Deutlich weniger Versuche kostet die folgende Suchmethode:
Man installiert in jeder Fläche des ungefärbten Graphen (1) einen "Wirbel", der entweder rechts- oder linksdrehend sein kann (2). Das ergibt 2^f Kombinationen. Mit f=10 ergibt sich die Zahl 1024, also deutlich weniger als im ersten Beispiel. Jede Kante erhält einen Richtungspfeil, wenn die "Strömung" der Wirbel auf beiden Seiten gleichgerichtet ist (3). Sobald an einer Ecke drei Pfeilspitzen oder Pfeilenden Zusammentreffen, wird diese Kombination verworfen. Bei den übrigbleibenden Kombinationen können nun die Richtungspfeile beginnend an einer beliebigen Stelle abwechselnd mit zwei der drei Kantenfarben (blau/grün) gefärbt (4), und schliesslich die dritte Kantenfarbe (rot) ergänzt werden. Die Suche nach den Lösungen ist also ein np-schweres Problem, der Beweis des Vierfarbensatzes aber nicht zwangsläufig!
Die Anzahl der Färbungsmöglichkeiten für die drei an einer Ecke zusammentreffenden Kanten steigt exponentiell mit 2^(e/2) bzw. 2^(F-2) mit e=Eckenzahl und f=Flächenzahl. Betrachtet man den Graphen als aus elastischen Fäden geknüpftes Netz, und durchtrennt einen beliebigen davon, so entsteht ein gerichtetes Bündel aus Fäden und Knoten, wenn man die beiden „losen Enden“ wie in nachstehender Grafik gezeigt in die Länge zieht.
Es entsteht ein bipartiter Baum, der nach Einführung von Richtungspfeilen genau gleich viele Verzweigungs- und Vereinigungsknoten enthält. In der Regel zerfallen beide in eine Anzahl kleinere Bäume, die zusammen einen bipartiten Wald bilden. Es genügt, die Färbungsmöglichkeiten an einem der beiden durchzuprobieren. Die Färbung der „anderen Hälfte“ kann schlüssig ergänzt werden. Dieses wäre also die effizienteste Methode. Auf der mein graphischer, in Visual Basic geschriebener Editor beruht, mit dessen Hilfe ich die essentiellen Erkenntnisse gewonnen habe, die schliesslich zu meinem Beweis geführt haben.
Keine Kommentare:
Kommentar veröffentlichen