什么是二分图？
简单来说，就是把一个图的顶点划分为两个不相交子集 ，使得每一条边都分别连接两个集合中的顶点。如果存在这样的划分，则此图为一个二分图。
这样如果不理解，可以看个例子：
此图即为一个二分图，将蓝色点与红色点分别划为两个子集。
要点：
· 无向图
· 所有点分成 A、B 两个不相交的集合
· 两个集合中没有边存在
· 边全部存在于两个集合之间
· 二分图当且仅当图中不含奇数环（必要性）
· 由上条反推，如果不含有奇数环的话一定是二分图（充分性）
二分图的应用
· 染色法判定二分图
· 二分图最大匹配，匈牙利算法
如何判定二分图
在图中任选一顶点 v ，定义其距离标号为 0 ，然后把它的邻接点的距离标号均设为 1 ，接着把所有标号为 1 的邻接点均标号为 2（如果该点未标号的话）。标号过程可以用一次BFS实现。标号后，所有标号为奇数的点归为 X 部，标号为偶数的点归为 Y 部。
接下来，二分图的判定就是依次检查每条边，看两个端点是否是一个在 X 部，一个在 Y 部。
如果一个图不连通，则在每个连通块中作判定。
由于图中没有奇数环，所以染色过程中一定不会出现矛盾。
二分图匹配
给定一个二分图 G ，在 G 的一个子图 M 中， M 的边集 {E} 中的任意两条边都不交汇于同一个结点，则称 M 是一个匹配。
（明天继续）
标签：二分,标号,两个,奇数,判定,关于,集合 From： https://www.cnblogs.com/marswithme/p/16667402.html