三着色问题是NP完全的

【图着色问题】
在图着色问题中,试图给图G中的每一个结点分配颜色,使得如果(u,v)是一条边,则边的两个结点的颜色不同。目标是使用很少的几种颜色做到这一点。使用的颜色数量为k。图着色问题可以阐述为:任意给图G和界限k,问G有k-着色吗?
三着色问题是NP完全的
有一个图G是二可着色的当且仅当它是二部图(这里不对齐进行证明)。对于3种颜色的情况,已经比较复杂了。三着色问题其实是一个NP完全问题。首先很容易证明其是一个NP问题。这里通过证明3-SAT\leq_p三着色,来证明三着色问题是NPC的。
【3-SAT\leq_p三着色】
首先对于每一个变量,添加结点v_i\overline v_i。添加结点T(真结点)、F(假结点)、B(基点)。用边连接每一对结点v_i\overline v_i。再连接这些结点与基点。也将真结点、假结点、基点连接起来。如图12所示。
在这里插入图片描述
图12 三着色问题的归约的开始部分
于是,在G的任何三着色中,结点v_i\overline v_i必须着不同的颜色,并且都必须与基点的颜色不同。
在G的任何三着色中,真结点、假结点和基点一定以某种顺序得到全部的3种颜色。可以根据什么结点得到什么颜色原则,使得这3个结点分别得到真色、假色和基色。因此v_i\overline v_i中只有一个得到真色,另一个得到假色。
考虑子句x_1 \vee \overline x_2 \vee x_3,即这个x_1, \overline x_2, x_3三个结点中至少有一个着真色。现在插入一个小子图,使得任何能扩展到该小子图的三着色必须至少给x_1, \overline x_2, x_3着一个真色。
这样的子图如图13所示。
在这里插入图片描述
​图13 附加的子图
则,必须至少给x_1, \overline x_2, x_3着一个真色,才能使得子图实现三着色(否则会出现颜色冲突)。如图14为子图的三着色实例。
在这里插入图片描述
图14 子图的三着色方案
可以论证3-SAT实例时可满足的当且仅当子图有三着色方案。即3-SAT\leq_p三着色,因此三着色问题是NPC的.

0

Leave a Reply

Your email address will not be published.