CS170 Efficient Algorithms and Intractable Problems Section9

课程主页：

课程视频：

参考资料：

吴彧文（atyuwen）Algorithms.Exercises.solution

这次回顾Section 9。

假设maximal匹配的边集合为

$E^1= \{(u_1^1,v_1^1),\ldots,(u_n^1,v_n^1)\}$

maximum匹配的边集合为

$E^2= \{(u_1^2,v_1^2),\ldots,(u_m^2,v_m^2)\}$

任取$e=(u,v)\in E^1$，或者$e\in E^2$，或者$e\not \in E^2$，对于第二种情形，$E^2$中必然存在一条边包含$u$或$v$，这是因为如果该条件不满足，则$E^2$中可以添加$e$，这就与maximum匹配的定义矛盾。

因此$E^1$中的每一条边或者和$E^2$中一条边对应，或者和$E^2$中两条边对应，假设这两种情形的数量分别为$x,y$，那么计算顶点的数量

$\begin{aligned} 2x + 2y & = 2n\\ 2x + 4y&= 2m \end{aligned}$

所以

$4n =4x + 4y \ge 2x + 4y = 2m\Rightarrow n \ge \frac m 2$

图片来自于吴彧文（atyuwen）Algorithms.Exercises.solution 7.23，该解答参考了大佬的做法。

假设二部图的两步分别为$U,V$，现在增加顶点$S,T$，其中$S$和$U$中每条边都相连，$T$和$V$中每条边都相连。

假设顶点覆盖为$C$，定义

$\begin{aligned} L&= C\cap U\\ R&= C\cap V\\ M&=U-L\\ N&=V-R \end{aligned}$

由于$C=L\cup R$，并且$C$为顶点覆盖，所以$M,N$之间必然不存在边，考虑割$(L\cup N\cup T,S\cup M\cup R)$，根据上图可知，割为

从而顶点覆盖正好对应了一个分割；反之，构造满足上述条件的图，即$M,N$之间不存在边，然后求出割$(S\cup M\cup R, L\cup N\cup T)$，那么$L\cup R$必然为顶点覆盖，从而分割也对应了一个顶点覆盖。

因此两者一一对应，求最小顶点覆盖的问题可以转化为求最小割的问题。

对于图$G=(V,E)$，构造$U=V$，以及子集$S_i$，其中子集的构造如下：

那么最小顶点覆盖对应于$U,S_i$的集合覆盖。