图论讲义第3章-匹配问题.pdf

1第三章 匹配理论 §3.1 匹配与最大匹配 定义 3.1.1 设 G 是一个图, )(GEM ⊆ ，满足:对ie∀ , Mej∈ ，ie 与je 在 G 中不相邻，则称 M 是 G 的一个匹配对匹配 M 中每条边 uve = ，其两端点 u 和 v 称为被匹配 M 所匹配，而 u和 v 都称为是 M饱和的(saturated vertex) 注: 每个顶点要么未被 M 饱和, 要么仅被 M 中一条边饱和 定义 3.1.2 设 M 是 G 的一个匹配, 若 G 中无匹配 M′, 使得 |||| MM >′ , 则称 M 是 G 的一个最大匹配；如果 G 中每个点都是 M 饱和的, 则称 M 是 G 的完美匹配(Perfect matching). 显然, 完美匹配必是最大匹配 例如，在下图 G1中，边集 {e1}、 {e1,e2}、 {e1,e2,e3}都构成匹配， {e1,e2,e3}是 G1的一个最大匹配在 G2中，边集 {e1,e2,e3,e4}是一个完美匹配，也是一个最大匹配 定义 3.1.3 设 M 是 G 的一个匹配, G 的 M交错路是指其边 M 和 MGE \)( 中交替出现的路。

如果 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′,使|||| MM >′ . 令 ][ MMGH ′⊕= ，( MMMMMM ′−′=′⊕ ∩∪ 称为对称差) 则 H 中每个顶点的度非1即2(这是因为一个顶点最多只与 M 的一条边及 M′的一条边相关联)故 H 的每个连通分支要么是 M 的边与 M′的边交替出现的一个偶长度圈，要么是 M 的边与 M′的边交替出现的一条路 由于 |||| MM >′ ， H 的边中 M′的边多于 M 的边， 故必有 H的某个连通分支是一条路，且始于 M′的边又终止于 M′的边。

这条路是一条 M 可扩展路这与条件矛盾 证毕 G1 G2e1 e2 e3 e2e1e3e4 2§3.2 完美匹配 定义 3.2.1 图 G 的奇分支： G 的含有奇数个顶点的连通分支 用 )(GO 表示 G 的奇分支的个数 定理 3.2.1 (Tutte,1947) 图 G 有完美匹配的充分必要条件是对 )(GVS ⊂∀ ， ||)\( SSGO ≤ 证明 （ Lovász,1973） 必要性 ：设图 G 有完美匹配 M对 )(GVS ⊂∀ ，若 SG \ 无奇分支，则0)\( =SGO ；否则，设kGGG ,,,21null 是 SG \ 的所有奇分支注意每个iG 中至少有一个顶点iu 在 M 下与 S 中的某个顶点iv 配对（ ki ,,2,1 null= ） ， （因iG 是奇分支， M 是完美匹配） 故 SvvvkSGOk≤== |},,,{|)\(21null 充分性 （反证法） ：设 G 满足：对 )(GVS ⊂∀ ， SSGO ≤)\( ，但 G 没有完美匹配首先，取 φ=S ，知 0)( =GO ，故 )(GV 是偶数现在，给 G 添加边以获得一个没有完美匹配而有尽可能多的边的图*G 。

因 G 是*G 的生成子图，故对 )(GVS ⊂∀ ， SG \ 是 SG \*的生成子图，从而 SSGOSGO ≤≤ )\()\(*. （ *） 令 }1)(),({**−=∈= νudGVuuUG. 若 )(*GVU = ，则*G 是偶数阶完全图，有完美匹配这与*G 的性质矛盾因此，)(*GVU ≠ ，可以证明，此时 UG \*的每个连通分支都是完全图（记为命题Ａ，另证） 由（ *）式， UUGO ≤)\(*，即 UG −*的奇分支个数最多是 U 但这样一来，*G 就有一个完美匹配： UG \*的各奇分支中的一个顶点和 U 的一个顶点配对； U 中余下的顶点以及 UG \*的各分支中余下的顶点在本分支内配对（由于各分支及 U 都是完全图） …u1 u2 uk …S…v2vkv1…G1 G2 Gk奇分支 偶分支……UG*\U 的奇分支 G*\U 的偶分支… 3这与*G 无完美匹配矛盾证毕 . 命题Ａ的证明： 在上述充分性证明的条件下，当 )(*GVU ≠ 时， UG \*的每个连通分支都是完全图 用反证法证明：若不然，设 UG \*中某个连通分支iG 不是完全图，则 3)( ≥iGV 。

必存在)(,,iGVzyx ∈ ，使得 )(,iGEyzxy ∈ ，且 )(iGExz∉ 由于 Uy∉ ，故必有与 y 不相邻的顶点，即必存在 ),\(*UGVw∈ 使得 )(*GEyw∉ 由于*G 是不含完美匹配的极大图，所以 xzG +*和 ywG +*都含有完美匹配，分别设为1M 和2M 用 H 表示 { }ywxzG ,*∪ 中由21MM ⊕ 导出的子图由于对 )(HVu∈∀ ， 2)( =udH或0（由1M 和2M 都是完美匹配知） ，故 H 的每个非平凡连通分支都是其边在1M 和2M 中交替出现的偶长度圈下分两种情形： (1) xz 和 yw分别在 H 的不同分支中设 yw在 H 的某个圈 C 上，则1M 在 C 上的边连同2M 不在 C 上的边构成*G 的一个完美匹配这与*G 的选择矛盾 情形（ 1） 情形（ 2） (2) xz 和 yw在 H 的同一分支Ｃ中， 由 x 和 z 的对称性， 不妨设 zwyx ,,, 在 C 中依次出现，并设1M 在 C 的 zywnull 段中的边集为1M′，2M 在 C 的 zywnull 段中的边集为2M′，于是 )\(}{221MMyzM ′′ ∪∪ 是*G 的完美匹配，又与*G 的选择矛盾。

综合 (1)、 (2)两种情形，便证明了 UG \*的每个连通分支都是完全图 推论 3.2.1 ( 1−k )边连通偶数阶 k 正则图有完美匹配 证明：设 G 是命题中所述的 k 正则图 当 1=k 时，结论显然 以下假定 2≥k 设 S 是 G 的任一个非空顶点集，nGGG ,,,21null 是 SG \ 的奇分支令 ),(iiGV=ν eemi|{|= 是iG 与 S 之间的连边 |} wzyx C M1的边 M2的边 wyx zC…UGi x wy z 4由于 1−≥′ kκ ，故 1−≥ kmi, ),,2,1( mi null= 若存在 i ，使得 1−= kmi，则因 iGVvGkvdiν=∑∈ )()( ， SkvdSvG=∑∈)( ， （ *） 从而 )(2)()()()(iiGVvGGVvGiGkvdvdmiiiεν −=−=∑∑∈∈因此， 1)1()1()(2 +−=−−=−=iiiiikkkmkG νννε 但因 1−iν 是偶数（每个iG 是奇分支） ，上式两端不可能相等这个矛盾说明 kmi≥ （ ),,2,1 ni null= ，于是 knmnii≥∑=1,（**） 故有 SudkmknSGOSuGnii=∑∑≤∈=≤⋅=−(*)1(**))(11)( 由 Tutte 定理， G 有完美匹配。

证毕 推论 3.2.2 (Peterson, 1891) 2边连通（无割边）的 3 正则图有完美匹配 证明：设 G 是 2 边连通的 3 正则图因 νε 3)(2)(==∑∈ GVvvd ，故 ν 为偶数由推论 3.2.1， G 有完美匹配 证毕 注： 有割边的 3 正则图未必有完美匹配，例如，对如下所示的图 G，因 ()3OG v−=，故无完美匹配 推论 3.2.3 偶数阶完全图nK2有 12 −n 个边不重的完美匹配 ……G1 G2 Gn SG\S 的奇分支 G\S 的偶分支Gv 5证明：用平面上正 12 −n 边形的点代表1221,,,−nvvv null ，而用其中心点代表nv2点用直线段连接每个顶点对， 即得nK2 构作匹配iM 为边nivv2和所有与nivv2垂直的边之集 易检验每个iM都是 G 的完美匹配，且不同的iM 无公共边例如，按这种方法构作出 K6的两个完美匹配如下图 (b)、 (c)所示显然，nv2关联的每条边对应这样一个完美匹配，故共有 12 −n 个边不重的完美匹配。

证毕 §3.3 二部图的匹配 定理 3.3.1 (Hall, 1935) 设 G 是具有二划分 ),( YX 的二部图，则 G 有饱和 X 的匹配当且仅当对 XS ⊆∀ ， SSN ≥)( ，其中 )(SN 表示 S 的所有邻点之集 证明：必要性设 G 有饱和 X 的匹配 M ，则对 XS ⊆∀ ，因 S 的顶点在 M 下和 )(SN 中顶点配对，故 SSN ≥)( 充分性：设 ),( YXG = 是二部图，且对 XS ⊆∀ ， SSN ≥)( 下用反证法 假如 G 没有饱和 X 的匹配，则 G 的最大匹配*M 不能饱和 X 的所有顶点设 u 是 X 的一个*M 不饱和点，并设 |{vA = u 到 v 有*M 交错路 } 由于*M 是最大匹配，故由 Berge 定理， u 是 A 中唯一的*M 非饱和点令 XAS ∩= ， YAT ∩= 注意 }{uS − 中的顶点在*M 下与 T 中的顶点一一配对（因 Su∈ ，且对 Tt ∈∀ ， u 与 t 有*M交错路tP 相连，而且 t 是*M 饱和的，故交错路tP 上最后一条边必是*M 的边，它将 S 中一个顶点与 t 配对而且不同的 t 会有 S 中不同的顶点相配，否则会有两条*M 的边关联到 S 中同一顶点） 。

因此 1−= ST (1) XYS T u M*的边 v6 v1 v3 v2 v5 v4 v6v1v3v2v5v4v6v1v3 v2 v5v4(a) (c) (b) 6此外， TSN ⊇)( （因 T 中顶点通过 S 中顶点与 u 连*M 交错路） ， 且 TSN ⊆)( （对 )(SN中每个顶点 t ,设它是 S 中顶点 s 的邻点,从 u 到 s 的*M 交错路必可延伸为 u 到 t 的*M 交错路） 故 TSN =)( (2) 由(1)、(2)知： () | | 1NS T S S==−k ，则 G 有 k 个边不重的完美匹配 证明： （1）先证 G 有完美匹配 证法１：设 ),( YXG = 是 k 正则二部图，则 YkGEXk == )( ，因 0>k ，故 YX = ，任取 XS ⊆ ，令 =1E {G 中与 S 关联的边}， =2E {G 中与 N(S)关联的边}则21EE ⊆ 因而SkEESNk =≥=12)( ，即 SSN ≥)( 由推论 3.3.2,G 有完美匹配 证法２: 由推论 3.3.1， G 中有饱和 X 的匹配因 YX = （如前所证） ，故这个匹配就是完美匹配。

（2）再证 G 中有 k 个边不重的完美匹配（用归纳法） 当 1=k 时，显然 设对所有 k 正则二部图，结论成立下证对 )1( +k 正则二部图。