划分问题:三维匹配问题、图着色问题

6 划分问题

讨论两个划分问题,一个是三维匹配问题,另一个是图着色问题。对于三维匹配问题,要求搜索把对象集合分成子集的方式。对于图着色问题,要求划分图中的结点。

6.1 三维匹配问题

【三维匹配问题】
给定三个不相交的集合X、Y、Z,三个集合的大小都为n。给定一个三元组集合T \subseteq X \times Y \times Z,集合T的大小为m。
问:T中是否存在一个大小为n的子集T’,这个子集恰好包含X,Y,Z每个元素一次。
三维匹配问题其实是集合覆盖和集合包装问题的特例。

6.2 三维匹配问题是NP完全的

首先,很容易证明三维匹配问题是NP问题。只需要判断集合T’的大小是否为n,且包含X,Y,Z中每个元素一次。证明三维匹配问题是NPC的,可以通过3-SAT\leq_p三维匹配证明。
【3-SAT\leq_p三维匹配证明】
考虑任意的一个3-SAT实例,有n个变量x_1,x_2,…,x_n和k个子句C_1,C_2,…,C_n。构造3DM实例X,Y,Z,T。
对于每一个变量,都有一个零件相对应。如图9所示。每个零件有Core(核心)元素、Tip(边梢)元素、Triple元组。每一个零件大大小为2k。k为子句的大小。\
则,对于每一个变量x_i,建立:
A_i={a_{i,1},a_{i,2},…,a_{i,2k}}
B_i={b_{i,1},b_{i,2},…,b_{i,2k}}
t_{i,j}={(a_{i,j},a_{i,j+1},b_{i,j}}
构造的零件如图9所示。
在这里插入图片描述
图9 三维匹配的零件
对于每一个子句C_t加入两个元素P_t,P_t’,如果C_{t}包含x_{j},则加入三元组P=(P_t,P_t’,b_{j,2t}),显然一个C_i有三个三元组。
如果包含\overline x_j,则加入P=(P_t,P_t’,b_{j,2t-1});所以每个子句的三元组所包含的tip元组是不冲突的。即C_iC_j的三元组中没有相同的b元素。如图10所示。
在这里插入图片描述
图10 从3-SAT到三维匹配的归约,第一部分
定义,如果t_{ij}中的j为偶数,则称t_{ij}为偶三元组,如果j为奇数,则t_{ij}为奇三元组。
如果b_{i,j}中的j为偶数,则称b_{i,j}为偶tip,如果j为奇数,则称b_{i,j}为奇tip。
可以看到,要想core元素都被包含,且不被重复包含,则必须要么选择全部的偶三元组,要么选择全部的奇三元组。定义如果选择了全部的偶三元组,则x_{i}=0,否则,x_i=1
因此,可以看到,如果一个子句为1,则必然有一项的值为1,即选择该变量的所有奇三元组或所有偶三元组中。如果3-SAT是可满足的,则每个C_t的3个三元组中,至少有一个能够被选择。
对于每个没有被选择的tip元素,添加cleanup零件:Q={q_i,q_i’}。即有(n-1)k个tip等待覆盖。并且添加三元组(b_{i,j},q_i,q_i’)
如图11完成了3-SAT到三维匹配的归约。
在这里插入图片描述
图11 从3-SAT到三维匹配的归约,第二部分
此时,我们令:
X={a_{i,j}(j是偶数)} \vee{p_j} \vee {q_j} 。
Y={a_{i,j}(j是奇数)} \vee{p_j’} \vee {q_j’} 。
Z={b_{i,j}} 。
T={所有构造出来的三元组}。
可以看到,X,Y,Z三个集合的大小是相等的。
【对于每一个3-SAT实例】
假设有一个真值赋值,则如果x_i=1,则选择x_i对应的变量零件的所有奇三元组。若果c_j包含x_i,则c_j为1,则选择(p_j,p_j’,b_{t,2j}),因为b_{t,2j}为偶tip,因此没有被覆盖。如果x_i=0,则选择x_i对应的变量零件的所有偶三元组。若果c_j包含\overline x_i,则c_j为1,则选择(p_j,p_j’,b_{t,2j-1}),因为b_{t,2j-1}为奇tip,因此没有被覆盖。剩余没有被选中的tip元组被cleanup零件覆盖。
因此最终所有的元素都只被覆盖一次。
因此一个完美的三维匹配为:
T={变量中选择的三元组}\vee{子句中选择的三元组}\vee{cleanup中的三元组}
【对于一个三维匹配实例】
如果有一个完美三维匹配,则每个子句零件中的3个元组必须有一个被选择,则c_j为1。如果被选择的子句三元组中有偶tip,则说明该项的值为1,否则,该项的值为0。即存在一个可满足的真值赋值。此时,已经完成了3-SAT到三维匹配的证明。因此,三维匹配问题是一个NPC问题。

6.3 图着色问题

【图着色问题】
在图着色问题中,试图给图G中的每一个结点分配颜色,使得如果(u,v)是一条边,则边的两个结点的颜色不同。目标是使用很少的几种颜色做到这一点。使用的颜色数量为k。图着色问题可以阐述为:任意给图G和界限k,问G有k-着色吗?

6.4 三着色问题是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.