图3-使用给定函数着色的颜色
-
20-12-2019 - |
题
我有函数three_colorability(n,E),它给出了true(当具有这些边和顶点的图可以用3种颜色着色时)或false(如果不是)。(!没有参数知道什么已经被着色了) 我们假设这个函数在线性时间复杂度下工作。
我必须使用给定的函数对给定的无向图G进行3着色算法,该函数将在多项式时间内工作。
我不能来解决这个问题。
解决方案
添加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条边。
不隶属于 StackOverflow