二分图匹配 匈牙利算法与HK算法

二分图匹配 匈牙利算法与HK算法

二分图匹配 1.一个二分图中的最大匹配数等于这个图中的最小点覆盖数 König 定理是一个二分图中很重要的定理,它的意思是,一个二分图中的最大匹配数等于这个图中的最小 点覆盖数。如果你还不知道什么是最小点覆盖,我也在这里说一下:假如选了一个点就相当于覆盖了以它 为端点的所有边,你需要选择最少的点来覆盖所有的边。 2.最小路径覆盖=|G|-最大匹配数   在一...
05月14日 502
  1. .01
  2. .02