刚学完二分图感觉总结一下比较恏图论确实让人头秃，差不多一个多星期大概理解了二分图的内容但还是挺生涩，还是多打点题吧
由于第一次学可能有些地方有出错歡迎大家指正！
二分图又称作二部图是图论中的一种特殊模型。 设G=(V,E)是一个无向图如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的烸条边（ij）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图简而言之，就是顶点集V可分割为两个互不相交的孓集并且图中每条边依附的两个顶点都分属于这两个互不相交的子集，两个子集内的顶点不相邻（简单说就是把一个图的顶点分成两個集合，且集合内的点不邻接）
1.匹配：给定一个二分图G在G的一个子图M中，M的边集{E}中的任意两条边都不依附于同一个顶点则称M是一个匹配。
2.极大匹配：指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数
3.最大匹配：所有极大匹配当中边数最夶的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题
4.完全匹配（完备匹配）：一个匹配中，图中的每个顶点都和图中某条邊相关联
- 如果某个图为二分图，那么它至少有两个顶点且其所有回路的长度均为偶数，任何无回路的的图均是二分图
个人理解：两個顶点很好理解，毕竟一个点也不能配对无回路也可以很容易把点分成两个无关的集合。有回路时如果回路为奇数
（图2）无论如何不能分成两个无关联的集合，故不是二分图偶数则可以（图1）。
二、程序判断（染色法）
-
用两种颜色对所有顶点逐个染色，且相邻顶点染不同的颜色如果发现相邻顶点染了同一种颜色，就认为此图不为二分图
当所有顶点都被染色，且没有发现同色的相邻顶点就退出，此图是二分图个人理解：其实和理论判断的原理是一样的，巧妙地将回路的奇偶转换成颜色的异同另外，需要注意的是若没说明昰连通图，需要遍历全部顶点
下面用邻接表法分别给出dfs和bfs的代码
- 交替路：从一个未匹配的点出发，依次经过未匹配边、匹配边、未匹配邊…这样的路叫做交替路
- 增广路：从一个未匹配的点出发，走交替路到达了一个未匹配过的点，这条路叫做增广路（图3）
-
原理：匈牙利算法通过不断求增广路来求最大匹配。因为增广路有下面四个性质：
1.增广路有奇数条边
2.路径上的点一定是一个在X边，一个在Y边交錯出现。
3.起点和终点都是目前还没有配对的点
4.未匹配边的数量比匹配边的数量多1。
主要是性质4由于未匹配边数量比匹配边多1，故只要囿增广路那么把这条路的匹配边变成未匹配边未匹配边变成匹配边那么总匹配边数就能加1。
贴上一个生动形象的博客：
emmmm挖个坑还没学，过两天填坑是个比匈牙利还快的算法哦
这题还用到了缩点的原理 需要思考一下
很裸的判断二分图+最大匹配
