Zeichnen Sie die 3-Farben-Färbung mit der angegebenen Funktion

Question

Ich habe die Funktion three_colorability(n,E), die die Ausgabe „true“ (wenn der Graph mit diesen Kanten und Eckpunkten mit drei Farben gefärbt werden kann) oder „false“ (falls nicht) liefert.(! Es gibt keinen Parameter, um zu wissen, was bereits gefärbt wurde) Wir gehen davon aus, dass diese Funktion in der linearen Zeitkomplexität funktioniert.

Ich muss unter Verwendung der angegebenen Funktion einen 3-Farben-Algorithmus für den gegebenen ungerichteten Graphen G erstellen, der in polynomieller Zeit funktioniert.

Ich kann hier keine Lösung finden.

Answer 1

Fügen Sie 3 neue Knoten mit dem Namen hinzu C1, C2 Und C3 nach Farbe, die sie darstellen.Fügen Sie Kanten zwischen neuen Knoten hinzu (C1,C2), (C2,C3) Und (C1,C3).Wenn three_colorability(V,E) ist wahr als three_colorability(V+{C1,C2,C3},E+{(C1,C2),(C2,C3),(C1,C3)}) stimmt auch.

Für jeden (ursprünglichen) Scheitelpunkt v, three_colorability() gibt für mindestens einen der Graphen mit hinzugefügten zwei Kanten „true“ zurück {(v,C1), (v,C2), (v,C3)}.Z.B.Wenn three_colorability() gibt für ein Diagramm mit hinzugefügten Kanten „true“ zurück {(v,C2), (v,C3)}, es bedeutet das v kann mit Farbe 1 eingefärbt werden.

Um die Farbe für alle Scheitelpunkte zu ermitteln, ermitteln Sie schrittweise die Scheitelpunktfarbe und fügen Sie diese beiden Kanten in einem Diagramm hinzu.