匹配与最大匹配.

推论 3.2.1（ k − 1）边连通偶数阶 k 正则图有完美匹配
证明：设 G 是命题中所述的 k 正则图。
当 k = 1 时，结论显然。 以下假定 k ≥ 2 。设 S 是 G 的任一个非空顶点集， G1, G2 ,L, Gn 是 G \ S 的奇分支。令
ν i = V (Gi ), mi =| {e | e 是 Gi 与 S 之间的连边} | 。
并设 M1 在 C 的 ywL z 段中的边集为 M1′ ， M 2 在 C 的 ywL z 段中的边集为 M 2′ ，于是 M1′ U {yz} U (M 2 \ M 2′ )
是 G* 的完美匹配，又与 G* 的选择矛盾。
综合(1)、(2)两种情形，便证明了 G* \ U 的每个连通分支都是完全图。证毕。
A = {v |u 到 v 有 M * 交错路}。
由于 M * 是最大匹配，故由 Berge 定理， u 是 A 中唯一的 M * 非饱和点。令 S = AI X ，T = AIY 。
uS
X
M*的边
T Y
注意 S − {u} 中的顶点在 M * 下与T 中的顶点一一配对（因 u ∈ S ，且对 ∀t ∈ T ，u 与 t 有 M * 交错路 Pt 相连，而且 t 是 M * 饱和的，故交错路 Pt 上最后一条边必是 M * 的边，它将 S 中一个 顶点与 t 配对。而且不同的 t 会有 S 中不同的顶点相配，否则会有两条 M * 的边关联到 S 中同一
由（*）式， O(G* \ U ) ≤ U ，即 G* − U 的奇分支个数最多是 U 。但这样一来， G* 就
有一个完美匹配：
G* \ U 的各奇分支中的一个顶点和U 的一个顶点配对；U 中余下的顶点以及 G* \ U 的各
分支中余下的顶点在本分支内配对（由于各分支及 U 都是完全图）。
G*\U 的奇分支
由(1)、(2)知： N (S) = T = S − 1 < S ，这与定理条件矛盾。证毕。
推论 3.3.1 设 G = ( X ,Y ) 是二部图，若 X 中每个顶点至少关联 k 条边（ k ≥ 1) 而 Y 中每个顶 点至多关联 k 条边，则 G 中存在饱和 X 的匹配。 证明：由条件知，对 ∀S ⊆ X ，S 至少关联 k | S | 条边。这 k | S | 条边至少关联Y 中 | S |个顶点。 即 N (S) ≥ S ，由 Hall 定理， G 有饱和 X 的匹配。证毕。
u1 G1
奇分支
u2
… un
G2
Gn
偶分支
…
v1 v2 … vn … S
充分性（反证法）：设 G 满足：对 ∀S ⊂ V (G) ， O(G \ S ) ≤ S ，但 G 没有完美匹配。首先， 取 S = φ ，知 O(G) = 0 ，故V (G) 是偶数。现在，给 G 添加边以获得一个没有完美匹配而有尽 可能多的边的图 G* 。因 G 是 G* 的生成子图，故对 ∀S ⊂ V (G) ，G \ S 是 G* \ S 的生成子图，
显然,完美匹配必是最大匹配。
定义3.1.3 设 M 是 G 的一个匹配, G 的 M 交错路是指其边 M 和 E(G) \ M 中交替出现的 路。如果 G 的一条 M 交错路(alternating path)的起点和终点都是 M 非饱和的,则称其为一条 M 可扩展路或 M 增广路(augmenting path)。 定理 3.1.1(Berge,1957) 图 G 的匹配 M 是最大匹配的充要条件是G中不存在 M 可扩展路。 证明:必要性:设 M 是 G 的一个最大匹配。如果 G 中存在一个 M 可扩展路 P,则将 P 上所有不 属于 M 的边构成集合 M ′ 。显然 M ′ 也是 G 的一个匹配且比 M 多一条边。这与 M 是最大匹配
相矛盾。
充分性:设 G 中不存在 M 可扩展路。若匹配 M 不是最大匹配,则存在另一匹配 M ′ ,使 | M ′ |>| M |. 令
H = G[M ⊕ M ′] ，( M ⊕ M ห้องสมุดไป่ตู้ = M U M ′ − M I M ′ 称为对称差)。 则 H 中每个顶点的度非1即2(这是因为一个顶点最多只与 M 的一条边及 M ′ 的一条边相关 联)。故 H 的每个连通分支要么是 M 的边与 M ′ 的边交替出现的一个偶长度圈，要么是 M 的 边与 M ′ 的边交替出现的一条路。由于| M ′ |>| M |，H 的边中 M ′ 的边多于 M 的边，故必有 H 的某个连通分支是一条路，且始于 M ′ 的边又终止于 M ′ 的边。这条路是一条 M 可扩展路。这
证明：必要性。设 G 有饱和 X 的匹配 M ，则对 ∀S ⊆ X ，因 S 的顶点在 M 下和 N (S) 中 顶点配对，故 N (S) ≥ S 。
5
充分性：设 G = ( X ,Y ) 是二部图，且对 ∀S ⊆ X ， N (S) ≥ S 。下用反证法。
假如 G 没有饱和 X 的匹配，则 G 的最大匹配 M * 不能饱和 X 的所有顶点。设 u 是 X 的一 个 M * 不饱和点，并设
…
G*\U 的偶分支
…
… U
2
这与 G* 无完美匹配矛盾。证毕. 命题Ａ的证明：当U ≠ V (G* ) 时， G* \ U 的每个连通分支都是完全图。
用反证法证明：若不然，设 G* \ U 中某个连通分支 Gi 不是完全图，则 V (Gi ) ≥ 3 。必存在 x, y, z ∈V (Gi ) ，使得 xy, yz ∈ E(Gi ) ，且 xz ∉ E(Gi ) 。由于 y ∉U （故必有与 y 不相邻的顶 点），故必存在 w ∈V (G* \ U ), 使得 yw ∉ E(G* ) 。
从而
O(G* \ S) ≤ O(G \ S) ≤ S . （*）
令
U = {u u ∈V (G* ), dG* (u) = ν − 1} .
若 U = V (G* ) ，则 G* 是偶数阶完全图，有完美匹配。这与 G* 的性质矛盾。因此，
U ≠ V (G* ) ，可以证明，此时 G* \ U 的每个连通分支都是完全图（此记为命题Ａ，另证）。
与条件矛盾。 证毕。
1
§3.2 完美匹配
定义 3.2.1 图 G 的奇分支：G 的含有奇数个顶点的连通分支。用 O(G) 表示 G 的奇分支的个数。
定理 3.2.1 (Tutte,1947) 图 G 有完美匹配的充分必要条件是对 ∀S ⊂ V (G) ， O(G \ S) ≤| S | 。
证明（Lovász,1973）必要性：设图 G 有完美匹配 M。对 ∀S ⊂ V (G) ，若 G \ S 无奇分支，则 O(G \ S) = 0 ；否则，设 G1, G2 ,L, Gn 是 G \ S 的所有奇分支。注意每个 Gi 中至少有一个顶 点 ui 在 M 下与 S 中的某个顶点 vi 配对（ i = 1,2,L, n ），（因 Gi 是奇分支， M 是完美匹配）。 故 O(G \ S) = n =| {v1, v2 ,L, vn} |≤ S 。
完美匹配。
证毕
注：有割边的３正则图未必有完美匹配，例如：
v
G
因 O(G − v) = 3, 故无完美匹配。
推论 3.2.3 偶数阶完全图 K 2n 有 2n − 1个边不重的完美匹配。 证明 1：当 n = 1时，结论显然。下设 n ≥ 2 。
4
令V (K2n ) = {v1, v2 , L, v2n }，对每个 i = 1,2,L,2n −1 ，构作一个匹配:
现的偶长度圈。下分两种情形：
(1) xz 和 yw 分别在 H 的不同分支中。设 yw 在 H 的某个圈 C 上，则 M1 在 C 上的边连同 M 2 不在 C 上的边构成 G* 的一个完美匹配。这与 G* 的选择矛盾。
Cy w
x
z
w y
C
M1 的边 M2 的边
x
z
情形（1）
情形（2）
(2) xz 和 yw 在 H 的同一分支Ｃ中，由 x 和 z 的对称性，不妨设 x, y, w, z 在 C 中依次出现，
4． 两人在图 G 上做游戏：交替选择相异的顶点 v0 , v1, v2 ,L ，使得对每个 i > 0, vi 相邻于 vi−1 ，
选择最后一个顶点者获胜。证明：第一个选点人有一个得胜策略当且仅当图 G 没有完美匹 配。
§3.3 二部图的匹配
定理 3.3.1 (Hall, 1935) 设 G 是具有二划分 ( X ,Y ) 的二部图，则 G 有饱和 X 的匹配当且仅当 对 ∀S ⊆ X ， N (S) ≥ S ，其中 N (S) 表示 S 的所有邻点之集。
例：
v1
v1
v1
v5 v4
v2 v5 v6
v3
v4
v2
v5
v6
v3
v4
v2 v6
v3
习题五
1． 证明：若图 G 是连通简单图但不是完全图，则 G 中存在三个顶点 u、v 和 w，使得
uv, vw ∈ E(G) ,而 uw ∉ E(G) 。
2． 证明：一棵树最多只有一个完美匹配。
3． 证明树 G 有完美匹配当且仅当对 ∀v ∈V (G) 都有 O(G − v) = 1。
顶点）。因此
T = S −1。
(1)
此外，N (S) ⊇ T（因T 中顶点通过 S 中顶点与 u 连 M * 交错路），且 N (S) ⊆ T（对 N (S) 中每个顶点 t ,设它是 S 中顶点 s 的邻点,从 u 到 s 的 M * 交错路必可延伸为 u 到 t 的 M * 交错
路）。故
N (S) = T (2)
v∈V (Gi )
v∈V (Gi )
2ε (Gi ) = kν i − mi = kν i − (k − 1) = k(ν i − 1) + 1 。
但 因 ν i − 1 是 偶 数 （ 每 个 Gi 是 奇 分 支 ）， 上 式 两 端 不 可 能 相 等 。 这 个 矛 盾 说 明 mi ≥ k （ i = 1,2,L, n) ，于是
{ } M i = {viv2n }U vi− jvi+ j j = 1,2,L, n − 1 ,
其中 i − j 和 i + j 都是 mod(2n − 1) 的，易检验每个 M i 都是 G 的完美匹配，且不同的 M i 无公
共边。
v1 v8
v2 v3
v7 v6
v4 v5
证明 2：用平面上正 2n − 1边形的点代表 v1, v2 ,L, v2n−1 ，而用其中心点代表 v2n 点。用直线段 连接每个顶点，即得 K 2n ， M i 的边为 vi v2n 和所有与 vi v2n 垂直的边。
y
w
x
z…
Gi
U
由于 G* 是不含完美匹配的极大图，所以 G* + xz 和 G* + yw 都含有完美匹配，分别设为 M 1 和
M 2 。用 H 表示 G* U {xz, yw}中由 M1 ⊕ M 2 导出的子图。由于对 ∀u ∈V (H ) ，d H (u) = 2 或
0（由 M 1 和 M 2 都是完美匹配知），故 H 的每个非平凡连通分支都是其边在 M 1 和 M 2 中交替出
n
∑ mi ≥ kn ,（**）
i =1
故有
≤ ∑ ∑ = O(G − S)
=
1 n
k (**)
⋅
n i =1
mi
≤
1 k u∈S dG (u) (*)
S
由 Tutte 定理， G 有完美匹配。证毕。
推论 3.2.2 (Peterson, 1891) ２－边连通（无割边）的３正则图有完美匹配。
∑ 证明：设 G 是２边连通的３正则图。因 2ε = d (v) = 3ν ，故ν 为偶数。由推论 3.2.1，G 有 v∈V (G )
第三章 匹配理论
§3.1 匹配与最大匹配
定义3.1.1 设 G 是一个图, M ⊆ E(G) ,满足:对 ∀ ei , e j ∈ M , ei 与 e j 在 G 中不相邻,则称 M 是 G 的一个匹配。对匹配 M 中每条边 e = uv ,其两端点u和v称为被匹配 M 所匹配,而u和v 都称为是 M 饱和的(saturated vertex)。 注:每个顶点要么未被 M 饱和,要么仅被 M 中一条边饱和。 定义3.1.2 设 M 是 G 的一个匹配,若 G 中无匹配 M ′ ,使得 | M ′ |>| M | ,则称 M 是 G 的一个 最大匹配；如果 G 中每个点都是 M 饱和的,则称 M 是 G 的完美匹配(Perfect matching).
3
由于κ ′ ≥ k − 1 ，故 mi ≥ k −1, (i = 1,2,L, m) 。
G\S 的奇分支
G1
G2 …
Gn
G\S 的偶分支
…
S
若存在 i ，使得 mi = k − 1 ，则因
∑ ∑ dG (v) = kν i ， dG (v) = k S ，（*）
v∈V (Gi )
v∈S
∑ ∑ 从而 mi = dG (v) − dGi (v) = kν i − 2ε (Gi ) 。因此，