在图中找一些路径,这些路径覆盖图中所有的顶点,每个顶点都只与一条路径相关联.
熟悉了这些概念之后,还有一个二分图最大匹配的Konig定理,这个定理的内容是:最大匹配 = 最小顶点覆盖.此处不证明其正确性.有了这个定理之后还可以得出一些二分图特有的公式:
这个公式,我们可以利用最大匹配来找到最大的独立集.而最大独立集和最小路径覆盖有个千丝万缕的关系.
POJ2271: 题目大意是,一群男孩和女孩共N人,某些男孩和女孩之间会发生恋爱关系(满足一定的关系),现在希望找到最多的孩子,他们之间不会发生恋爱关系.
分析:找到最多的孩子,没有恋爱关系,这实质上是找最大独立集.假设男孩在左有a个,女孩在右有b个,那么如果某男孩和某女