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

所有内容：NP与计算的难解性

6 划分问题

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

6.1 三维匹配问题

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

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

首先，很容易证明三维匹配问题是NP问题。只需要判断集合T’的大小是否为n，且包含X,Y,Z中每个元素一次。证明三维匹配问题是NPC的，可以通过3-SAT$\leq_p$≤p​三维匹配证明。
【3-SAT$\leq_p$≤p​三维匹配证明】
考虑任意的一个3-SAT实例，有n个变量$x_1,x_2,...,x_n$x1​,x2​,...,xn​和k个子句$C_1,C_2,...,C_n$C1​,C2​,...,Cn​。构造3DM实例X,Y,Z,T。
对于每一个变量，都有一个零件相对应。如图9所示。每个零件有Core（核心）元素、Tip（边梢）元素、Triple元组。每一个零件大大小为2k。k为子句的大小。
则，对于每一个变量$x_i$xi​，建立：
$A_i={a_{i,1},a_{i,2},...,a_{i,2k}}$Ai​=ai,1​,ai,2​,...,ai,2k​。
$B_i={b_{i,1},b_{i,2},...,b_{i,2k}}$Bi​=bi,1​,bi,2​,...,bi,2k​。
$t_{i,j}={(a_{i,j},a_{i,j+1},b_{i,j}}$ti,j​=(ai,j​,ai,j+1​,bi,j​。
构造的零件如图9所示。

图9 三维匹配的零件
对于每一个子句$C_t$Ct​加入两个元素$P_t,P_t'$Pt​,Pt′​，如果$C_{t}$Ct​包含$x_{j}$xj​，则加入三元组$P=(P_t,P_t',b_{j,2t})$P=(Pt​,Pt′​,bj,2t​)，显然一个$C_i$Ci​有三个三元组。
如果包含$\overline x_j$xj​，则加入$P=(P_t,P_t',b_{j，2t-1})$P=(Pt​,Pt′​,bj，2t−1​)；所以每个子句的三元组所包含的tip元组是不冲突的。即$C_i$Ci​和$C_j$Cj​的三元组中没有相同的b元素。如图10所示。

图10 从3-SAT到三维匹配的归约，第一部分
定义，如果$t_{ij}$tij​中的j为偶数，则称$t_{ij}$tij​为偶三元组，如果j为奇数，则$t_{ij}$tij​为奇三元组。
如果$b_{i,j}$bi,j​中的j为偶数，则称$b_{i,j}$bi,j​为偶tip，如果j为奇数，则称$b_{i,j}$bi,j​为奇tip。
可以看到，要想core元素都被包含，且不被重复包含，则必须要么选择全部的偶三元组，要么选择全部的奇三元组。定义如果选择了全部的偶三元组，则$x_{i}=0$xi​=0，否则，$x_i=1$xi​=1。
因此，可以看到，如果一个子句为1，则必然有一项的值为1，即选择该变量的所有奇三元组或所有偶三元组中。如果3-SAT是可满足的，则每个$C_t$Ct​的3个三元组中，至少有一个能够被选择。
对于每个没有被选择的tip元素，添加cleanup零件：$Q={q_i,q_i'}$Q=qi​,qi′​。即有$(n-1)k$(n−1)k个tip等待覆盖。并且添加三元组$(b_{i,j},q_i,q_i')$(bi,j​,qi​,qi′​)。
如图11完成了3-SAT到三维匹配的归约。

图11 从3-SAT到三维匹配的归约，第二部分
此时，我们令：
$X=$X={$a_{i,j}(j是偶数)$ai,j​(j是偶数)} $\vee$∨{$p_j$pj​} $\vee$∨ {$q_j$qj​} 。
$Y=$Y={$a_{i,j}(j是奇数)$ai,j​(j是奇数)} $\vee$∨{$p_j'$pj′​} $\vee$∨ {$q_j'$qj′​} 。
$Z=$Z={$b_{i,j}$bi,j​} 。
$T=$T={所有构造出来的三元组}。
可以看到，X，Y，Z三个集合的大小是相等的。
【对于每一个3-SAT实例】
假设有一个真值赋值，则如果$x_i=1$xi​=1，则选择$x_i$xi​对应的变量零件的所有奇三元组。若果$c_j$cj​包含$x_i$xi​，则$c_j$cj​为1，则选择$(p_j,p_j',b_{t,2j})$(pj​,pj′​,bt,2j​)，因为$b_{t,2j}$bt,2j​为偶tip，因此没有被覆盖。如果$x_i=0$xi​=0，则选择$x_i$xi​对应的变量零件的所有偶三元组。若果$c_j$cj​包含$\overline x_i$xi​，则$c_j$cj​为1，则选择$(p_j,p_j',b_{t,2j-1})$(pj​,pj′​,bt,2j−1​)，因为$b_{t,2j-1}$bt,2j−1​为奇tip，因此没有被覆盖。剩余没有被选中的tip元组被cleanup零件覆盖。
因此最终所有的元素都只被覆盖一次。
因此一个完美的三维匹配为：
$T=$T={变量中选择的三元组}$\vee$∨{子句中选择的三元组}$\vee$∨{cleanup中的三元组}
【对于一个三维匹配实例】
如果有一个完美三维匹配，则每个子句零件中的3个元组必须有一个被选择，则$c_j$cj​为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$≤p​三着色，来证明三着色问题是NPC的。
【3-SAT$\leq_p$≤p​三着色】
首先对于每一个变量，添加结点$v_i$vi​和$\overline v_i$vi​。添加结点T（真结点）、F（假结点）、B（基点）。用边连接每一对结点$v_i$vi​和$\overline v_i$vi​。再连接这些结点与基点。也将真结点、假结点、基点连接起来。如图12所示。

图12 三着色问题的归约的开始部分
于是，在G的任何三着色中，结点$v_i$vi​和$\overline v_i$vi​必须着不同的颜色，并且都必须与基点的颜色不同。
在G的任何三着色中，真结点、假结点和基点一定以某种顺序得到全部的3种颜色。可以根据什么结点得到什么颜色原则，使得这3个结点分别得到真色、假色和基色。因此$v_i$vi​和$\overline v_i$vi​中只有一个得到真色，另一个得到假色。
考虑子句$x_1 \vee \overline x_2 \vee x_3$x1​∨x2​∨x3​，即这个$x_1$x1​, $\overline x_2$x2​, $x_3$x3​三个结点中至少有一个着真色。现在插入一个小子图，使得任何能扩展到该小子图的三着色必须至少给$x_1$x1​, $\overline x_2$x2​, $x_3$x3​着一个真色。
这样的子图如图13所示。

​图13 附加的子图
则，必须至少给$x_1$x1​, $\overline x_2$x2​, $x_3$x3​着一个真色，才能使得子图实现三着色（否则会出现颜色冲突）。如图14为子图的三着色实例。

图14 子图的三着色方案
可以论证3-SAT实例时可满足的当且仅当子图有三着色方案。即3-SAT$\leq_p$≤p​三着色，因此三着色问题是NPC的。

,.♥,.,.♥,.,.♥,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥♥,.,.♥,.,.♥,.,.♥,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥,.,.♥
广告时间：
本宝宝开通了一个公众号，记录日常的深度学习和强化学习笔记。希望大家可以共同进步，嘻嘻嘻！求关注，爱你呦！