二分图最大匹配的贪心解法及证明
2012-08-06
二分图最大匹配问题的经典解法是匈牙利算法，匈牙利算法描述起来很简洁，但有一个不大好理解的实现。我没弄懂匈牙利算法的时候，自己想出来一个贪心解法。网上也有这种做法的介绍，但没有证明。凑巧，看到一篇介绍贪心算法正确性证明方法的文章(《如何证明贪心算法是最优 using exchange argument》)，找到了思路，遂尝试做证明如下。
问题描述：设 \(G = (V,E)\) 是一个无向图，若顶点集$V$可以分为两个不相交的子集\({V_1}\), \({V_2}\)之并，而边集$E$中每条边相关联的顶点恰好分属这两个不同的子集，则称$G$为二分图，记为\(G = ({V_1}, {V_2}, E)\)。设$M$是二分图$G$的子图，且$M$的边集$E$中任意两条边都不依附于同一个顶点，则称$M$是一个匹配。选择这样的子图中边数最大的图称为二分图的最大匹配问题。
贪心算法描述：
1. 如果$E$非空，转2，否则算法结束；
2. 找出${V_1}$中度最小的顶点集${V'_1}$，选出与这些顶点相连的边、顶点，得到图\(G' = ({V'_1},{V'_2},E')\)；
3. 在${V'_2}$中找出度最小的“一个”顶点${v_b}$，并在${V'_1}$找出与之关联的点${v_a}$；
4. 将边\(\left\langle {{v_a},\left. {{v_b}} \right\rangle } \right.\)添加到匹配中去，在原图中删除${v_a}$, ${v_b}$及相应的边，转1.
证明：
令贪心解为$A$. 由于贪心解对边的选取顺序有规定，所以对于一个给定的最优解（最优解本身不包含边的选取顺序，如匈牙利算法，匹配包含的边一直交替变换），不妨让它尽量按照和A相匹配的顺序添加边. 下面证明，贪心解是最优解（下面过程所使用记号的意义同上述算法描述）.
假设$A$不是最优解，而最优解$O$是和$A$最接近的最优解，即$O$是（调整顺序后的）最优解中和$A$相同边数最多的，并设$O$与$A$前$K$步选择相同，第$K+1$次不同，即: $(1)$ $O$没有选择$V$中的顶点，$(2)$ $O$选择了$V$中的顶点，但没有选择$V$中度最小的顶点.
先用反证法否定$(1)$. 现在依次可得出以下几个结论：
1. ${V'_1}$中的点不出现在$O$中，这是条件假设；
2. ${V'_2}$中的点都在$O$中，否则，$O$还可以添加至少一条边，与$O$是最优解矛盾；
3. 设$A$在第$K+1$步选择了边\(\left\langle {{v_a},\left. {{v_b}} \right\rangle } \right.\)，$O$在第$K+1$步选择了边\(\left\langle {{v_c},\left. {{v_d}} \right\rangle } \right.\)，其中，\({v_a} \in {V'_1}\)，\({v_c} \in {V_1} - {V'_1}\)，\({v_b} \in {V'_2}\)；
4. 与${v_c}$相关联的其他顶点必在$O$中，否则，设${v_d}$是其中不在$O$中的顶点，则在$O$中用边\(\left\langle {{v_a},\left. {{v_b}} \right\rangle } \right.\)和\(\left\langle {{v_c},\left. {{v_d}} \right\rangle } \right.\)替换边\(\left\langle {{v_c},\left. {{v_b}} \right\rangle } \right.\)，得到一个新解，该解边数比$O$的边数多，与$O$是最优解矛盾；
5. 设${v_d}$是与${v_c}$相关联的顶点，又设${v_e}$是$O$中与之关联的顶点。那么，将$O$中的边\(\left\langle {{v_c},\left. {{v_b}} \right\rangle } \right.\)和\(\left\langle {{v_d},\left. {{v_e}} \right\rangle } \right.\)替换成边\(\left\langle {{v_a},\left. {{v_b}} \right\rangle } \right.\)和\(\left\langle {{v_c},\left. {{v_d}} \right\rangle } \right.\)，也是最优解，但该最优解比$O$更接近$A$，与假设矛盾！
现在否定了$(1)$，对于$(2)$，可将其放在子图$G'$中作类似讨论，同样予以否定。
证毕
证完了感觉好像不大漂亮，很可能证错了。还请有心人帮忙检查。
comments powered by Disqus