Hier ein (umstrittener) Beweis, den ein gewisser sigi im Artikel haben möchte:
ein neuer beweis für das vier-farben-problem.
zunächst einmal die grundstruktur unseres beweises. wir stellen uns
einfach die menge aller tatsächlichen lösungen vor und unterteilen diese in
zwei gruppen von denen die erste eine bestimmte eigenschaft(E1) hat während
wir für unseren beweis ein bestimmte zweite eigenschaft(E2) brauchen.
sollte nun in der ersten gruppe E2 nicht auftauchen so liefert gerade dies
uns den grund dass sie ganz bestimmt in der anderen gruppe zu finden ist.
wir zeigen also dass wenn die lösung nicht in der ersten gruppe vorkommt
gerade dies der beweis ist dass sie in der zweiten existiert.
E1 und E2 nun sind dadurch bedingt dass man die länder nicht mehr mit vier
farben einfärbt sondern nur noch mit zwei (sagen wir F1 und F2) wobei die
länder die die gleiche farbe haben ketten und zweige (also bäume) bilden
dürfen aber niemals geschlossene ringe. das heisst also dass von drei ländern
die ein dreieck bilden nur zwei F1 (bzw. F2) sein können während das dritte
die komplementärfarbe haben muss. das heisst weiter dass wenn ich von einem
F1-land ausgehe und auf irgendein anderes angrenzendes F1-land überwechsle
(jedoch nicht auf das unmittelbar davor verlassene) ich in kein land mehr komme
wo ich schon einmal war wie oft auch immer ich diesen schritt wiederhole (bzw.
wiederholen kann). gleichzeitig bedeutet das dass ich jeweils von einem F1-
ursprungsland zu einem beliebigen anderen F1-land kommen kann denn nur dadurch
dass die F1-länder einen zusammenhang bilden können sie ja verhindern dass
die F2-länder einen ring bilden (und umgekehrt). diesen F1-(bzw. F2-)zusammen-
hang kann ich jetzt abwechselnd mit F1a und F1b (bzw. F2a und F2b) einfärben
so dass beispielsweise jeweils zwei F1a-länder durch ein F1b-land getrennt sind
und brauche so natürlich nie mehr als vier farben um die bedingung zu erfüllen
dass keine zwei aneinandergrenzenden länder die gleiche farbe haben.
wie brauchen also ein verfahren dass eine ringbildung zuverlässig verhindert
und so die bedingung erfüllt.
wir gehen zunächst von einem einzigen land aus dass wir uns so gross denken
wie alle länder zusammen die eine beliebige länderkombination bilden mögen.
das heisst wir können durch entsprechende abtrennung (also aufteilung und
umfärbung) aus einem land jede beliebige länderkombination bilden.
dabei gehen wir schrittweise vor. wir nennen unser ursprungsland |1| und
trennen zunächst einmal |2| ab. dadurch wird |1| zwar kleiner und ändert seine
form aber wie der leser wahrscheinlich schon längst weiss oder zumindest ahnt
kommt es hierauf überhaupt nicht an sondern allein auf die rein topologischen
beziehungen. so können wir also |1| und |2| ohne rücksicht auf ihr aussehen
und ihren grenzverlauf immer mit F1 und F2 einfärben so wie bei einem weiteren
abgetrennten |3| und |4| die farben F1a F1b F2a F2b ausreichend sind wobei wir
auch keine richtigen farben brauchen sondern blosse benennungen genügen.
genauso können wir den sonderfall dass zwei oder mehrere länder nur einen
punkt gemeinsam haben (was die färbung (oder benennung) vereinfachen würde da
diese länder alle die gleiche farbe haben dürfen) dadurch aufheben dass wir die
punktgrenze in einer beliebigen richtung um mindestens einen punkt erweitern.
und den ebenso vereinfachenden sonderfall dass ein oder zwei länder ein weiteres
völlig einschliessen können wir dadurch aufheben dass wir die fehlenden ein
oder zwei länder dazuerfinden so dass jedes land von mindestens drei ländern
eingeschlossen wird (die topologischen bedingungen auf die es uns ankommt
bleiben dabei erhalten).
topologisch gesehen gilt also bei vier ländern für jedes land (also auch für
|1|) dass es von den drei anderen eingeschlossen ist. ich habe noch vergessen
zu sagen dass jedes neue land das wir abtrennen von |1| abgetrennt wird
was man sich dadurch anschaulich machen kann dass man |1| immer als die
zusammenfassung aller noch nicht abgetrennten länder definiert. so ist es
auch völlig ausreichend nur |1| und seine unmittelbaren nachbarn zu betrachten
und zu zeigen dass man diese nachbarn immer so färben kann dass bei einem
beliebig abgetrennten neuen land der farbzusammenhang zu dem |1| gehört (im
folgenden immer F1) um ein glied erweitert wird ohne dass ein F1-ring entstehen
kann. diesen vorgang können wir nun auf grund der allgemeingültigkeit des verfah-
rens beliebig oft wiederholen was zu einer vollständigen induktionskette führt.
nun ist es ja so dass bei einem neu abgetrennten land (nennen wir es N)
immer zwei länder der nachberschaftskette (nennen wir sie L und R (für links
und rechts)) sowohl mit |1| als auch mit N verbunden bleiben (d.h. eine
gemeinsame grenze haben) während die zwischen L und R liegenden länder der
kette (falls vorhanden) zur abtrennunggsseite hin von N übernommen werden (zu
dessen nachbarschaftskette zählen). gehören nun L und R dem F2-zusammenhang an
während |1| ja zu F1 gehört so ist unmittelbar einsichtig dass wie oben schon
gesagt F1 durch N um ein glied erweitert werden kann ohne dass ein F1-ring
entsteht da bei der neu entstandenen verbindung |1|-N keine seiteneffekte
auftreten also alle übrigen länder ihre färbung und ihre (topologische)
färbungsumgebung behalten. d.h. wenn vorher kein farbring da war ist auch jetzt
keiner da. und hier kommen wir schon zu den oben erwähnten eigenschaften:
E1 := wenn wir |1| als F1 voraussetzen können wir für irgend ein L immer F2
erzwingen indem wir einen unmittelbaren nachbarn NB von |1| und L als F1 färben
(indem wir ihn wie oben beschrieben als das zuletzt hinzugekommene N ansehen).
(es sei hier noch einmal an die grundstruktur unseres beweises erinnert der
eine lösungsgruppe durch E1 definiert. somit handelt es sich dabei um alle
lösungen bei denen |1| und NB dem F1-zusammenhang angehören wodurch L
automatisch zu F2 gehört.)
E2 := können wir in entweder der einen oder der anderen lösungsgruppe immer
eine lösung finden bei der für ein beliebig gewähltes L und R beide F2 sind
dann können wir auch jede beliebige länderkombination erzeugen.
man kann das alles leichter nachvollziehen wenn man sich statt der länder
kleine kreise denkt (sozusagen die schwerpunkte der länder) und für jeweils
zwei länder die eine gemeinsame grenze haben die entsprechenden kreise mit
einer linie verbindet wobei sich keine zwei linien kreuzen dürfen. man erhält
dann eine entsprechende kombination von dreiecken (natürlich nur topolologisch)
deren eckpunkte eben die kleinen kreise bilden die man dann weiss (was F1
entsprechen soll) oder schwarz (entspricht F2) einfärben kann. wir betrachten
auch hier nur |1| rings umgeben von seinen direkten nachbarn die mit ihm wie
ein radkranz durch speichen mit der nabe verbunden sind.
unsere anfängliche 4-länderkombination können wir uns jetzt als ein auf eine
fläche abgebildetes tetraeder vorstellen welches nur aus kanten und eckpunkten
besteht wobei die eckpunkte alle als kleine kreise dargestellt sind.
2_________ 3
|\ /|
| \ / |
| \ / |
| 1 |
\ | /
\ | /
\ | /
\|/
4
wenn wir uns fragen welcher der |1|-nachbarn das zuletzt hinzugekommene N
ist wird klar dass es jeder sein kann denn wenn wir bei irgendeinem die
abtrennung (die ja hier ein herausziehen ist) wieder umkehren (ihn also nach
|1| hineinziehen) entsteht eine reale n minus 1 länderkombination und diesen
vorgang kann man bis zurück zu 1 wiederholen. folglich kann jeder nachbar
(natürlich nicht alle zugleich) dem farbzusammenhang von |1| (hier weiss)
angehören was wiederum bedeutet dass die rechts und links von ihm liegenden
nachbarn dem komplementärzusammenhang angehören (um gleichfarbige dreiecke zu
vermeiden).
bei unserer 4-länderkombination ist es allein schon auf grund der völligen
symmetrie klar dass jeder der drei nachbarn von |1| N sein kann während die
links und rechts von ihm liegenden länder L und R sind. somit ist hier also E2
unmittelbar erfüllt: jeweils zwei beliebige nachbarn von |1| können als L und
R fungieren. damit habe ich 6 möglichkeiten ein neues N oder |5| zu erzeugen
die ich hier der anschaulichkeit wegen einzeln anführe wobei das jeweils links
stehende land als L und das jeweils rechts stehende als R fungiert:
|2|-|3| |2|-|4| |3|-|4| |3|-|4|-|2| |4|-|3|-|2| |4|-|2|-|3|.
dies ist nun die menge aller tatsächlich möglichen topologischen konstruktionen
und damit leider auch schon die lösung unseres problems denn da E2 offensicht-
lich immer erfüllt ist muss E1 gar nicht mehr in anspruch genommen werden.
und das ist auch kein zufall denn wir haben es hier nur mit teilketten zu tun
die aus zwei oder drei gliedern bestehen. und wenn bei drei gliedern das mittlere
NB und also weiß ist müssen L und R schwarz sein weil sie sich ja im dreieck
mit |1| und NB befinden. bei nur zwei gliedern gehen wir vermittels einer
schöpferischen anwendung von E1 einfach davon aus dass L hier als |1| fungiert
und R als NB wobei das ursprüngliche |1| die rolle von R übernimmt. damit ist
sofort klar dass das neue |1| und das neue N die gleiche farbe haben dürfen
und somit haben auch bei einer zurückbenennung L und R die gleiche farbe.
verlassen wir jetzt den konkreten einzelfall und kommen wir zur alles
entscheidenden abstraktion. wir stellen uns für eine beliebig gewählte länder-
kombination die menge aller tatsächlichen lösungen vor und unterteilen diese in
zwei gruppen von denen die erste durch E1 bestimmt ist also |1| und NB weiß
sind und damit L schwarz ist.
jetzt suchen wir in dieser gruppe nach einer lösung bei der R ebenfalls
schwarz ist. haben wir erfolg dann ist E2 erfüllt und wir können ein neues N
erzeugen. haben wir aber hier keinen erfolg dann bedeutet das dass das von uns
auf weiss gesetzte NB immer ein ebenfalls weisses R erzwingt. das bedeutet aber
dass wenn der eine weiss ist nur dann ein farbring verhindert werden kann
wenn auch der andere weiss ist da wir nicht sagen können wer zuerst da war
das weisse NB oder das weisse R. folglich gilt umgekehrt: ein weisses R erzwingt
ein weisses NB.
folglich sind beide entweder weiss oder schwarz (die denknotwendigkeit
auf welcher der ganze beweis beruht ist somit die umkehrbarkeit einer ein-
deutigen wirkung in einem gebilde in dem von natur aus (von der struktur her)
keine richtung bevorzugt wird).
der rest ist ein kinderspiel. da eine verschiedene färbung der beiden letzge-
nannten felder ausscheidet brauchen wir nur noch zu beweisen dass es eine
lösung gibt (nun natürlich in der restgruppe) bei der eines dieser felder
schwarz ist (|1| immer als weiss vorausgesetzt). nun haben wir ja schon
gezeigt dass eine zweigliedrige teilkette immer die komplementärfarbe von
|1| annehmen kann und L und NB sind eine solche teilkette. folglich werden wir
in der zweiten gruppe erfolg haben.
(ich hätte sagt man mir den letzten absatz etwas unzulässig formuliert.
ein bisschen spass muss sein.)
Und hier die Reaktionen darauf:
Die Darstellung mag brillant sein. Mir ist sie zu umfangreich.
Die Kleinschreibung ermuntert meine Lesefreudigkeit nicht.
Straffung, Kürzung mancher ans Epische erinnernder Stellen und mehr Verweise wären wünschenswert.
Und eine Gliederung: Information - möglichst deutliche Darstellung des Problems - deutliche Darstellung der Problemlösung sollte genügen. --Wst
zu Wst:
tut mir leid: die kleinschreibung ist mein persönlicher tick. im übrigen wären natürlch
ein paar zeichnungen (graphen) mit weißen und schwarzen knoten mehr wert als eine
menge zeilen dieses textes da es sich hier im grunde um eine einfache symmetriefrage
handelt.
leider bin ich noch ziemlich neu in wiki und weiß z.b.
nicht wie man eine zeichnung einfügt (abgesehen davon dass ich erst mal eine erstellen
müßte.
was mich nebenbei wundert: die abstände im text (statt kommas) sind nicht mehr da. -- sigi
zu Schewek:
ich gebe dir 1000 euro wenn du mir beweisen kannst dass das
nur ein scherz (also falsch ist). wenn du das nicht kannst
möchte ich 500 euro von dir. ist das ein angebot? -- sigi
Ich bin kein Mathematiker oder Graphentheoretiker, kann den Beweis also nicht widerlegen. Kannst Du sagen, wo der Beweis veröffentlicht ist? So, wie er da steht, ist das nicht formal genug, dass man das einen Beweis nennen könnte. --Schewek
Ein Beweis muss nicht notwendigerweise formal aufgeschrieben sein, auch wenn das letztendlich recht mühsam ist. Bin aber auch der Meinung, dass in die Wikipedia keine mathematischen Beweise von diesem Kaliber gehören. Für sowas wäre ein MatheWiki besser geeignet. --Flups
Nochmal etwas klarer: Es ist nicht wichtig, ob der Beweis richtig oder falsch ist.
Die Wikipedia ist ein Nachschlagewerk, und kann demnach nur 'etabliertes Wissen' beinhalten. Und, das sehe ich so wie Flups, der Beweis selber gehört hier nicht hin, nur die Beweisidee (falls man die verständlcih darstellen kann) und ein Verweis auf die Originalveröffentlichung.
Auch der 'tick' der Kleinschreibung ist nicht akzeptabel, da die Wikipedia sich an die neue Rechtschreibung halten will. Ich denke, der Beweis sollte aud dem Artikel wieder raus, oder, falls es eine Veröffentlichung gibt, mit Verweis drinbleiben. --Schewek
Also ich schließe mich der Meinung an, dass die Wikipedia nicht der richtige Platz ist, einen ungeprüften neuen Beweis, der noch dazu ob der Geschichte des Problems einigermaßen dubios anmuten muss, zu veröffentlichen.
Der richtige Platz, sowas zu diskutieren wäre die Newsgroup de.sci.mathematik.
Davon abgesehen, lieber sigi:
Ich hab mich jetzt wirklich bemüht - aber der Beweis ist vollkommen unverständlich.
Soweit ich verstanden habe, teilst Du die Knoten des planaren Graphen in zwei Gruppen, wobei die eine einen Baum und die andere einen Wald bilden soll.
Diese färbst Du dann alternierend mit je zwei Farben.
So weit so gut.
Wie dieser Baum aber konkret konstruiert wird, verschließt sich mir.
Z.B. schreibst Du "nun ist es ja so dass bei einem neu abgetrennten land (nennen wir es N) immer zwei länder der nachberschaftskette (nennen wir sie L und R (für links und rechts)) sowohl mit |1| als auch mit N verbunden bleiben".
Das ist definitiv falsch, z.B. für das erste abgetrennte Land, das ja gar keine Nachbarn (abgesehen von |1|) haben kann.
lieber rade kutil
mit dir habe ich noch ein ganz besonderes hühnchen zu rupfen.
wieso nennst du den kurzbeweis den ich zuerst in topologie
veröffentlicht habe 'einen schmarrn' und löschst ihn einfach?
(vater vergib ihm er wußte nicht was er tat).
hast du dich schon einmal gefragt wie es kommt dass eine so
offensichtliche tatsache wie die färbung eines planaren graphen
mit 4 farben so schwierig zu beweisen ist dass man praktisch
gezwungen war alle nur denkbaren kombinationen per rechner
auszuprobieren ? (immerhin genial überhaupt zu erkennen dass
die zahl der möglichen kombinationen begrenzt ist).
könnte die schwierigkeit vielleicht daher kommen dass man unter
beweis normalereise eine induktion versteht also eine erweiterung
von n auf n + 1 (wenn dann n + 1 wieder als neues n genommen werden
kann ist die induktion vollständig und der beweis gelungen)?
nun ist es aber beim 4-farben-problem so dass eine erweiterung um
eins mehrere färbungsmöglichkeiten hat. will man also wissen ob
eine erlaubte darunter ist muss man sie der reihe nach ausprobieren.
umgekehrt ist es natürlich viel einfacher mehrere n + 1 färbungen
(egal ob erlaubt oder verboten)
auf eine gemeinsame n färbung zurückzuführen.
da es nun gar nicht darauf ankommt zu zeigen welche färbung
richtig ist sondern nur ob es überhaupt eine richtige gibt liegt
es sicherlich nahe sich zu fragen ob die vollständige induktion
auch umkehrbar ist. und das ist sie in der tat (auch wenn bisher
keiner davon gebrauch gemacht hat).
wenn ich zeigen kann dass eine unbekannte kombination angenommen
sie existiert sich so reduzieren lässt dass sie zu einer bekannten
kombination führt dann habe ich in der tat die existens der
unbekannten kombination bewiesen.
(wenn zum beispiel ein kind nur die zahlen von 1 bis 100 kennt
und nicht weiß ob es zahlen gibt die größer als 100 sind dann
könnte man ihm erklären dass eine zahl die um eins erweitert
wird eine größere zahl ergibt. folglich kann man 100 um eins
erweitern und erhält eine zahl die größer als 100 ist. man könnte
aber auch argumentieren dass angenommen es gäbe eine zahl die größer
ist als 100 dann könnte man von dieser zahl eins abziehen und würde
eine um eins kleinere zahl erhalten. von der könnte man dann wieder
eins abziehen und schließlich würde man sicherlich eine zahl erhalten
die kleiner als 100 ist. und da diese ja erkennbar existiert
existiert auch die unbekannte zahl von der man ausgegangen ist:)
nebenbei bemerkt: nachschlagewerk|standardwissen|neue rechtschreibung:
alles schmarrn (gebt es doch zu: am liebsten würdet ihr noch mit sie
(großgeschrieben) angeredet werden.)
wiki ist eine spielwiese für open-source-intelligenz. es gibt keinen
vorgegebenen inhalt - höchstens eine vorgegebene struktur(und auch die
ist verhandelbar)- alle inhalte sind angebote: wenn jemand darauf
reagiert (egal ob positiv oder negativ) umso besser.
ganz nebenbei bemerkt: das ist auch genau der grund warum ich hier
überhaupt etwas schreibe. wie ihr sicherlich schon bemerkt habt (siehe
auch: jehovas zeugen|freigeld)) ist die herrschende (standard)gesellschaft
für mich ein witz und das streben nach ruhm und anerkennung in diesem
misthaufen einfach lächerlich.
wenn ich wirklich einen beweis gefunden habe dann sollte ich dankbar sein
und allen die keinen finden konnten eine entschädigung bezahlen.
aber ich brauche mir nichts darauf einzubilden. ich bin ja auch nicht
stolz auf mich selbst wenn ich z.b. eine größere summe erbe.
--ein gewisser sigi.
zu "es gibt keinen vorgegebenen inhalt": Natürlich haben wir inhaltliche Vorgaben. Wir wollen eine Enzyklopädie erstellen und haben ein Kriterium, dem sich alles andere unterzuordnen hat, den neutralen Standpunkt. Und ich denke es ist Konsens, dass so ein schwerverständlicher Beweis nicht in eine Enzyklopädie gehört. Schreib eine kurze Zusammenfassung, etwas zur Geschichte seiner Entstehung o.ä. und einen Link/Literaturangabe zu einer Veröffentlichung. Das ist dann ein Teil eines Enzyklopädie-Eintrages. --Kurt Jansson
Sigi, deine "Umkehrung der Induktion" wird normalerweise "backward chaining" (vom Ziel zum Ausgangspunkt durch logisches Schließen) genannt und hat mit Induktion nichts zu tun. "Wenn man annimmt, dass eine gültige Färbung existiert, dann kann man die Kombination auf n - 1 reduzieren " - Ja, wenn man das annimmt, allerdings kann man so gar nicht zu einer Aussage kommen (denk mal an Münchhausen :) ). Du beweißt mit einer Annahme die Annahme selber. Bei einer solchen Induktion wäre dann nur ein Induktionsbeweiß "drin", also in der Art: Es existiert ein planarer Graph, der nicht vierfärbbar ist. Die Aussage sollte dann zu einem Widerspruch führen. Deine Methode ist, wie leicht einsehbar ist, falsch: Entferne alle Knoten bis auf einen, der entstehende Graph ist vierfärbbar, also ist es der ursprüngliche auch. Oder verstehe ich überhaupt nicht, worauf du hinaus willst? Du müsstest eine Operation finden, die die Vierfärbbarkeit des Graphen nicht verändert, unabhängig von einer Vorraussetzung, ob er vierfärbbar ist.
Zum Rest: Bist du so ein Pseudo-Revolutionär, der gegen alles ist? Ich glaube, du hast noch nicht ganz begriffen, was gesellschaftliche Konventionen sind, wie sie funktionieren und wozu sie da sind. Rechtschreibung ist da ein herrlich einfaches Beispiel: Sie vereinfacht die Kommunikation, macht Texte einfacher zu lesen und verhindert Missverständnisse. Es ist geradezu ein Gebot, sich nach den eigenen Fähigkeiten daran zu halten - und das Umgekehrte kannst du dir ja wohl selber denken. Deine Texte sind schwer zu lesen, wundere dich nicht, wenn sie irgendwann niemand mehr list. Nichts gegen "Revolution" oder wie man das auch immer nennen will, aber man sollte sie doch immer begründen können. --Vulture