6.1 二部图

本节大多都是概念的引入，我就用我自己的话去记录了。

• 二部图（偶图）：我们将图里的点分为两个集合$V_1$V1​,$V_2$V2​后，每一条边的端点分别属于$V_1$V1​,$V_2$V2​。我们将二部图记做$G$G = <$V_1$V1​,$V_2$V2​,$E$E>。其中$V_1$V1​,$V_2$V2​称为互补顶点子集。
• 当二部图中$V_1$V1​的每一个顶点到$V_2$V2​的每一个顶点均有且仅有一条边相关联，则称其为完全二部图（完全二部图）。当$|V_1| = n$∣V1​∣=n,$|V_2| = m$∣V2​∣=m 时，完全二部图记做 $K_{n,m}$Kn,m​。

判断一个图是否为二部图的方法：
当且仅当图中没有长度为奇数的回路。

eg：

是二部图但不是完全二部图。因为上面的一个点没有与下面的每一个点关联。

• 判断是不是二部图的时候我们把注意力放在边上。
• 判断是不是完全二部图的时候我们把注意力放在点上。

这两个图是同构的，是二部图也是完全二部图。

这个图不是二部图。图里有一个三角形，所以存在长度为3（奇数）的回路。故不是二部图。

---

• 在所有边中取子集$M$M，若边集$M$M中的边两两不相邻，则边集$M$M为图的匹配。
• 若再往$M$M里添一条边就不是匹配了，那么$M$M是图的极大匹配。
• $M$M中边数最多的匹配称为最大匹配。
• 最大匹配中边的条数称为匹配数。
• 若$M$M中的边与点$v_i$vi​关联，则$v_i$vi​为$M$M的饱和点，否则称为非饱和点。
• 若图中每一个点都是饱和点，则称$M$M是完美匹配。（简单来说就是$M$M中的边包含了所有点就是完美匹配）（再简单说就是如果 匹配数 X 2 = 图中点数，那么是完美匹配）

eg：

匹配：{$e_1$e1​}，{$e_1$e1​,$e_7$e7​} 等等
极大匹配：{$e_5$e5​}，{$e_1$e1​,$e_7$e7​}，{$e_2$e2​,$e_6$e6​}，{$e_3$e3​,$e_7$e7​}，{$e_4$e4​,$e_6$e6​}
最大匹配：{$e_1$e1​,$e_7$e7​}，{$e_2$e2​,$e_6$e6​}，{$e_3$e3​,$e_7$e7​}，{$e_4$e4​,$e_6$e6​}
匹配数：2
无完美匹配：因为$M$M中的点必为偶数个，而此图中的点为奇数个。

匹配：{$e_1$e1​}，{$e_7$e7​} 等等
极大匹配：{$e_2$e2​,$e_5$e5​}，{$e_3$e3​,$e_6$e6​}，{$e_1$e1​,$e_7$e7​,$e_4$e4​}，{$e_2$e2​,$e_6$e6​,$e_4$e4​}
最大匹配：{$e_1$e1​,$e_7$e7​,$e_4$e4​}，{$e_2$e2​,$e_6$e6​,$e_4$e4​}
匹配数：3
3 x 2 = 6 == 6，所以是完美匹配

---

在二部图 $G$G = < $V_1$V1​ , $V_2$V2​ , $E$E > 中 ， $|V_1|$∣V1​∣ $\leq$≤ $|V_2|$∣V2​∣ ，$M$M 为 $G$G 中一个最大匹配，若$|M|$∣M∣ = $|V_1|$∣V1​∣ ，则称$M$M 为 $G$G 中 $V_1$V1​ 到 $V_2$V2​的完备匹配。当$|V_1|$∣V1​∣ = $|V_2|$∣V2​∣时，完备匹配是完美匹配。

eg1：

如图：
{$e_1$e1​,$e_2$e2​}为最大匹配，无完备匹配，更无完美匹配。

eg2：

{$e_1$e1​,$e_2$e2​,$e_3$e3​}是此图的最大匹配，其是完备匹配，但是不是完美匹配。

eg3：

{$e_1$e1​,$e_2$e2​,$e_3$e3​}是此图的最大匹配，其是完备匹配也是完美匹配。

Hall 定理：设二部图$G$G = < $V_1$V1​ , $V_2$V2​ , $E$E > 中 ， $|V_1|$∣V1​∣ $\leq$≤ $|V_2|$∣V2​∣ ，$G$G 中存在从$V_1$V1​ 到 $V_2$V2​的完备匹配当且仅当 $V_1$V1​ 中任意 k 个顶点至少邻接 $V_2$V2​ 中的 k 个顶点。

证明的时候有用，先在这里记一下。