写在前面

二分图又称偶图,双图。是离散数学中一个非常重要的模型。
值得注意的是偶图和对偶图其实完全不是一个东西。
在离散数学中习惯称呼其为偶图 在本文中 笔者将沿用OI的称呼称其为二分图

1.二分图的特点

我们可以将一个图的点分为两个点集 使得这两个点集内部不存在边
这样这个图就是一个二分图

2.二分图的判定

我们先给出判定方法:
一个图$G$为二分图的充要条件是 $G$中包含的每一个环的长度均为偶数(显然在此我们认为环的长度为$0$也是偶数)
证明如下:
(1)必要性
这个挺显然的 我们取一个环 那么为保证其二分图的特性 每条边一定是跨过点集的 那么要想从一侧回到这一侧 显然需要跨过偶数次点集 这个环的长度就显然是偶数
(2)充分性
题设变为给定一个无向图$G$ $G$满足其中每个环的长度都是偶数并且联通 我们来证明这是一个二分图
证明这个图是二分图 显然我们需要给出一种满足定义的点的划分 看我接下来的划分:我们任取一个点$v$ 规定点集$V_1$满足其中所有点到点$v$的距离都是奇数 点集$V_2$中每个点到点$v$的距离都是偶数
那么下证两个点集内部不存在边
取出某个集合中的点$v_1$,$v_2$
由这两个点到点$v$的距离的奇偶性相同知 任何一个点到点$v$的最短路径上都不经过另外一个点
假设存在$e(v_1,v_2)$这样一条边 此时一定存在$v_1 -> v -> v_2 -> v_1$这样一个环 前两部分长度奇偶性相同 加在一起为偶数 最后又$+1$ 此时环的长度为奇数 不合题意
证明完毕

3.完全偶图

定义

完全偶图指的是对于一个偶图的两个点集$V_1$,$V_2$满足$V_1$的任意一个点都和$V_2$中的任意一个点有连边

完全偶图的性质

总顶点数$p$是奇数的时候 完全偶图$K _ {(p-1)/2,(p+1)/2}$
总顶点树$p$是偶数的时候 完全偶图$K _ {p/2,p/2}$
图中的边数是$p^2/4$条
根据完全偶图的特性我们引入图兰定理

图兰定理

图兰定理:如果一个图中没有三角形 那么边数最多是$p^2/4$条

4.二分图的匹配

4.1 概念

设$G=<V, E>$是二分图,而且$E$是$V1$和$V2$的笛卡尔乘积子集。若$M$包含于$E$,而且$M$中任何两条边不相邻,则称$M$是$G$的一个匹配;具有边数量最多的匹配称为最大匹配;若$|V1|=|V2|=|M|$,则称$M$为完美匹配。匹配$M$中的边$e$称为杆。
这个概念有点谜语人那味 我来简单翻译一下
就是两侧顶点一一配对能配成的方案 就是匹配
匹配最多对就是最大匹配 全都匹配上了就是完全匹配
显然我们发现完美匹配一定是最大匹配 反之不然
此外我们还发现 一个二分图的匹配不一定是唯一的 最大匹配也不一定是唯一的 完美匹配还不一定是唯一的
此外 每个二分图都存在最大匹配 但并非每个二分图都有完美匹配

4.2 一些概念

关于匹配问题还有以下四个重要的定义:
设$M$是一个匹配,则:
1.$V_1$中的结点$u$和$V_2$中的结点$v$称被$M$所匹配,当且仅当有杆$e$属于$M$,使得$e=(u, v)$
2.结点$u$被称为$M$的饱和点当且仅当有杆$e$属于$M$匹配结点$u$;否则结点$u$称为$M$的非饱和点
3.交错路$P$是一条分别交替的属于$M$和$E\M$的边构成的极大的初级路(或圈);
4.增广路$P$是一条起点为$u$以及终点为$v$且都是非饱和点的交错路。
这边为交错路和增广路这两个概念划重点 接下来将基于这个概念给出一种常见的二分图匹配算法

4.3 Hall定理

我们不加证明地给出这个定理
设二分图的两部分为$X$、$Y$,且$|X|≤|Y|$。则定理描述为:二分图存在完美匹配,等价于对于$X$的任意子集$X′$,与它们中任意点相连的$Y$的结点个数$≥|X′|$。
Hall定理常用与判断是否有解 尤其常见于OI与ACM中网络流复杂度不支持的时候进行拆点和拆边之后变成二分图匹配

