图的匹配

定义

1. M 是图 G 的边子集（不含自环），且 M 中的任意两条边没有共同顶点，则称 M 是 G 的一个匹配
2. 如果 G 中顶点 v 是 G 的匹配 M 中某条边的端点，则称它为 M 饱和点，否则称为 M 非饱和点
3. 如果不能通过加边使得匹配 M 增大，称 M 是图 G 的极大匹配
4. 如果 M 是图 G 的包含边数最多的匹配，称 M 是 G 的一个最大匹配
5. 如果最大匹配饱和了 G 的所有顶点，称它为 G 的一个完美匹配

M 交错路，M 增广路

• M 交错路 : M 是图 G 的匹配，G 中一条由 M 中的边和非 M 中的边交错形成的路，称为 G 中的一条 M 交错路
• M 增广路 : 如果 M 交错路的起点与终点是 M 非饱和点 (不被 M 的边集覆盖), 则这种 M 交错路称为 M 增广路

Berge 定理

G 的匹配 M 是最大匹配，当且仅当 G 不包含 M 增广路

二部图匹配的存在性判定定理

Hall 定理： 设 G=(X, Y) 是二部图，则 G 存在饱和 X 每个顶点的匹配的充要条件是：对任意点子集 \(S\inX\), 有 \(|N(S)| \geq |S|\) 也就是从 X 中任意选一堆顶点集合，它在 Y 中的相邻点的个数要大于它本身子集含有的顶点数。

1. k-正则二部图一定存在完美匹配 (k>0)

证明：

点覆盖与匹配

定理

设 M 是 G 的匹配，K 是 G 的点覆盖，若 |M|=|K|, 则 M 是最大匹配，而 K 是最小点覆盖。 证明：

Konig 定理

在二部图中，最大匹配的边数等于最小点覆盖的顶点数

完美匹配的判定

Tutte 定理

图G有完美匹配当且仅当对V(G)的任意子集S, 有 \(o(G-S)\leq |S|\). 其中：

1. o(G−S)表示奇分支数目(奇分支是阶数为奇的连通分支)
2. S是V(G)的任意子集(可以是空集)
3. |S|+o(G−S)与|V(G)|的奇偶性相同.

推论

3正则无桥图存在完美匹配 (桥就是割边) 这个条件只是一个充分条件，也就是说存在完美匹配的 3 正则图，也可以是有桥的，例如：