图论讲义3匹配.pdfVIP

第三章 匹配理论 §3.1 匹配与最大匹配 定义3.1.1 设 G 是一个图, M ⊆E (G) ,满足:对∀e ,e ∈M ,e 与e 在 G 中不相邻,则称 i j i j 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.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 UM −M IM 称为对称差)。 则 H 中每个顶点的度非1即2(这是因为一个顶点最多只与M 的一条边及M ′的一条边相关 联)。故H 的每个连通分支要么是M 的边与M ′的边交替出现的一个偶长度圈，要么是M 的 边与M ′的边交替出现的一条路。由于| M ′|| M | ，H 的边中M ′的边多于M 的边，故必有H 的某个连通分支是一条路，且始于M ′的边又终止于M ′的边。这条路是一条M 可扩展路。这 与条件矛盾。 证毕。 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 ；否则，设G , G , L, G 是 G \ S 的所有奇分支。注意每个G 中至少有一个顶 1 2 n i 点u 在M 下与S 中的某个顶点v 配对（i 1,2, L, n ），（因G 是奇分支，M 是完美匹配）。 i i i 故O(G \ S ) n | {v , v , L, v } |≤ S 。 1 2 n