Färben Sie einen Graphen so, dass jeder Knoten entweder farbig oder neben einem farbigen Knoten liegt.

Question

Angenommen, Sie haben einen verbundenen ungerichteten Graphen G. Sie möchten, dass jeder Knoten in G entweder farbig oder neben einem farbigen Knoten ist. Entwerfen Sie einen Algorithmus, um den Graphen G entsprechend zu färben. Sie dürfen nur Boden (n/2) Knoten färben, wobei n die Gesamtzahl der Knoten ist.

Ich habe versucht, eine Lösung, aber ich erkannte, dass es die Probleme mit den Einschränkungen nicht vollständig löst, und ich möchte entweder einen Anstupser oder zu sagen, dass ich auf der falschen Spur bin.

Meine Lösung bestand im Wesentlichen darin, BFS auszuführen und die Knoten auf jeder dritten "Ebene" zu färben. Aber ich habe eine Instanz gefunden, bei der das fehlschlägt - nur eine Liste von drei Knoten. Wenn ich entweder den Kopf oder den Schwanz färbe, dann wird einer der Knoten Entfernung 2 von einem farbigen Knoten entfernt sein, und ich bin nicht ganz sicher, wie man garantiert, dass der mittlere Knoten gefärbt wird.

Answer 1

Wählen Sie eine Wurzel und generieren Sie einen Spanning-Tree mit, sagen wir DFS.

Dann färben Sie die Knoten in jeder 2. Ebene. Wählen Sie aus, ob Sie die geraden oder ungeraden Ebenen farbig gestalten möchten, je nachdem, welche Farbe die wenigsten Knoten haben würde.