图3-使用给定函数着色的颜色

Question

我有函数three_colorability（n，E），它给出了true（当具有这些边和顶点的图可以用3种颜色着色时）或false（如果不是）。(!没有参数知道什么已经被着色了） 我们假设这个函数在线性时间复杂度下工作。

我必须使用给定的函数对给定的无向图G进行3着色算法，该函数将在多项式时间内工作。

我不能来解决这个问题。

Answer 1

添加3个新节点，命名为 C1, C2 和 C3 它们代表的颜色。在新节点之间添加边 (C1,C2), (C2,C3) 和 (C1,C3).如果 three_colorability(V,E) 真的比 three_colorability(V+{C1,C2,C3},E+{(C1,C2),(C2,C3),(C1,C3)}) 也是如此。

对于每个（原始）顶点 v, three_colorability() 对于至少一个添加了两个边缘的图形返回true {(v,C1), (v,C2), (v,C3)}.例如。如果 three_colorability() 对于添加边的图形返回true {(v,C2), (v,C3)}, ，意思是 v 可以用颜色1着色。

要查找所有顶点的颜色，请逐步查找顶点颜色并在图中添加这2条边。