das vier-farben-problem

vorgeschichte :
vor über 30 jahren, es mögen auch 40 gewesen sein, nachdem ich mich schon jahrelang mit dem 4-farben-problem beschäftigt hatte (in meiner schulzeit war einmal der mathe-lehrer ausgefallen und die vertretung (wie das manchmal so ist mit diesen seiten-effekten, die interessantere folgen haben können als das haupt-programm) also die vertretung machte nicht den normalen unterricht weiter, da sie nicht im thema war, sondern erzählte uns etwas über das 4-farben-problem, was mir dann irgendwann wieder in den sinn kam und mein zunehmendes interesse erweckte) nachdem ich mich also jahrelang damit beschäftigt hatte (nicht immer, aber immer öfter) fasste ich mir ein herz und suchte, es war in hannover, einen der professoren der technischen hochschule auf, herrn professor kaluza . der wiederum war durchaus im thema, da sein kollege, prof. heesch gerade in dieser sache in den usa war, um dort den computer-beweis vorzuschlagen und durchzuführen (der damals aber noch die computer überforderte und erst später gelang) .
ich schilderte ihm also meinen ansatz, der durchaus neu für ihn war, und er verwies mich weiter an die assistenten von heesch . die versuchten daraus ein computer-proramm zu machen und ich gab ihnen ratschläge, was zu tun sei, aber es erwies sich nicht als vollständig computerisierbar und so konnten sie es nicht als lösung anerkennen, obwohl sie den ansatz faszinierend fanden . prof. kaluza bot mir an, sich um ein mathe-stipendium für mich zu bemühen, was ich aber ablehnte, da ich damals voll im anarcho-syndikalistischen flügel der apo (außerparlamentarischen opposition) integriert war und mit den akademikern eigentlich nichts am hut hatte .
mein ansatz bestand aber darin, dass man jeden 4-farben-graph in drei bäume zerlegen kann (siehe oben) .
um einen baum einzufärben braucht man zwei farben, um zwei bäume einzufärben, braucht man drei farben (das ist noch trivial) . folglich besagt der analogie-schluss, dass man für drei bäume vier farben braucht .
das lässt sich aber schlecht programmieren, da der dritte baum den beiden andern entgegenläuft und programmiertechnisch ein kreislauf ausgeschlossen werden muss .
dafür habe ich bisher noch keinen ansatz gefunden .
aber mein interesse an bäumen und strukturen war geweckt und hat mein denken bis heute befruchtet .


“abkürzung”
es reicht eigentlich schon, das prinzip für zwei felder zu beweisen .
nehmen wir an, eine richtige färbung wäre möglich (ohne zu sagen, wie) .
nehmen wir weiter an, bei richtiger färbung gäbe es immer eine möglichkeit, den graphen so zusammen zu ziehen, dass ein feld verschwindet und die richtige färbung für alle anderen erhalten bleibt . bei zwei feldern bleibt also eins übrig . ein feld ist nach definition immer färbbar .
da wir also garantiert bei einer richtigen färbung landen, können wir den vorgang jetzt gedanklich umkehren und die färbung jetzt wieder in genau der gleichen weise auseinander ziehen, wie wir sie zusammen gezogen haben (ohne zu sagen, wie (nur, dass es genau umgekehrt läuft)) .
die these lautet dann :
wenn durch gedankliches zusammen ziehen einer richtigen färbung immer ein zustand erreicht werden kann, der auch real richtig ist, dann kann man sich diesen vorgang auch umgekehrt denken und kommt zu einer gedanklich richtigen ausgangsfärbung (gedanklich deshalb, weil man damit nicht bestimmen kann, wie die färbung konkret aussieht)

x – 1 = 1 ==> x = 2 oder allgemein x – n = 1 ==> x = 1 + n


um einen graphen so zusammen zu ziehen, dass ein feld verschwindet und die richtige färbung für alle anderen erhalten bleibt, gehen wir von einem knoten mit höchstens 5 kanten aus, die wir uns als gummi-schnüre denken (ein solches feld muss immer vorhanden sein, da nicht jeder knoten mehr als 5 kanten haben kann) .
bei richtiger färbung ist also ein umgebungsknoten (u1) einmal vorhanden, während zwei umgebungsknoten (u2) jeweils doppelt sind . u1 – u2 – u2 – u2 – u2 . jetzt ziehe ich den innen-knoten mitsamt seinen kanten auf u1, wobei seine färbung verschwindet, zusammen mit der verbindungskante zu u1 . die übrige färbung bleibt erhalten .


ein sonderfall wäre, wenn ich keinen u1 – u2 – u2 – u2 – u2 knoten habe, sondern nur einen u2 – u2 – u2 – u2 knoten (also 4 kanten, wobei 2 jeweils doppelt sein können) . in diesem fall hilft eine (immer mögliche) umfärbung . nehmen wir an, der innen-knoten ist 1 und die kette ist 2 – 3 – 2 – 3 . dann ersetze ich die erste 2 durch eine 4, alle daran anschließenden 4-er durch eine 2 und so fort . wenn danach die zweite 2 immer noch da steht, kann ich zusammenziehen . wenn auch die zweite 2 eine 4 wurde, habe ich eine durchgehende kette, die von der 1 – 3 kette nicht durchbrochen werden kann . ich ersetze also die 1 – 3 kette nach einer seite duech ein 3 – 1 kette und danach den innen-knoten selber durch eine 2 . jetzt kann ich auch hier zusammenziehen .

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: