第三章匹配理论 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)
此外,N(S)彐T(因T中顶点通过S中顶点与a连M交错路),且N(S)∈T(对N(S) 中每个顶点t,设它是S中顶点s的邻点,从到s的M交错路必可延伸为u到t的M交错 路)。故 N(S)=7(2) 由(1)、(2)知:|N(S)=7上=S-10),则G有k个边不重的完美匹配 证明:(1)先证G有完美匹配 证法1:设G=(X,Y)是k正则二部图,则kx=|E(G=ky1,因k>0,故X=,任 取SX,令E1=G中与S关联的边},E2=G中与NS关联的边}。则E1E2。因而 4N(S)=|E2|2|E=kS,即N(S)≥|S。由推论332,G有完美匹配 证法2:由推论33.1,G中有饱和X的匹配。因X=(如前所证),故这个匹配就是完美 (2)再证G中有k个边不重的完美匹配(用归纳法) 当k=1时,显然 设对所有k正则二部图,结论成立。下证对(k+1)正则二部图G,结论也成立。 设M是G的一个完美匹配。令G′=G\M。则G′是k正则二部图。由归纳假设,G′中 有k个边不重的完美匹配。故G中有k+1个边不重的完美匹配。证毕。 下一推论是显然的。 推论334完全二部图Kk中存在k个边不重的完美匹配。 推论335设G=(XY)是二部图,且x1==n。若6(G)≥万,则G有完美匹配 证明(用反证法):若G没有完美匹配,则由推论3.3.2,存在SgX,S≠φ,使|N(S)kS|。 因G是二部图且δ(G)≥1,故|SN(S)δ(G)≥",且Y\N(S)≠p(因
6 此外，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) 由(1)、(2)知： NS T S S () | | 1 = = − 0) ，则G 有k 个边不重的完美匹配。 证明：（1）先证G 有完美匹配。 证法１：设G = (X ,Y) 是 k 正则二部图，则 k X = E(G) = k Y ，因 k > 0 ，故 X = Y ，任 取 S ⊆ X ，令 E1 = {G 中与 S 关联的边}， E2 = {G 中与 N(S)关联的边}。则 E1 ⊆ E2。因而 k N S = E ≥ E = k S 2 1 ( ) ，即 N(S) ≥ S 。由推论 3.3.2,G 有完美匹配。 证法２: 由推论 3.3.1，G 中有饱和 X 的匹配。因 X = Y （如前所证），故这个匹配就是完美 匹配。 （2）再证G 中有 k 个边不重的完美匹配（用归纳法）。 当 k = 1时，显然。 设对所有 k 正则二部图，结论成立。下证对(k +1) 正则二部图G ，结论也成立。 设 M 是G 的一个完美匹配。令G′ = G \ M 。则G′ 是 k 正则二部图。由归纳假设，G′ 中 有 k 个边不重的完美匹配。故G 中有 k +1个边不重的完美匹配。证毕。 下一推论是显然的。 推论 3.3.4 完全二部图 Kk ,k 中存在 k 个边不重的完美匹配。 推论 3.3.5 设G = (X.Y)是二部图，且 X = Y = n 。若 2 ( ) n δ G ≥ ，则 G 有完美匹配。 证明(用反证法)：若 G 没有完美匹配，则由推论 3.3.2，存在 S ⊆ X , S ≠ φ ，使| N(S) | N S ≥ δ G ≥ ， 且 Y \ N(S) ≠ φ （ 因
N(S)kS|SXHY|)。令∈Y\N(S),则N()X\S,因此, δ(G)≤da(u)=N(u)图x|-|Skn n 这与条件矛盾。故G有完美匹配。证毕。 例33.1下图所示的是14个大小相同的正方形组成的图形。试证明:不论如何用剪刀沿着图形 中所画的直线对它进行裁剪,总剪不出7个由相邻的两个小正方形组成的矩形来 证明:将图形中方格从1到14编号。以方格为顶点集作简单图G=(V,E,边∈E(G)当且 仅当i、j所在的方格在图形中相邻(有公共边) 注意G中每条边对应于原图形中由相邻两个小正方形组成的矩形,故剪出7个矩形相当于 在G中求由7条边组成的匹配。由于有14个顶点,故所求的是完美匹配。但这样的匹配是不 存在的。事实上,G是一个二部图,其二划分为 X={1,34.6,9,1112,14},Y={2,5,7,8,10,13}。 X=8>6=Y|。由推论332,不存在完美匹配。 注:G的k正则生成子图称为G的k因子。若G存在无公共边的k因子H1, 使得G=H1∪H2U…∪Hn,则称G是可k-因子分解的 推论323证明了完全图K是可1一因子分解的;推论334证明了完全二部图Kn,是可 1一因子分解的;推论3.33证明了每个k正则二部图是可1一因子分解的 若图G有1因子,则它显然应是偶数阶图。因此奇数阶完全图K2mn1不可能有1因子 因子分解是图论研究的一个重要选题,进一步的了解可参看 [1]G Chartrand, and O.R. Ollermann, Applied and Algorithmic Graph Theory, MCGraw-Hill, New York, 1993 [2J. Akiyama, M. Kano, Factors and factorizations of graphs -a survey, J Graph Theory, 9(1985) 3]W D. Wallis, One-factorizations, Kluwer Academic Publishers, Dordrecht, Boston, 1997 [4]Guizhen Liu, and Binhai Zhu, Some problems on factorizations with constraints in bipartite graphs, 128(2003),421-434
7 | N(S) | 6 = |Y|。由推论 3.3.2，不存在完美匹配。 注：G 的 k 正则生成子图称为 G 的 k 因子。若 G 存在无公共边的 k 因子 H H Hn , , , 1 2 " ， 使得G = H1 ∪ H2 ∪"∪ Hn ，则称 G 是可 k－因子分解的。 推论 3.2.3 证明了完全图 K2n 是可 1－因子分解的；推论 3.3.4 证明了完全二部图 Kn,n 是可 1－因子分解的；推论 3.3.3 证明了每个 k 正则二部图是可 1－因子分解的。 若图 G 有 1 因子，则它显然应是偶数阶图。因此奇数阶完全图 K2n+1 不可能有 1 因子。 因子分解是图论研究的一个重要选题，进一步的了解可参看 [1] G. Chartrand, and O.R. Ollermann, Applied and Algorithmic Graph Theory, MCGraw-Hill, New York, 1993. [2] J. Akiyama, M. Kano, Factors and factorizations of graphs — a survey, J. Graph Theory, 9(1985), 1-42. [3] W.D. Wallis, One-factorizations, Kluwer Academic Publishers, Dordrecht, Boston, 1997. [4] Guizhen Liu, and Binhai Zhu, Some problems on factorizations with constraints in bipartite graphs, 128(2003), 421-434. 4 5 6 7 1 2 3 8 9 10 11 12 13 14 4 1 6 7 8 5 2 3 9 10 11 12 13 14
§34二部图中最大匹配与最大权匹配的算法 、求完美匹配的匈牙利算法 1背景与问题 指派问题( assignment problem):欲安排n个人员x1,x2,…xn从事n项工作y1,y2,…,yn。已 知每个人能胜任其中一项或几项工作。试问:能否给每个人分配一项他所胜任的工作?若能, 如何求出这种安排? 图论描述:对于一个二部图G=(X,Y):X={x1,x2…xn},Y={y1,y2…,yn},当且仅当x 胜任工作y时,xy∈E(G)。问:G中是否有完美匹配?若有,如何求之? 2理论基础 Berge定理(定理3..):图G的匹配M是最大匹配的充要条件是G中不存在M可扩展路 Hal定理(定理33.1):设G是具有二划分(X,Y)的二部图,则G有饱和X的匹配当且仅当 对ⅤS≤X,N(S)≥|S,其中N(S)表示S的所有邻点之集 3匈牙利算法 匈牙利算法由匈牙利数学家 Egervary首先提出,后来由 Edmond(1965)基于 Berge定理和 Ha定理进行了改进[5]。这种算法既能判定一个二部图中完美匹配是否存在,又能在存在时求 出一个完美匹配。 [5]J. Edmonds, Path, tree and flowers, Canad. J. Math. 17(1965 )449-467 算法思想:从图G的任何匹配M开始。 若M饱和X,则M是G的完美匹配。 若M不饱和X,在X中选择一个M不饱和点x。若存在以x为起点的M增广路P,则由 Berge定理知M不是最大匹配,且M'=M⊕E(P)是比M更大的匹配。用M替代M重复上 述过程:若G中不存在以x为起点的M增广路,则可找到与x由M交错路相连的顶点集合A 而S=A∩X满足|N(S)kS|(见Hll定理的证明)。由Hal定理,G不存在完美匹配。 算法步骤 step0.任取图G的一个匹配M。 stepl.若M饱和X,则停止,M是G的完美匹配 否则,取Ⅹ中一个M不饱和点x,记S={x},T:=φ。 step2.若N(S)=T,则停止,G无完美匹配。(因N(S)HTHS|-1<S|)。 否则取y∈N(S)T。 step3.若y是M饱和的,设y∈M,令S:=SU{},T:=TU{y},转step2。(此时仍保
8 §3.4 二部图中最大匹配与最大权匹配的算法 一、求完美匹配的匈牙利算法 1.背景与问题 指派问题（assignment problem）：欲安排 n 个人员 n x , x ,"x 1 2 从事 n 项工作 n y , y , , y 1 2 " 。已 知每个人能胜任其中一项或几项工作。试问：能否给每个人分配一项他所胜任的工作？若能， 如何求出这种安排？ 图论描述：对于一个二部图 G = (X, Y )：X = { n x , x ,"x 1 2 }，Y＝{ n y , y , , y 1 2 " }，当且仅当 i x 胜任工作 j y 时， x y E(G) i j ∈ 。问：G 中是否有完美匹配？若有，如何求之？ 2.理论基础 Berge 定理（定理 3.1.1）：图G 的匹配 M 是最大匹配的充要条件是 G 中不存在 M 可扩展路。 Hall 定理（定理 3.3.1）：设G 是具有二划分(X,Y) 的二部图，则G 有饱和 X 的匹配当且仅当 对∀S ⊆ X ， N(S) ≥ S ，其中 N(S) 表示 S 的所有邻点之集。 3.匈牙利算法 匈牙利算法由匈牙利数学家 Egerváry 首先提出，后来由 Edmonds(1965)基于 Berge 定理和 Hall 定理进行了改进[5]。这种算法既能判定一个二部图中完美匹配是否存在，又能在存在时求 出一个完美匹配。 [5] J. Edmonds, Path, tree and flowers, Canad. J. Math. 17(1965)449-467. 算法思想：从图 G 的任何匹配 M 开始。 若 M 饱和 X，则 M 是 G 的完美匹配。 若 M 不饱和 X，在 X 中选择一个 M 不饱和点 x。若存在以 x 为起点的 M 增广路 P，则由 Berge 定理知 M 不是最大匹配，且 M ′ = M ⊕ E(P) 是比 M 更大的匹配。用 M ′ 替代 M 重复上 述过程；若 G 中不存在以 x 为起点的 M 增广路，则可找到与 x 由 M 交错路相连的顶点集合 A， 而 S = A∩ X 满足| N(S) |<| S |（见 Hall 定理的证明）。由 Hall 定理，G 不存在完美匹配。 算法步骤： step0. 任取图 G 的一个匹配 M。 step1. 若 M 饱和 X，则停止，M 是 G 的完美匹配。 否则，取 X 中一个 M 不饱和点 x，记 S := {x}, T := φ 。 step2. 若 N(S) = T ，则停止，G 无完美匹配。（因| N(S) |=| T |=| S | −1 <| S |）。 否则取 y ∈ N(S) \ T 。 step3. 若 y 是 M 饱和的，设 yz ∈ M ，令 S := S ∪{z}，T := T ∪{y}，转 step2。（此时仍保
持|THS|-1)。否则,取M增广路P(x,y),令M:=M⊕E(P),转 stepl 例341判断如下二部图是否存在完美匹配。若存在,求其出一个完美匹配;若不存在,给出 满足N(S)=T的集合S和T 解:从一个初始匹配M={x2y2,x3y3,x5y3}(图1)出发,执行匈牙利算法。因M尚未饱和X, 找到X中一个M未饱和点x1。从x1出发,反复执行算法第2步和第3步,找到一条M增广路 xyx2y(图2)。按第3步,沿增广路交换进入匹配和不进入匹配的边,匹配扩大为M {xy2,x2y1,x3y3,x5y5}(图3) ,Ⅹ V1 y2 y3 y4 y5 VI J2 J3 图1:图G=(X,Y)及一个匹配M 图2:M增广路x1yx2y 图3:无完美匹配 因M仍未饱和Ⅹ,按算法第1步,找到Ⅹ中一个M未饱和点x4。然后算法令 S={x4},T=φ,并转入第2步试图找一条从x4出发的M增广路。因当前N(S)={y2,y3} N(S)≠T,从N(S)\T中任意取出一个,比如y,转到第三步。因y是M饱和的,其匹配 点为x,按算法第3步,S和T更新为S={x4,x3},T={y3}。此后,转第2步判断是否 N(S)=T。因当前N(S)={y2,y3}≠T,故取y2∈N(S)\T,再次循环执行第3步,找到 y2的匹配点x1,S和T进一步更新为S={x4,x3,x1,},T={y3,y2},再转第2步。此时发现 N(S)={y2,y3}=T,因此该图不存在完美匹配。算法找到的满足N(S)=T的集合为 S={x4,x3,x1,},T={y3,y2}。 匈牙利算法的正确性由 Berge定理和Hall定理可知 匈牙利算法是多项式时间算法。事实上,设n=XHY|。算法每找到一条增广路更新 次匹配,匹配边增加一条,故最多需执行n次增广路的循环。 算法每找一条增广路需反复执行第2步和第3步“生长”交错路,这实际上是反复扩充集 合S和T的过程。算法每循环一次第2步和第3步,S和T的元素各增加1个由于|xyF=n 故这种扩张不会超过n次。 而算法每执行一次第二步和第三步,除了需要做两次赋值(S:=S∪{},T:=TU{y}) 和一次判断(y是否M饱和的)外,主要计算量在于判断N(S)=T。由于总有N(S)2T, 故可转为判断是否|N(S)T|。|T的计数可通过每次循环加1来实现,|N(S)的计数可用
9 持| T |=| S | −1) 。否则，取 M 增广路 P(x, y) ，令 M := M ⊕ E(P) ，转 step1. 例 3.4.1 判断如下二部图是否存在完美匹配。若存在，求其出一个完美匹配；若不存在，给出 满足 N(S) = T 的集合 S 和 T。 解：从一个初始匹配 M＝ 22 33 55 {,,} x y xy xy （图 1）出发，执行匈牙利算法。因 M 尚未饱和 X， 找到 X 中一个 M 未饱和点 x1。从 x1出发，反复执行算法第 2 步和第 3 步，找到一条 M 增广路 x1 y2 x2 y1（图 2）。按第 3 步，沿增广路交换进入匹配和不进入匹配的边，匹配扩大为 M＝ 12 21 33 55 {, , , } x y xy xy xy （图 3）。 图 1：图 G=(X,Y)及一个匹配 M 图 2：M 增广路 x1 y2 x2 y1 图 3：无完美匹配 因 M 仍未饱和 X，按算法第 1 步，找到 X 中一个 M 未饱和点 x4。然后算法令 4 S xT = = { }, φ ，并转入第 2 步试图找一条从 x4 出发的 M 增广路。因当前 2 3 NS y y () { , } = ， NS T ( ) ≠ ，从 NS T ( )\ 中任意取出一个，比如 y3，转到第三步。因 y3 是 M 饱和的，其匹配 点为 x3，按算法第 3 步，S 和 T 更新为 43 3 S xx T y = { , }, { } = 。此后，转第 2 步判断是否 N(S) = T 。因当前 2 3 NS y y T () { , } = ≠ ，故取 2 y ∈ NS T ( )\ ，再次循环执行第 3 步，找到 y2 的匹配点 x1，S 和 T 进一步更新为 4 31 3 2 S xxx T yy = { , , ,}, { , } = ，再转第 2 步。此时发现 2 3 NS y y T () { , } = = ，因此该图不存在完美匹配。算法找到的满足 N(S) = T 的集合为 4 31 3 2 S xxx T yy = = { , , ,}, { , }。 匈牙利算法的正确性由 Berge 定理和 Hall 定理可知。 匈牙利算法是多项式时间算法。事实上，设nXY =| || | = 。算法每找到一条增广路更新一 次匹配，匹配边增加一条，故最多需执行 n 次增广路的循环。 算法每找一条增广路需反复执行第 2 步和第 3 步“生长”交错路，这实际上是反复扩充集 合 S 和 T 的过程。算法每循环一次第 2 步和第 3 步，S 和 T 的元素各增加 1 个。由于| || | X = = Y n ， 故这种扩张不会超过 n 次。 而算法每执行一次第二步和第三步，除了需要做两次赋值（ S := S ∪{z}，T := T ∪{y}） 和一次判断（y 是否 M 饱和的）外，主要计算量在于判断 N(S) = T 。由于总有 NS T ( ) ⊇ ， 故可转为判断是否| ( )| | | NS T = 。| T |的计数可通过每次循环加 1 来实现，| ( )| N S 的计数可用 x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 y1 y2 y3 y4 y5 x1 x2 x3 x4 x5 x1 x2 x3 x4 x5 y1 y2 y3 y4 y5 x1 x2 x3 x4 x5 y1 y2 y3 y4 y5
上一循环的|N(S)|值加上本次循环新进入S集合的点二在Y-N(S)中的邻点数计算,这需要 不超过Y=n次判断。因此算法总的计算复杂度约为n·n·(n+6)=O(n)。 注:(1)匈牙利算法稍加修改后可用于求二部图的最大匹配(留作习题); (2)也可在匈牙利算法中引入标号方法,此时算法的计算复杂度为O(U·E)。具体可参看 文献6或[7。 (3)求二部图最大匹配目前已知的最好算法是 Hopcroft和Karp提出的一个O(23)算法 读者可参看文献[7或[8] (4)求一般图的最大匹配也有多项式时间算法。第一个多项式时间算法是由 Edmonds给出 的一个O(U)阶算法。关于该算法读者可参看文献[9],也可在文献[6]、[7或[10]-[12中找到对 该算法的描述。 ahuja、 Magnanti和Oin对这一算法进行了处理,将其复杂度降低为OU3) Even和 Kariv提出的一个算法将时间复杂度改进到O(U25)。目前已知的最快算法是Mcai 和 Vazirani提出的O(EU03)阶算法13161,该算法对稀疏图运算时,比O(25)算法快 [6]谢政,网络算法与复杂性理论(第二版),国防科技大学出版社,2003 7]DB.west, Introduction to Graph Theory( (second edition), Prentice Hall2001(中译本:李建中、 骆吉周译,图论导引,机械工业出版社,2006)。 [8]J. Hopcroft, and R. M. Karp, An O(n")algorithm for maximum matching in bipartite graphs, SIAM J Computing, 2(1973), 225-231 [9]J. Edmonds, Paths, trees, and flowers, Canad. J. Math., 17(1965),449-467 [10] C H. Papadimitriou K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc, Englewood Cliffs, New Jersey, 1982 [ll田丰,马仲蕃,图与网络流理论,科学出版社,北京,1987。 [12]蒋长浩,图论与网络流,中国林业出版社,2001。 [13]R K. Ahuja, T L. Magnanti, J. B. Orlin, Network Flows: Theory, Algorithms, and Applications Prentice hall993(影印版:网络流:理论算法与应用,机械工业出版社,2005年)。 [14]S. Even, and O Kariv, An O(n) algorithm for maximum matching in general graphs, in Proc 16 IEEE Symp. Found. Comp. Sci., 1975, 100-112 [15]S Micali, and V.V. Vazirani, An O(V D algorithm for finding maximum matching in general graphs. in Proc. 21 IEEE Symp. Found. Comp. Sci., ACM(1980), 17-27 [16] V.V. Vazirani, A theory of alternating paths and blossoms for proving correctness of the O(.IED general graph matching algorithm, Combinatorica, 14(1994),71-91 [17 H W. Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 2(1955),83-97 [18]J. Munkres, Algorithms for the assignment and transportation problems, J. Soc. Indust. Appl Math.5(1957),32-38
10 上一循环的| ( )| N S 值加上本次循环新进入 S 集合的点 z 在Y NS − ( ) 中的邻点数计算，这需要 不超过|Y|＝n 次判断。因此算法总的计算复杂度约为 3 n n n On ⋅⋅ + = ( 6) ( ) 。 注：(1) 匈牙利算法稍加修改后可用于求二部图的最大匹配（留作习题）； (2) 也可在匈牙利算法中引入标号方法，此时算法的计算复杂度为O( ) υ ⋅ε 。具体可参看 文献[6]或[7]。 (3) 求二部图最大匹配目前已知的最好算法是 Hopcroft 和 Karp 提出的一个 2.5 O( ) υ 算法。 读者可参看文献[7]或[8]。 (4) 求一般图的最大匹配也有多项式时间算法。第一个多项式时间算法是由 Edmonds 给出 的一个 4 O( ) υ 阶算法。关于该算法读者可参看文献[9]，也可在文献[6]、[7]或[10]~[12]中找到对 该算法的描述。Ahuja、Magnanti 和 Orlin 对这一算法进行了处理[13]，将其复杂度降低为 3 O( ) υ 。 Even 和 Kariv 提出的一个算法[14]将时间复杂度改进到 2.5 O( ) υ 。目前已知的最快算法是 Micali 和 Vazirani 提出的 0.5 O( ) ευ 阶算法[15,16 ]，该算法对稀疏图运算时，比 2.5 O( ) υ 算法快。 [6] 谢政，网络算法与复杂性理论（第二版），国防科技大学出版社，2003。 [7] D.B. West, Introduction to Graph Theory (second edition), Prentice Hall, 2001。（中译本：李建中、 骆吉周译，图论导引，机械工业出版社，2006）。 [8] J. Hopcroft, and R.M. Karp, An 2.5 O n( ) algorithm for maximum matching in bipartite graphs, SIAM J. Computing, 2(1973),225-231. [9] J. Edmonds, Paths, trees, and flowers, Canad. J. Math., 17(1965), 449-467. [10] C.H. Papadimitriou & K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc., Englewood Cliffs, New Jersey, 1982. [11] 田丰，马仲蕃，图与网络流理论，科学出版社，北京，1987。 [12] 蒋长浩，图论与网络流，中国林业出版社，2001。 [13] R.K. Ahuja, T.L. Magnanti, J. B. Orlin, Network Flows : Theory, Algorithms, and Applications, Prentice Hall, 1993.(影印版：网络流：理论算法与应用，机械工业出版社，2005 年)。 [14] S. Even, and O. Kariv, An 2.5 O n( ) algorithm for maximum matching in general graphs, in Proc. 16th IEEE Symp. Found. Comp. Sci., 1975, 100-112. [15] S. Micali, and V.V. Vazirani, An OVE ( | | | |) ⋅ algorithm for finding maximum matching in general graphs. in Proc. 21th IEEE Symp. Found. Comp. Sci., ACM (1980), 17-27. [16] V.V. Vazirani, A theory of alternating paths and blossoms for proving correctness of the OVE ( | | | |) ⋅ general graph matching algorithm, Combinatorica, 14(1994),71-91. [17] H.W. Kuhn, The Hungarian method for the assignment problem, Naval Research Logistics Quarterly, 2(1955), 83-97. [18] J. Munkres, Algorithms for the assignment and transportation problems, J. Soc. Indust. Appl. Math. 5(1957), 32-38