Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Liegt das Vierfarbenproblem in NP
Meines Kenntnisstandes nach ist die Vierfärbbarkeit beliebiger Landkarten zwar praktisch bewiesen, aber der theoretische Beweis ist wohl sehr schwer und bislang nicht erbracht (Fermat war ja auch ein schwieriger Fall).
Die Vierfärbbarkeit beliebiger Landkarten ist ja bei graphentheoretischer Betrachtung das NP Problem k-Col für k=4. Jedoch beschränken ja Polygon basierte zweidimensionale Landkarten die Menge der möglichen Graphen auf eben diejenigen für die es definitiv geht.
Hier nun meine Fragen:
Ist das Problem aufgrund dieser Tatsache nicht der NP-Klasse zuzurechen?
Ist es in P?
Was sind die schnellsten Algorithmen für dieses Problem in O-Notation nach Landau?
Ich hoffe, es weiß jemand eine Antwort darauf!
Ciao
John
Es gibt einen Algorithmus inO(V^2)
Siehe http://www14.in.tum.de/lehre/2004WS/ds/2005-02-08.pdf
Beschrieben ist er anscheinend z.B. auf: http://www.math.gatech.edu/~thomas/FC/fourcolor.html
Sieht aber kompliziert aus 
Liegt das Vierfarbenproblem in NP
Tausend Dank erstmal!
Werde mir den Algorithmus mal zu Gemüte ziehen 
Bis demnächst
John
P.S.: Bin nämlich hobbymäßig auch an einem Algo dran - ist aber noch nicht spruchreif…
Bericht erbeten! 
4FP in NP…
Werde ich tun!
Mein Ziel ist O(|V|). Mal sehen, ob es die grauen Zellen zulassen…
Ciao
John
da bin ich ja mal gespannt viel erfolg!
Na, was ist in den letzten 2 Monaten mit den grauen Zellen passiert?
Liegt das Vierfarbenproblem in NP
Die grauen Zellen arbeiten zwar auf Hochtouren, nur leider hab ich berufl. (bin selbständig) viel zu tun, so dass ich zwar weiter gemacht habe, aber noch nicht an dem Punkt bin, über Ergebnisse zu reden.
Muss auch noch ein paar Grundkomponenten machen, die mir in meiner Sammlung fehlen, um mit den “Kanonen der Graphen auf den Spatz” zu schiessen
Ich melde mich, sobald ich die ersten Karten in O(|V|) koloriert bekomme!
Ich habe Akne. Mein Problem ist NP-vollständig.
genau wie deine mutter.
badideldidel… also afaik IST die Vierfärbbarkeit von Landkarten bewiesen… mit meinem beschränkten Kenntnisstand würd’ ich das jetzt einmal der Tatsache zu schreiben (Deppenleerzeichen just for fun), dass der K5 der erste nichtplanare vollständige Graph ist, woraus folgt, dass der K4 wohl noch planar ist (sieht man ja auch gleich: man kritzelt ein Quadrat, baut eine Diagonale ein, und verbindet das verbleibende nicht verbundene Knotenpaar mit einer umständlichen Schleife um den bisherigen Graphen herum). Und man kann auch Landkarten in Graphen transformieren, indem man die Gebiete als Knoten sieht, und die gemeinsamen Grenzen zweier Gebiete als Kanten zwischen den entsprechenden Knoten. Und jetzt geht’s halt noch darum zu zeigen, dass es in Landkartengraphen nur maximal 4er-Cliquen geben kann, was den chromatischen Index auf maximal 4 beschränken würde. Könnte irgendwie damit zusammenhängen, dass zweidimensionale Landkarten ja irgendwie schonmal planar sind Man könnte sich dazu überlegen, wie man aus einem Landkartengraphen wieder eine Landkarte macht (gibt da natürlich überabzählbar viele Möglichkeiten, wenn wir keine diskret verpixelschweinerten hernehmen). Aber wenn man alle möglichen Landkarten zu einem gegebenen nichtplanaren Graphen betrachtet, kommt dabei vielleicht heraus, dass deren Anzahl nicht mehr so ganz unnull ist ← viel Geschwafel, das sich in einfachere Worte fassen lässt, die da lauten: “Wieviele Landkarten gibt es, bei denen mindestens fünf Gebiete paarweise gemeinsame Grenzen haben?”. Schön, zumindest hab ich erkannt, dass mein Post quasi inhaltslos ist. Wer syntaktische oder orthographische Fehler findet, möge sie sich goldgerahmt und hasenkostümiert im Pferdemantel an den Nasenring zangen.
Landkarten sind sogar 3-färbbar, wenn sie keine Dreiecke enthalten.
Also das zu entscheiden ist aber eins der klassischen NP-harten Probleme.
Landkarten sind sogar 3-färbbar, wenn sie keine Dreiecke enthalten???
@FordPerfect:Ne, das stimmt nicht:
| | 3 | |
| ------- |
| |1||2| |
| ------- |
| 4 |
|---|
Land 1,2 (Qudarate) grenzen an 3 (Rechteck) an, Land 4 umschließt die “1,2,3er” Insel!
Hier braucht 4 Farben!
doe; aber da hast doch dann ein dreieck!!
Im Graphen sind sowohl die Fläche 1 als auch die Fläche 2 ein Dreieck.
Dreieck/Viereck
Jo, als Graph gedacht sind es natürlich Dreiecke. Ich bin von der Graphdef. über die Länderflächen ausgegangen - mein Fehler!
[m]
1—2
/ \ /
\ 4 /
\ | /
3
[/m]
9öpö