图论-二分图相关

定义 二分图又称作二部图,是图论中的一种特殊模型。 设$G=(V,E)$是一个无向图,如果顶点$V$可分割为两个互不相交的子集$(U,V)$,并且图中的每条边$(i,j)$所关联的两个顶点$i$和$j$分别属于这两个不同的顶点集,则称图$G$为一个二分图。 一个无向图为二分图的充要条件是没有奇环。 二分图染色 求解算法 思路 判定一个图是否为二分图,使用dfs进行黑白染色,判定能否满足每条边的两个顶点异色。 实现 二分图最大匹配 定义 又称最大边独立集,即边数最多的匹配。 有关概念 匹配:又称边独立集,一个边集,满足边集中的任两边不邻接。 极大匹配:又称极大边独立集,本身是匹配,加入任何边就不是。 增广路:连接两个未匹配结点的路径,且已匹配边和未匹配边在路径上交替出现,可以发现非匹配边的数量比匹配边的数量多$1$,故将路径上的每一条边取反就能使匹配边的数量$+1$。 求解算法 匈牙利算法 思路 在图中找出增广路; 对增广路上每一条边取反(即匹配边改为非匹配边,非匹配边改为匹配边); 重复以上两步直到找不到增广路为止。 样例推导 给出二分图: 从$X1$开始,找到增广路$X1-Y1$,标

Continue reading