# 偶图 (bipartite graph 或 paar graph)

设 G=(V,E) 是简单无向图。若存在着结点集 V 的一个划分$\{V_1,V_2\}(v=v_1\cup V_2,V_1\cap V_2=\varnothing)$, 使得边集$E\in V_1\times V_2$ ，则称 G 是偶图 (或二分图、二部图)。
偶图一般记为$G=(V_1,V_2,E)(或G=(V_1,E,V_2))$。
同时称 V1，V2 是 V 的互补结点子集。
当$E=V_1\times V_2$ 时，称 G 是完全二分图。这时，若$|V_1|=m，|V_2|=n$，则记完全二分图为K_

# 定理 1

设$G=(V,E)$ 是简单无向图。那么
G 是偶图$\iff$G 中每个圈都是偶圈 (长度为偶数的圈)
$\iff$G 中不含奇圈 (长度为奇数的圈) 。

# 推论 1

设$G=(V,E)$ 是简单无向图。那么 G 是偶图
$\iff$ G 的顶点可用两种颜色来着色 (即 G 的顶点色数是 2)
$\iff$ G 的顶点可用 A、B 两个字母来标号 。

所谓一个图的着色，分以下三种情况：

1. 将图的顶点染以颜色，使相邻顶点的颜色不同；
2. 将图的边染以颜色，使相邻边的颜色不同；
3. 将平面图的面染以颜色，使相邻面的颜色不同；

• 所谓图的色数，是在第 (1) 种着色情况下，所用的最少颜色；而在第 (2) 种着色情况下，
  所用的最少颜色，称为图的着色指数。

# 推论 2

设$G=(V_1,V_2,E)$ 是偶图。那么

1. 偶图 G 含有 H - 圈 (G 是 H - 图)
   $\implies$|V1|=|V2|
   $\implies$ 红、蓝着色结点的数目相同
   $\implies$A、B 标号结点的数目相同；
2. 偶图 G 有 H - 路$\implies | |V1|-|V2||\leqslant1$
   $\implies$ 红、蓝着色结点的数目至多差 1
   $\implies$A、B 标号结点的数目至多差 1。

有些图 G 虽然不是偶图，但 可通过给图 G 的某个结点的某条边上增加一个结点而获得另一图 >$G'$，使得：

1. 图 G$G'$ 是偶图 (能完成标号法)；
2. 图 G 有 H - 圈 (是 H - 图)$\iff$ 图 G$\iff$ 有 H - 圈 (是 H - 图) ；
   而图$G'$ 能用标号法判定不含 H - 圈 (不是 H - 图) ，因此， 可得图 G 一定不含 H - 圈 (不是 H - 图)

# 匹配 最大匹配 完美匹配

设$G＝(V1,V2,E)$ 是偶图，这里：$V=V_1\cup V_2，V_1\cap V_2=\varnothing,E\subseteq V_1\times V_2$ 。若存在着边集$E_1\subseteq E且E_1\ne \varnothing$ 使得：

1. 若$E_1$ 中任何两边都不相邻，则称 E1 是图 G 的一个匹配 (Matching)；
2. 若$E_1$ 是一个具有最多边数的匹配，则称 E1 是图 G 的一个最大匹配 (Maximum
   matching)；
3. 若$E_1$ 是一个满足条件$|E1|＝|V1|\leqslant |V2|$ 的匹配，则称$E_1$ 是图 G 的一个从$V_1$ 到$V_2$ 的最大匹配 (Maximum matching from $V_1$ to $V_2$)；
4. 若 E1 是一个满足条件$|E1|＝|V1|=|V2|$ 的匹配，则称 $E_1$ 是图 G 的一个完美匹配 (Perfect matching)

• 匹配又称为对集 (并列集、径集)，通常将匹配$E_1$ 记为 M；
• 匹配 M 中的边$e\in M$ 称为杆 (bar)；
• 完美匹配又称为 1 - 因子 (1-factor)；
• 完美匹配一定是最大匹配；
• 最大匹配不一定是完美匹配；
• $(|M|=|V1|\leqslant|V2|)\land (|M|=|V2|\leqslant|V1|)\implies M$ 一定是最大匹配；
• M 是最大匹配$\implies (|M|=|V1|\leqslant|V2|)\land (|M|=|V2|\leqslant|V1|)$
• $|V1|\ne |V2|\implies$ 图 G 一定没有完美匹配。

