二分图（菜鸟笔记）

dkdklcx / 2023-08-04 / 原文

1.二分图的有关性质

首先二分图必定不具有奇数环。而不具有奇数环的图必定可以被染成相邻两个点都不是同个颜色的图（只用黑白两色）。
首先证明不具有奇数环的图是图在染色不存在矛盾的充分必要条件。
证明充分性，用反证法。图中无奇数环，但是染色存在矛盾，则有白黑白黑...白这样的染色，但是存在这样的染色则一定存在奇数环。
证明必要性，用反证法。图中染色不存在矛盾，但有奇数环，那么一定有白黑白黑...白的染色发生，矛盾。
再证明二分图必定不具有奇数环。我们知道二分图的点必定可以被划分到两个集合中，且集合中的点两两都没有边。若二分图中有奇数环，则有白黑白黑...白这样的点的集合划分（黑白分别是两个集合），由于最后两个白在同一个集合且他们之间有边，因此矛盾。

关押罪犯

这题用到了染色法判定二分图。

2.二分图的最大匹配

接下来是二分图中用匈牙利算法求二分图的最大匹配。
首先匹配是指匹配好的一对点，最大匹配是指匹配的最大数量，匹配点是匹配中的点。
增广路径是从左边的未匹配点出发，经过非匹配边、匹配边、非匹配边、匹配边......，最后到达未匹配点的路径，我们可以把未匹配边转变为匹配边，把匹配边转变为未匹配边，这样匹配边数量就加一了。
有个结论是二分图中若匹配是最大匹配，那么必定不存在增广路径，不存在增广路径，必定是最大匹配。

棋盘覆盖

这题用到了匈牙利算法求二分图的最大匹配。

3.二分图的相关结论

（1）二分图的最小点覆盖等于二分图的最大匹配。
（2）二分图的最大独立集等于二分图的总点数 - 最小点覆盖。
解释一下：
首先最大独立集是一个图的点的集合，且这个集合中的点两两之间没有边且这个集合的点的数量最大。
那么最大独立集（最大独立集是基于无向图的）的意思就是让我们在所有点中去掉最少的点，使得这个集合成为最大独立集。
在二分图中去掉的这些点其实就是最小点覆盖的点，那么就有最大独立集等于二分图的总点数 - 最小点覆盖。
（3）二分图的最小路径点覆盖等于总点数 - 最大匹配，二分图的最小路径重复点覆盖等于原二分图做传递闭包后的最小路径点覆盖。
解释一下：
最小路径点覆盖是用最少的路径覆盖所有的点，且这些路径都不相交。最小路径重复点覆盖是也是用最少的路径覆盖所有的点，但是点可以重复经过即路径可以相交。
最小路径点覆盖和最小路径重复点覆盖都是基于有向无环图的，但是我们可以使用拆点来将有向无环图变成无向图。即若有n个点，那么我们左边构造1-n个点，叫出点，右边构造1'-n'个点，叫入点，例如当有3连向5时，那么我们就拆成3连向5'。那么对于每条边我们就有一个匹配了，而终点无法连向其他点，所以在左边他是个孤立点。