第三章匹配理论 S3.1匹配与最大匹配 定义311设G是一个图,MsE(G),满足:对ve,e∈M,e与e,在G中不相邻,则 称M是G的一个匹配。对匹配M中每条边e=uv,其两端点u和v称为被匹配M所匹配, 而和v都称为是M饱和的( saturated vertex)。 注:每个顶点要么未被M饱和,要么仅被M中一条边饱和。 定义312设M是G的一个匹配,若G中无匹配M,使得|M'卜M|,则称M是G的 个最大匹配;如果G中每个点都是M饱和的,则称M是G的完美匹配( Perfect matching) 显然,完美匹配必是最大匹配 例如,在下图G中,边集{en}、{e;e2}、{en,e2,e3}都构成匹配,{e,e2e3}是G1的一个最大匹 配。在G2中,边集{e,e2,e3,e4}是一个完美匹配,也是一个最大匹配 定义313设M是G的一个匹配,G的M交错路是指其边M和E(G)\M中交替出现的 路。如果G的一条M交错路( alternating path)的起点和终点都是M非饱和的,则称其为一条M 可扩展路或M增广路( augmenting path)。 定理311( 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],(MeM'=M∪M'-M∩M称为对称差)。 则H中每个顶点的度非1即2(这是因为一个顶点最多只与M的一条边及M的一条边相关 。故H的每个连通分支要么是M的边与M'的边交替出现的一个偶长度圈,要么是M的 边与M'的边交替出现的一条路。由于|M|M|,H的边中M'的边多于M的边,故必有H 的某个连通分支是一条路,且始于M'的边又终止于M'的边。这条路是一条M可扩展路。这 与条件矛盾。证毕
1 第三章 匹配理论 §3.1 匹配与最大匹配 定义3.1.1 设G 是一个图, M ⊆ E(G) ，满足:对 i ∀ e , e j ∈ M ， i e 与 j e 在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). 显然, 完美匹配必是最大匹配。 例如，在下图G1中，边集{e1}、{e1,e2}、{e1,e2,e3}都构成匹配，{e1,e2,e3}是G1的一个最大匹 配。在 G2中，边集{e1,e2,e3,e4}是一个完美匹配，也是一个最大匹配。 定义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 ∪ M ′ − M ∩ M ′称为对称差)。 则 H 中每个顶点的度非1即2(这是因为一个顶点最多只与 M 的一条边及 M ′ 的一条边相关 联)。故 H 的每个连通分支要么是 M 的边与 M ′ 的边交替出现的一个偶长度圈，要么是 M 的 边与 M ′ 的边交替出现的一条路。由于| M ′ |>| M |，H 的边中 M ′ 的边多于 M 的边，故必有 H 的某个连通分支是一条路，且始于 M ′ 的边又终止于 M ′ 的边。这条路是一条 M 可扩展路。这 与条件矛盾。 证毕。 G1 G2 e1 e2 e3 e1 e2 e3 e4
§32完美匹配 定义32.1图G的奇分支:G的含有奇数个顶点的连通分支。用O(G)表示G的奇分支的个数。 定理321(Tutt,1947)图G有完美匹配的充分必要条件是对wScV(G),O(G\S)sS 证明( Lovasz,1973)必要性:设图G有完美匹配M。对vScV(G),若G\S无奇分支,则 O(G\S)=0:否则,设G1,G2…,G4是G\S的所有奇分支。注意每个G1中至少有一个顶 点l在M下与S中的某个顶点v配对(i=1,2…,k),(因G1是奇分支,M是完美匹配) 故O(G\S)=k={,y"2…,vk}|S。 奇分支 偶分支 充分性(反证法):设G满足:对vScv(G),O(G\S)s|S,但G没有完美匹配。首先, 取S=φ,知O(G)=0,故V(G)是偶数。现在,给G添加边以获得一个没有完美匹配而有尽 可能多的边的图G。因G是G的生成子图,故对vScV(G),G\S是G\S的生成子图, 从而 O(G\S)≤O(G\s)≤|S 令 U={uu∈(G),d.()=v-1} 若U=V(G),则G是偶数阶完全图,有完美匹配。这与G”的性质矛盾。因此 U≠V(G”),可以证明,此时G\U的每个连通分支都是完全图(记为命题A,另证)。 由(*)式,O(G\)≤{,即G-U的奇分支个数最多是{。但这样一来,G就 有一个完美匹配 G\U的各奇分支中的一个顶点和U的一个顶点配对;U中余下的顶点以及G\U的各 分支中余下的顶点在本分支内配对(由于各分支及U都是完全图)。 G’的奇分支 G'U的偶分支 (③③…
2 §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 Gk , , , 1 2 " 是G \ S 的所有奇分支。注意每个Gi 中至少有一个顶 点ui 在 M 下与 S 中的某个顶点 i v 配对（i = 1,2,", k ），（因Gi 是奇分支， M 是完美匹配）。 故O G S k v v v S ( \ ) = =|{ 1, 2 ,", k } |≤ 。 充分性（反证法）：设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 * 的生成子图， 从而 O(G \ S) ≤ O(G \ S) ≤ S * . （*） 令 { ( ), * ( ) 1} * U = u u ∈V G d u =ν − G . 若 ( ) * U = V G ，则 * G 是偶数阶完全图，有完美匹配。这与 * G 的性质矛盾。因此， ( ) * U ≠ V G ，可以证明，此时G \U * 的每个连通分支都是完全图（记为命题Ａ，另证）。 由（*）式，O(G \U) ≤ U * ，即G −U * 的奇分支个数最多是 U 。但这样一来， * G 就 有一个完美匹配： G \U * 的各奇分支中的一个顶点和U 的一个顶点配对；U 中余下的顶点以及G \U * 的各 分支中余下的顶点在本分支内配对（由于各分支及 U 都是完全图）。 u1 u2 … uk … S v2 … vk v1 … G1 G2 Gk 奇分支 偶分支 … … U G* \U 的奇分支 G* \U 的偶分支 …
这与G无完美匹配矛盾。证毕 命题A的证明:在上述充分性证明的条件下,当U≠V(G)时,G\U的每个连通分支都是 完全图 用反证法证明:若不然,设G\中某个连通分支G不是完全图,则(G)≥3。必存在 xy,z∈(G,),使得xy,y∈E(G),且xgE(G)。由于ygU,故必有与y不相邻的顶 ,即必存在w∈V(G\U),使得y≠E(G)。 由于G是不含完美匹配的极大图,所以G+x和G+y都含有完美匹配,分别设为M1和 M2。用H表示G∪{x,y}中由M1M2导出的子图。由于对vu∈(H),d1()=2或 0(由M1和M2都是完美匹配知),故H的每个非平凡连通分支都是其边在M1和M2中交替出 现的偶长度圈。下分两种情形 (1)x和y分别在H的不同分支中。设y在H的某个圈C上,则M1在C上的边连同 M2不在C上的边构成G的一个完美匹配。这与G的选择矛盾。 M1的边 M2的边 情形(1) 情形(2) (2)x和w在H的同一分支C中,由x和z的对称性,不妨设x,y,,z在C中依次出现 并设M1在C的yw…段中的边集为M!,M2在C的w…z段中的边集为M2,于是 M'U)U(M,\M, 是G”的完美匹配,又与G的选择矛盾 综合(1)、(2)两种情形,便证明了G"\U的每个连通分支都是完全图。证毕。 推论3,2.1(k-1)边连通偶数阶k正则图有完美匹配 证明:设G是命题中所述的k正则图。 当k=1时,结论显然 以下假定k≥2。设S是G的任一个非空顶点集,G1,G2,…,Gn是G\S的奇分支。令 v=(G),m1={lle是G,与S之间的连边}
3 这与 * G 无完美匹配矛盾。证毕. 命题Ａ的证明：在上述充分性证明的条件下，当 ( ) * U ≠ V G 时，G \U * 的每个连通分支都是 完全图。 用反证法证明：若不然，设 G \U * 中某个连通分支 Gi 不是完全图，则V (Gi ) ≥ 3。必存在 , , ( ) V Gi x y z ∈ ，使得 , ( ) E Gi xy yz ∈ ，且 ( ) E Gi xz ∉ 。由于 y ∉U ，故必有与 y 不相邻的顶 点，即必存在 ( \ ), * w∈V G U 使得 ( ) * yw∉ E G 。 由于 * G 是不含完美匹配的极大图，所以G + xz * 和G + yw * 都含有完美匹配，分别设为 M1和 M 2。用 H 表示G {xz, yw} * ∪ 中由 M1 ⊕ M 2 导出的子图。由于对∀u ∈V (H) ，d (u) = 2 H 或 0（由 M1和 M 2都是完美匹配知），故 H 的每个非平凡连通分支都是其边在 M1和 M 2中交替出 现的偶长度圈。下分两种情形： (1) xz 和 yw分别在 H 的不同分支中。设 yw在 H 的某个圈C 上，则 M1在 C 上的边连同 M2 不在 C 上的边构成 * G 的一个完美匹配。这与 * G 的选择矛盾。 情形（1） 情形（2） (2) xz 和 yw在 H 的同一分支Ｃ中，由 x 和 z 的对称性，不妨设 x, y,w,z 在C 中依次出现， 并设 M1在C 的 yw"z 段中的边集为 M1 ′ ， M 2在C 的 yw"z 段中的边集为 M2 ′ ，于是 { } ( \ ) 1 M2 M2 M ′ ∪ yz ∪ ′ 是 * G 的完美匹配，又与 * G 的选择矛盾。 综合(1)、(2)两种情形，便证明了G \U * 的每个连通分支都是完全图。证毕。 推论 3.2.1 ( k −1)边连通偶数阶k 正则图有完美匹配 证明：设G 是命题中所述的k 正则图。 当 k = 1时，结论显然。 以下假定 k ≥ 2 。设 S 是G 的任一个非空顶点集，G G Gn , , , 1 2 " 是G \ S 的奇分支。令 ( ), ν i = V Gi m e e i =|{ | 是Gi 与 S 之间的连边} |。 w z y x C M1 的边 M2 的边 w y x z C … U Gi x y w z
由于x’≥k-1,故m1≥k-1,(i=1,2,…,m)。 GS的奇分支 GS的偶分支 若存在i,使得m1=k-1,则因 24(0)=k,24(0)=A, 从而m1=∑da(v)-∑d()=kv1-26(G)。因此, vEl(G) 2E(G,)=kv-m1=kv-(k-1)=k(v-1)+1 但因v-1是偶数(每个G是奇分支),上式两端不可能相等。这个矛盾说明m2≥k (i=1,2,…,n),于是 m2≥k,(**) 故有 O()=5k2m5k4(0) 由 Tutte定理,G有完美匹配。证毕 推论322( Peterson,1891)2边连通(无割边)的3正则图有完美匹配。 证明:设G是2边连通的3正则图。因26=∑d(v)=3v,故v为偶数。由推论321,G有 完美匹配 证毕 注:有割边的3正则图未必有完美匹配,例如,对如下所示的图G,因O(G-v)=3,故无完 美匹配。 推论323偶数阶完全图K2n有2n-1个边不重的完美匹配
4 由于κ ′ ≥ k −1，故 mi ≥ k −1, (i = 1,2,",m) 。 若存在i ，使得 mi = k −1，则因 i v V G G d v k i ∑ = ν ∈ ( ) ( ) ， d v k S v S ∑ G = ∈ ( ) ，（*） 从而 ( ) ( ) 2 ( ) ( ) ( ) i i v V G G v V G mi dG v d v k G i i i = ∑ − ∑ = ν − ε ∈ ∈ 。因此， 2ε (Gi) = kν i − mi = kν i − (k −1) = k(ν i −1) +1。 但因ν i −1 是偶数（每个 Gi 是奇分支），上式两端不可能相等。这个矛盾说明 m k i ≥ （i = 1,2,",n) ，于是 m kn n i ∑ i ≥ =1 ,（**） 故有 d u S k m k O G S n u S G n i ≤ ∑ i ∑ = = ∈ − = ⋅ ≤ (**) 1 (*) ( ) 1 1 ( ) 由 Tutte 定理，G 有完美匹配。证毕。 推论 3.2.2 (Peterson, 1891) 2 边连通（无割边）的 3 正则图有完美匹配。 证明：设G 是 2 边连通的 3 正则图。因2ε ( ) 3ν ( ) = ∑ = v∈V G d v ，故ν 为偶数。由推论 3.2.1，G 有 完美匹配。 证毕 注：有割边的 3 正则图未必有完美匹配，例如，对如下所示的图 G，因OG v ( )3 − = ，故无完 美匹配。 推论 3.2.3 偶数阶完全图 K2n 有 2n −1个边不重的完美匹配。 … … G1 G2 Gn S G\S 的奇分支 G\S 的偶分支 G v
证明:用平面上正2n-1边形的点代表v1V2…,V2n,而用其中心点代表v2n点。用直线段连 接每个顶点对,即得K2n构作匹配M1为边vv2n和所有与v;V2n垂直的边之集。易检验每个M1 都是G的完美匹配,且不同的M,无公共边。例如,按这种方法构作出K6的两个完美匹配如下 图(b)、(c)所示。显然,v2n关联的每条边对应这样一个完美匹配,故共有2n-1个边不重的完 美匹配。证毕 (a) §33二部图的匹配 定理331(Hal,1935)设G是具有二划分(X,H)的二部图,则G有饱和x的匹配当且仅当 对vS≤X,|N(S)≥|s,其中N(S)表示S的所有邻点之集。 证明:必要性。设G有饱和X的匹配M,则对VSX,因S的顶点在M下和N(S)中 顶点配对,故N(S)≥5 充分性:设G=(X,)是二部图,且对∨S≤X,|N(S)≥|S。下用反证法。 假如G没有饱和X的匹配,则G的最大匹配M不能饱和X的所有顶点。设u是X的 个M不饱和点,并设 A={vla到v有M`交错路}。 由于M是最大匹配,故由 Berge定理,u是A中唯一的M非饱和点。令 S=A∩X,T=A∩Y M的边 注意S-{}中的顶点在M下与T中的顶点一一配对(因u∈S,且对vt∈T,u与t有M 错路P相连,而且t是M饱和的,故交错路P上最后一条边必是M的边,它将S中一个 顶点与t配对。而且不同的t会有S中不同的顶点相配,否则会有两条M的边关联到S中同 顶点)。因此 7=|s
5 证明：用平面上正 2n −1边形的点代表 1 2 2 1 , , , n− v v " v ，而用其中心点代表 n v2 点。用直线段连 接每个顶点对，即得 K2n 。构作匹配 Mi 为边 i n v v2 和所有与 i n v v2 垂直的边之集。易检验每个 Mi 都是G 的完美匹配，且不同的 Mi 无公共边。例如，按这种方法构作出 K6 的两个完美匹配如下 图(b)、(c)所示。显然， n v2 关联的每条边对应这样一个完美匹配，故共有2n −1个边不重的完 美匹配。证毕。 §3.3 二部图的匹配 定理 3.3.1 (Hall, 1935) 设G 是具有二划分(X,Y) 的二部图，则G 有饱和 X 的匹配当且仅当 对∀S ⊆ X ， N(S) ≥ S ，其中 N(S) 表示 S 的所有邻点之集。 证明：必要性。设G 有饱和 X 的匹配 M ，则对∀S ⊆ X ，因 S 的顶点在 M 下和 N(S) 中 顶点配对，故 N(S) ≥ S 。 充分性：设G = (X,Y) 是二部图，且对∀S ⊆ X ， N(S) ≥ S 。下用反证法。 假如G 没有饱和 X 的匹配，则G 的最大匹配 * M 不能饱和 X 的所有顶点。设u 是 X 的一 个 * M 不饱和点，并设 A = {v |u 到 v 有 * M 交错路}。 由于 * M 是最大匹配，故由 Berge 定理，u 是 A 中唯一的 * M 非饱和点。令 S = A∩ X ，T = A∩Y 。 注意 S −{u}中的顶点在 * M 下与T 中的顶点一一配对（因u ∈ S ，且对∀t ∈T ，u 与t 有 * M 交错路 Pt 相连，而且t 是 * M 饱和的，故交错路 Pt 上最后一条边必是 * M 的边，它将 S 中一个 顶点与t 配对。而且不同的t 会有 S 中不同的顶点相配，否则会有两条 * M 的边关联到 S 中同一 顶点）。因此 T = S −1。 (1) X Y S T u M* 的边 v6 v1 v3 v5 v2 v4 v6 v1 v3 v5 v2 v4 v6 v1 v3 v5 v2 v4 (a) (c) (b)