# 定理 2.(P.Hall 定理 (1934))

设$G=(V_1,V_2,E)$ 是偶图。这里：$|V1|\leqslant|V2|$。则存在着图 G 的一个从$V_1$ 到$V_2$ 的最大匹配 M
$\iff(\forall S)(S\subseteq V_1\implies |N(S)|\geqslant |S|)$ (相异性条件)
其中： $\displaystyle N(S)＝\bigcup_{v\in S}N(v)$ 称为结点集$S\in V_1$ 的邻域；
$N(v)=\{v'|v'\in V_2\land (v, v')\in E\}$ 称为结点$v\in V_1$ 的邻域；

Hall 定理中条件 (*) 的等价的、通俗易懂的叙述是：图 G 中有从$V_1$ 到$V_2$ 的最大匹配的充分必要条件是：$V_1$ 中的任何$k (0\leqslant k\leqslant |V1|)$ 个结点，一定至少连接着$V_2$ 中的 k 个结点。

# 定理 3.(Philip.Hall 一般婚姻定理 (1934))

设$G=(V1,V2,E)$ 是偶图。这里： $|V_1|=|V_2|$ 。则存在着图 G 的一个完美匹配:

$$M\iff(\forall S)(S\subseteq V_1\implies |N(S)|\geqslant |S|)$$

# 推论 1

完全二分图$K_{m,n}$ 一定有一个最大匹配 M，且$|M|=min\{m,n\}$ ；并且当 m=n 时， M 为一完美匹配。

# 推论 2 婚姻定理

k - 正则偶图 (每个结点的度都是 k 的偶图) 一定有一个完美匹配 M。

# 推论 3

设$G =(V1,V2,E$) 是偶图。若$\exists e\in k)(k\in N\land k\geq 1)$, 使得:

1. $(\forall v)(v\in V_1\implies deg(v)\geq k)$；
2. $(\forall v)(v\in V_2\implies deg(v)\leq k)$；

则图 G 中一定存在着一个从 V1 到 V2 的最大匹配 M

# 匈牙利方法 (Hungarian method)

# 定义 3. 匹配 饱和点 非饱和点 交错路 增广路

设$G =(V1,V2,E$) 是偶图。M 是图 G 的一个匹配。

1. 称结点$u\in V_1\cup V_2$ 被 M 所匹配$\iff$ 存在着匹配 M 的某条杆 $e\in M$，以 u 为其一个端点 (这时称结点 u 覆盖 (Covering) M 的杆 e) ；
2. 称结点 $u\in V_1\cup V_2$ 是 M 的饱和点 (saturated node) $\iff$ u 被 M 所匹配；否则，称结点$u\in V_1\cup V_2$ 是 M 的非饱和点 (unsaturated node) ；
3. 交错路 (alternating path) 是一条分别交替的由 M 中的边和 E\M 中的边构成的极大的初级路；
4. 增广路 (augmenting path) 是一条两个端点都是非饱和点的交错路

# 求最大匹配 M 的算法 (匈牙利方法－J.Edmonds (1965))：

1. 任取一匹配 M (可以空或只取一边)；
2. 取$S:=\{u|u\in V_1\land u$ 是 M 的非饱和点$\}$；若$S=\varnothing$ 则 M 已是最大匹配；exit ；
3. 任取一结点$u_0\in S$，从 u0 走出几条交错路： $P_{i1}, P_{i2},..., P_{i3}$ ；
4. 如果这些路中有某一条是增广路，不妨记为 P，则令$M:=M\oplus P=(M\setminus P)\cup (P\setminus M)$ (并且 | M|(新)=|M|(旧)+1) ； go to No2 ；
5. 如果这些路中无一条是增广路，则令$S:=S\setminus\{u_0\}$；如果$S\ne \varnothing$ 则 go to No3 ；否则$S=\varnothing$ 则 M 已是最大匹配；exit ；