 3 Färbungsproblem |
PikBube
Grünschnabel
Dabei seit: 14.04.2009
Beiträge: 1
 |
|
Moin,
ich interessiere mich derzeit für das P vs. NP Problem und speziell für das 3-Färbungsproblem für Graphen, welches ja auch NP-vollständig sein soll. Bitte, schmeißt mich nicht sofort mit Kommentaren wie "Wieso sollte ausgerechnet du das Problem lösen?" zu. Ich weiß selber, dass das ziemlich unwahrscheinlich ist und ich mich hier wahrscheinlich lächerlich mache. Aber es würde mir ehrlich gesagt auch keine Ruhe geben, wenn ich mich dauernd fragen würde, ob mein Ansatz denn richtig gewesen wäre.
Also schaut euch es erstmal an und danach könnt ihr mir gerne meine Fehler aufzeigen. Danke.
Zurück zum Thema:
Ich gehe davon aus, dass ihr wisst, was das k-Färbungsproblem ist. Das "3-Färbungsproblem" ist eine speziellere Form von diesem. Es wird nicht mehr allgemein gefragt, ob der Graph mit k Farben färbbar ist, sondern danach, ob der Graph mit nur 3 färbbar ist.
Für dieses Problem wurde die NP-Vollständigkeit nachgewiesen.
Ich habe folgenden Ansatz gewählt:
Die Kante ist die einzige Einschränkungsmöglichkeit für das Problem. Die Kante kann aber nur so einschränken, dass der eine Farbwert auf dem Punkt A nicht auf dem Punkt B liegt. Um nun eine 3-Färbbarkeit zu verhindern, kann man das nur, indem man einen Widerspruch erzeugt. Man kann das als Reduzieren von Färbungsmöglichkeiten interpretieren.
Der Widerspruch kann dann auch nur wie folgt aussehen:
Die Kante verbindet zwei gleichfarbige Punkte.
1. Das passiert, wenn eine Kante ein Punkt mit sich selbst verbindet.
2. Die Kante verbindet zwei Punkte von denen man weiß, dass sie die gleiche Farbe haben.
Punkt 1 ist nicht das Problem. Man guckt dann einfach für jeden Punkt nach, ob er eine solche Kante hat oder nicht.
Punkt 2 ist komplizierter.
Folgende Fragen helfen einen weiter.
Sind die Möglichkeiten für Weitergabe von Punktwerten begrenzt und falls ja, wie lauten sie?
Es gibt prinzipiell nur eine Möglichkeit zum Weitergeben von Farbwerten beim 3-Färbungsproblem. Dabei machen wir uns die feste Anzahl von Farben zunutze.
Stellen euch folgende Anfangssituation vor:
Man hat 2 Punkte und will, dass die beiden Punkte den gleichen Wert besitzen. Für jeden dieser Punkte gibt es 3 Möglichkeiten einer Färbung.
Dazu hat man die Möglichkeit Kanten zu bilden und neue Punkte zu schaffen.
Kanten können aber nur die Möglichkeiten einer Färbung reduzieren, also müsste man, wenn man zwei Punkten den gleichen Wert geben will, bei beiden Punkten auch das gleiche abziehen.
Man muss hierbei beachten, dass man noch keine Punkte hat, die den gleichen Wert haben. Und man immer zwei verschiedene Werte abziehen muss, damit der Punkt nur eine Möglichkeit für eine Farbwahl hat.
Also fügt man erstmal 2 Punkte hinzu, da man 2 Werte abziehen muss. Da anfangs keine Punkte mit gleichen Farbwert existieren, muss man die zwei Anfangspunkte auch mit den beiden neuen Punkten verbinden, um sicherzustellen, dass auch wirklich das gleiche bei den Anfangspunkten abgezogen wird.
Außerdem müssen die beiden neuen Punkte verschiedene Werte haben, was man durch eine direkte Kante zwischen den beiden neuen Punkten erreicht.
Sowas hat immer zwei 3er-Cliquen, die eine Kante gemeinsam haben, als Folge.
Wichtig ist noch zu beachten, dass beim Weitergeben von Farbwerten neue Cliquen entstehen können. Die neuen Cliquen sind dann gleichberechtigt wir die normalen Cliquen.
Was ist nun, wenn es mehrere Punkte mit gleichen Wert gibt?
Diese Punkte können anfangs nur durch normale 3er-Cliquen entstanden sein. Für diese Methode gelten aber trotzdem die gleichen Bedingungen wie für normale Cliquen, sodass eigentlich keine neue Weitergabetechnik entsteht. Die Cliquen müssen zwar nicht mehr schon am Anfang direkt einsehbar sein, doch wenn man alle Kanten der Punkte mit gleichen Farbwert zusammenlegt, dann hat man wieder normale 3er-Cliquen, da die Punkte mit gleichen Wert immer durch zwei 3er-Cliquen miteinander verbunden sind.
Der Algorithmus sieht dann wie folgt aus:
G = (V,E) ist ein ungerichteter Graph
C-Speicher …. Cliquenspeicher
P(X)-Bank …. Jeder Punkt kriegt einen eigenen Speicher (seine Bank)
z …. die höchste Kantenanzahl an irgendeinem Punkt am Anfang
Werte .... mit Werte/Farbwerte werden die Farben bezeichnet
Algorithmus-Beginn
1. Schritt (Suche nach 3er-Cliquen)
Zum Finden von 3er-Cliquen wird das Backtracking-Verfahren eingesetzt oder andere bessere Verfahren. Die Cliquensuche ist für konstante Cliquen in polynomieller Zeit zu lösen.
Die gefundenen Cliquen im C-Speicher abgelegt.
Die Laufzeit für den ersten Schritt: O(V^3)
2. Schritt (Füllen der Banken)
Jede P-Bank wird mit den Punkten, die einen Abstand von 3 Kanten zum jeweiligen Punkt haben, gefüllt.
Dieser Schritt ist nötig, um später die neu entstehenden 3er-Cliquen zu finden.
Die Laufzeit für den zweiten Schritt: O( V*z^3 )
Wir nehmen (den worst-case) an, jeder Punkt hätte die gleiche Kantenanzahl, damit keine Unterschätzung geschieht, wird die höchste Kantenanzahl (z) im Graphen gewählt. Diese wird hoch drei genommen, weil sich die Anzahl der Kanten pro Kante mal sich selbst genommen werden muss. Da dies für jeden Punkt geschehen muss, wird noch mit der Anzahl der Punkte multipliziert.
3. Schritt (Suche nach neu entstehenden 3er-Cliquen)
Teilschritt 1
Im C-Speicher überprüfen, ob 3er-Cliquen eine Kante gemeinsam haben.
Falls zwei 3er-Cliquen gefunden werden, die eine Kante gemeinsam haben, wird zu Teilschritt 2 gewechselt. Danach werden die 2 übrigen Punkte und deren Banken verschmolzen.
Laufzeit Teilschritt 1: O( (V^3*3)^2 )
Wir nehmen an, die Suche nach den 3er-Cliquen hätte ergeben, dass jede Kombination eine 3er-Clique bildet, sodass wir nun alle Kombinationen kontrollieren müssen. Dazu muss jede Clique in ihre Kanten zerlegt werden. Bei 3er-Cliquen wären das 3 Kanten. Die Suche an sich verläuft dann quadratisch.
Teilschritt 2
Es muss vor dem Verschmelzen überprüft werden, ob eines der 2 Punkte in der Bank des anderen Punktes vorhanden ist.
Falls ja, ist eine neue 3er-Clique entstanden.
Die neue 3er-Clique wird dem C-Speicher hinzugefügt und Teilschritt 1 wird weiterverfolgt.
Laufzeit Teilschritt 2: O( (V*z^3)^2 )
Wir nehmen an, dass jeder Punkt mit jeder Bank verglichen werden muss. Die Suche verläuft quadratisch.
Notiz: Selbst wenn der Vergleich kein positives Ergebnis liefert, wird immer noch verschmolzen.
Letzter Schritt (Überprüfung auf 3-Färbbarkeit)
Es wird ein ähnlicher Algorithmus wie am Anfang gestartet, nur mit dem Unterschied, dass nun nach Kanten gesucht wird, die zum selben Punkt zurückführen (R-Kanten).
Falls solche Kanten gefunden werden, ist der Graph nicht 3-färbbar.
Laufzeit: (V^2)
Notiz: Es können schon anfangs solche R-Kanten existieren, diese Kanten machen dann jede Färbung an sich schon widersprüchlich/unerfüllbar, was zwar auch eine 3-Färbung einschließt und darum egal sein sollte, da die R-Kante so oder so später gefunden wird. Notfalls könnte man aber vorab eine Suche nach solchen Kanten (Laufzeit auch V^2) durchführen.
Unnatürliche R-Kanten entstehen beim Abarbeiten des Algorithmus, wenn der Graph verlangt, dass ein Punkt nicht mit der eigenen Farbe gefärbt werden darf.
Algorithmus-Stopp
Und was haltet ihr davon?
Eine längere Version füge ich den Anhang hinzu und möchte mich für die dauernden Rechtschreibkorrekturen entschuldigen... Da schleichen sich immer wieder welche rein.
Der Beginner-Thread ist auf:
http://board.gulli.com/thread/1358346-3-frbungsproblem/
Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von PikBube: 14.04.2009 20:54.
|
|
14.04.2009 20:52 |
|
|
ed209
Routinier
Dabei seit: 07.09.2006
Beiträge: 324
|
|
Was willst du überhaupt zeigen? Daß man das 3-Färbeproblem in polynomieller Zeit lösen kann, also daß P = NP sei?
Du solltest bevor du etwas zeigst, in etwa die Richtung aufzeigen wo du hinwillst.
| Zitat: |
Der Algorithmus ist „grob“ , aber ich wollte den Algorithmus lieber grob und leicht einsehbar als
sauber, aber dafür ungleich länger haben. Es gibt bestimmt einige von Ihnen, die bessere
Suchalgorithmen für die einzelnen Schritte kennen, aber ich denke, dass er in dieser Form für den
Beweis ausreicht.
|
Der Algorithmus wird nicht leichter einsehbar, dadurch daß er unsauber formuliert ist.
Du wirfst mit Begriffen wie "verschmelzen" um Dich, die du nicht definiert hast. Ausserdem ist bei den verschiedenen Schritten in deinem Algorithmus nicht klar, wie oft sie ausgeführt werden.
Pseudo-Code würde helfen.
Gruß,
ED
|
|
|
23.04.2009 14:48 |
|
|
|
