二分图常见模型

  此处列举了二分图的常见模型,仅为记录。

  

最大独立集

内容

  最大独立集数+最小点覆盖数=顶点数

  

证明

  最大独立集与最小点覆盖集是互补的。

  对于点覆盖集:每条边至少选择一个点。

  对于独立集:每条边至少不选择一个点。

  因此,每个点覆盖集都与唯一的独立集互补,每个独立集也与唯一的点覆盖集互补。

  即,最大独立集与最小点覆盖集互补

  

应用

  由于二分图的特殊性质,根据König定理可得最大匹配数=最小点覆盖数。因此,最大独立集数+最小点覆盖数=最大独立集数+最大匹配数=顶点数。

  同样的,由于最大独立集与最小点覆盖集的互补关系,可以求取最小点覆盖集来间接求得最大独立集。

  

例题

UVALive3415 - Description and Solutions

  

König 定理

内容

  最大匹配数=最小点覆盖数

  

证明

  详细证明见:

  二分图König定理的证明(Matrix67)

  二分图König定理的网络流思路证明(Nero___)

  

求最小覆盖点集

  将二分图看做左子集右子集两个部分。

  在左子集中,对于每一个未被匹配的节点,都扩展出一棵匈牙利树,并将树上的节点进行标记。

  最小覆盖点集即为左子集中未被标记的节点右子集中被标记的节点

  详细证明见Matrix67。

  

例题

UVA11419 - Description and Solutions

  

最小路径覆盖

构图方法

  对于有向无环图$G=(V,E)$

  图中每个节点$a \in V$,拆成$a$、$a’$两点

  图中每条边$(u,v) \in E$,向$(u,v’)$连边

  最小路径覆盖即为顶点数-最大匹配数

  

构图思路

  对于所有简单路,每个点只会出现一次

  对于每条简单路,除了结尾节点都有唯一的后缀节点。

  

例题

UVALive3126 - Description and Solutions

本站总访问量次 | 本站访客数人次

Powered by Hexo | Designed by iTimeTraveler | Refined by CSHwang