CS170 Efficient Algorithms and Intractable Problems Section9

距离上次更新已经 1409 天了，文章内容可能已经过时。

课程主页：

https://cs170.org/

https://inst.eecs.berkeley.edu/~cs170/fa18/

课程视频：

https://www.bilibili.com/video/BV1wK411g7ck

参考资料：

吴彧文（atyuwen）Algorithms.Exercises.solution

这次回顾Section 9。

1. Maximal Matching

假设maximal匹配的边集合为

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

maximum匹配的边集合为

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

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

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

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

所以

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

2. Bipartite Vertex Cover

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

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

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

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

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

• $L\to R$的边

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

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

3. Reducing Vertex Cover to Set Cover

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

• 对于$v\in V$，定义集合$S_v$：
  • $S_v=\{v\}\cup \{u|(v,u)\in E\}$

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