4.4 最大流方法进行二分图匹配

博客顶端搜索框搜索dinic算法即可 这里不过多进行赘述

4.5 匈牙利算法进行二分图匹配

匈牙利算法的局限性在于只能进行无权值的二分图匹配问题
匈牙利算法思想:通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时,达到最大匹配(增广路定理)。
算法原理:考虑一条增广路的构成 根据定义一定是有奇数条边的 并且是$M$以外的边比$M$中的边多一条 这样我们用前者取代后者就可以得到更大匹配
至于算法流程举例 网上太多了 我还懒得做图 加之这篇文章的终点并不在此 所以嘛嘻嘻嘻

4.6 KM算法进行带权二分图匹配

这个就可以抵消掉匈牙利算法的缺点 并且该算法是本篇文章的重点
先说句题外话(跑)

介绍一下 她叫阿迟 是Michael_Bryant找的画师设计的形象
好了进入正题
一个例题
阿迟的手下有三员干将 并且阿迟有三份工作需要完成
每员干将不是都能完成每份工作 并且他们对于每份工作的效率也不相同
现在阿迟想要找到效率最高的一种工作分配
Michael_Bryant接下来帮她完成这个问题
具体地 我们根据上述模型给出如下的具体问题:三个员工对应三份工作

KM算法的流程如下
1.首先对每个顶点赋值,将左边的顶点赋值为最大权重,右边的顶点赋值为$0$。
如图,我们将顶点$A$赋值为其两边中较大的$4$。

2.进行匹配,我们匹配的原则是:只与权重相同的边匹配,若是找不到边匹配,对此条路径的所有左边顶点$-1$,右边顶点$+1$,再进行匹配,若还是匹配不到,重复$+1$和$-1$操作。(这里看不懂可以跳过,直接看下面的操作,之后再回头来看这里。)
对$A$进行匹配,符合匹配条件的边只有$Ac$边。
匹配成功!

接下来我们对$B$进行匹配,顶点$B$值为$3$,$Bc$边权重为$3$,匹配成~ 等等,$A$已经匹配$c$了,发生了冲突,怎么办?我们这时候第一时间应该想到的是,让$B$换个工作,但根据匹配原则,只有$Bc$边 $3+0=0$ 满足要求,于是$B$不能换边了,那$A$能不能换边呢?对$A$来说,也是只有$Ac$边满足$4+0=4$的要求,于是$A$也不能换边,走投无路了,怎么办?

从常识的角度思考:其实我们寻找最优匹配的过程,也就是帮每个员工找到他们工作效率最高的工作,但是,有些工作会冲突,比如现在,$B$员工和$A$员工工作$c$的效率都是最高,这时我们应该让$A$或者$B$换一份工作,但是这时候换工作的话我们只能换到降低总体效率值的工作,也就是说,如果令$R=$左边顶点所有值相加,若发生了冲突,则最终工作效率一定小于$R$,但是,我们现在只要求最优匹配,所以,如果$A$换一份工作降低的工作效率比较少的话,我们是能接受的(对$B$同样如此)。
在KM算法中如何体现呢?
现在参与到这个冲突的顶点是$A$,$B$和$c$,令所有左边顶点值$-1$,右边顶点值$+1$,即 $A-1$,$B-1$, $c+1$,结果如下图所示。

我们进行了上述操作后会发现,若是左边有$n$个顶点参与运算,则右边就有$n-1$个顶点参与运算,整体效率值下降了$1*(n-(n-1))=1$,而对于$A$来说,$Ac$本来为可匹配的边,现在仍为可匹配边$(3+1=4)$,对于$B$来说,$Bc$本来为可匹配的边,现在仍为可匹配的边$(2+1=3)$,我们通过上述操作,为$A$增加了一条可匹配的边$Aa$,为$B$增加了一条可匹配的边$Ba$。
现在我们再来匹配,对$B$来说,$Ba$边 $2+0=2$,满足条件,所以$B$换边,$a$现在为未匹配状态,$Ba$匹配!

此时$C$无法匹配 所以$C-1$后可以匹配$Cc$
到下一次出现矛盾的几个点分别是$A$,$B$,$C$,$a$,$c$
处理方式同上 得到下图

完成了KM匹配
虽然不停换人的过程听起来很麻烦,但其实整个是个递归的过程,实现起来比较简单。比较复杂的部分就是期望值的改变,但是可以在递归匹配的过程中顺带求出来。
例题:HDU2255
以上