二分图漫谈

二分图

一个无向连通图 中存在 满足

被称作二分图.

二分图中没有奇环.

二分图的判定

使用双色染色法遍历整个图,如果遇到一条边两端的结点同色,则不是二分图,否则是二分图。

二分图匹配

匹配:任意两条边都没有公共端点的边集被称为图的一组匹配

最大匹配:边数最多的匹配

最大匹配

匈牙利算法

随机一篇博客糊一下

网络流

将二分图左右两部分别连接源点汇点,每条边的容量设为 1,计算源点到汇点的最大流即可

最大匹配模型

二分图匹配的模型两个要素:

  1. 结点能够分成独立的两个集合,每个集合内没有连接的边
  2. 待求解的问题中每个结点只能与 1 条匹配边相连

最小点覆盖

最小点覆盖:大小最小的一个点集,让每条边都至少和其中一个点连接;

二分图的最小点覆盖=最大匹配数

略证:金海峰的博客

最小边覆盖

二分图的最小边覆盖:用尽量少的边覆盖二分图的所有顶点

二分图最小边覆盖 = 顶点数-最小点覆盖

最大独立集

最大独立集:在 N 个点的图 G 中选出 m 个点,使这 m 个点两两之间没有边的点中,m 的最大值。

二分图的最大独立集 = 顶点数-最小顶点覆盖


  转载请注明: Sshwy's Blog 二分图漫谈

 上一篇
网络流入门之最大流 网络流入门之最大流
摘要 网络流是强有力的图论算法之一,其算法本身不难,但是所解决的问题却千变万化。简而言之,网络流的难点在于建模。本文则注重讲解网络流的最大流算法。 2019.6.14:收编精选文章。 网络网络是指一个有向图 . 每条边
2018.12.21
下一篇 
组合数漫谈 组合数漫谈
排列与组合在考虑一类计数问题的过程中,我们常常会遇到讨论排列或者组合的问题。 排列数从 n 个不同元素中,任取 m 个元素按照一定的顺序排成一列,叫做从 n 个不同元素中取出 m 个元素的一个排列;从 n 个不同元素中取出 m 个元素的所有
2018.12.21
  目录