中国社会科学院：图论与网络流理论（一）：图论讲义3匹配

1 第三章 匹配理论 §3.1 匹配与最大匹配 定义 3.1.1 设 G 是一个图, )(GEM ? ,满足:对 i e? , Me j ∈ , i e 与 j e 在 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). 显然,完美匹配必是最大匹配。 定义 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 ′?′=′⊕ IU 称为对称差)。 则 H 中每个顶点的度非1即2(这是因为一个顶点最多只与 M 的一条边及 M′的一条边相关 联)。故 H 的每个连通分支要么是 M 的边与 M′的边交替出现的一个偶长度圈，要么是 M 的 边与 M′的边交替出现的一条路。 由于 |||| MM >′ ， H 的边中 M′的边多于 M 的边， 故必有 H 的某个连通分支是一条路，且始于 M′的边又终止于 M′的边。这条路是一条 M 可扩展路。这 与条件矛盾。 证毕。 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 ；否则，设 n GGG ,,, 21 L 是 SG \ 的所有奇分支。注意每个 i G 中至少有一个顶 点 i u 在 M 下与 S 中的某个顶点 i v 配对（ ni ,,2,1 L= ） ， （因 i G 是奇分支， M 是完美匹配） 。 故 SvvvnSGO n ≤== |},,,{|)\( 21 L 。 充分性（反证法） ：设 G 满足：对 )(GVS ?? ， SSGO ≤)\( ，但 G 没有完美匹配。首先， 取 φ=S ，知 0)( =GO ，故 )(GV 是偶数。现在，给 G 添加边以获得一个没有完美匹配而有尽 可能多的边的图 * G 。因 G 是 * G 的生成子图，故对 )(GVS ?? ， SG \ 是 SG * 的生成子图， 从而 SSGOSGO ≤≤ )\()\( * . （ *） 令 }1)(),({ * * ?=∈= νudGVuuU G . 若 )( * GVU = ，则 * G 是偶数阶完全图，有完美匹配。这与 * G 的性质矛盾。因此， )( * GVU ≠ ，可以证明，此时 UG * 的每个连通分支都是完全图（此记为命题Ａ，另证） 。 由（ *）式， UUGO ≤)\( * ，即 UG ? * 的奇分支个数最多是 U 。但这样一来， * G 就 有一个完美匹配： UG * 的各奇分支中的一个顶点和 U 的一个顶点配对； U 中余下的顶点以及 UG * 的各 分支中余下的顶点在本分支内配对（由于各分支及 U 都是完全图） 。 … u 1 u 2 u n … S … v 2 v n v 1 … G 1 G 2 G n 奇分支 偶分支 … … U G * \U 的奇分支 G * \U 的偶分支 … 3 这与 * G 无完美匹配矛盾。证毕 . 命题Ａ的证明： 当 )( * GVU ≠ 时， UG * 的每个连通分支都是完全图。 用反证法证明：若不然，设 UG * 中某个连通分支 i G 不是完全图，则 3)( ≥ i GV 。必存在 )(,, i GVzyx ∈ ，使得 )(, i GEyzxy ∈ ，且 )( i GExz? 。由于 Uy? （故必有与 y 不相邻的顶 点） ，故必存在 ),\( * UGVw∈ 使得 )( * GEyw? 。 由于 * G 是不含完美匹配的极大图，所以 xzG + * 和 ywG + * 都含有完美匹配，分别设为 1 M 和 2 M 。用 H 表示 { }ywxzG , * U 中由 21 MM ⊕ 导出的子图。由于对 )(HVu∈? ， 2)( =ud H 或 0（由 1 M 和 2 M 都是完美匹配知） ，故 H 的每个非平凡连通分支都是其边在 1 M 和 2 M 中交替出 现的偶长度圈。下分两种情形： (1) xz 和 yw分别在 H 的不同分支中。设 yw在 H 的某个圈 C 上，则 1 M 在 C 上的边连同 2 M 不在 C 上的边构成 * G 的一个完美匹配。这与 * G 的选择矛盾。 情形（ 1） 情形（ 2） (2) xz 和 yw在 H 的同一分支Ｃ中， 由 x 和 z 的对称性， 不妨设 zwyx ,,, 在 C 中依次出现， 并设 1 M 在 C 的 zywL 段中的边集为 1 M′， 2 M 在 C 的 zywL 段中的边集为 2 M′，于是 )\(}{ 221 MMyzM ′′ UU 是 * G 的完美匹配，又与 * G 的选择矛盾。 综合 (1)、 (2)两种情形，便证明了 UG * 的每个连通分支都是完全图。证毕。 推论 3.2.1（ 1?k ）边连通偶数阶 k 正则图有完美匹配 证明：设 G 是命题中所述的 k 正则图。 当 1=k 时，结论显然。 以下假定 2≥k 。设 S 是 G 的任一个非空顶点集， n GGG ,,, 21 L 是 SG \ 的奇分支。令 ),( ii GV=ν eem i |{|= 是 i G 与 S 之间的连边 |} 。 w z y x C M 1 的边 M 2 的边 w y x z C … U G i x wy z 4 由于 1?≥′ kκ ，故 1?≥ km i , ),,2,1( mi L= 。 若存在 i ，使得 1?= km i ，则因 i GVv G kvd i ν= ∑ ∈ )( )( ， Skvd Sv G = ∑ ∈ )( ， （ *） 从而 )(2)()( )()( ii GVv G GVv Gi Gkvdvdm i i i εν ?=?= ∑∑ ∈∈ 。因此， 1)1()1()(2 +?=??=?= iiiii kkkmkG νννε 。 但因 1? i ν 是偶数（每个 i G 是奇分支） ，上式两端不可能相等。这个矛盾说明 km i ≥ （ ),,2,1 ni L= ，于是 knm n i i ≥ ∑ =1 ,（**） 故有 Sud k m k nSGO Su G n i i = ∑∑ ≤ ∈= ≤?=? (*)1(**) )( 11 )( 由 Tutte 定理， G 有完美匹配。证毕。 推论 3.2.2 (Peterson, 1891) ２－边连通（无割边）的３正则图有完美匹配。 证明：设 G 是２边连通的３正则图。因 νε 3)(2 )( == ∑ ∈ GVv vd ，故 ν 为偶数。由推论 3.2.1， G 有 完美匹配。 证毕 注： 有割边的３正则图未必有完美匹配，例如： 因 ,3)( =? vGO 故无完美匹配。 推论 3.2.3 偶数阶完全图 n K 2 有 12 ?n 个边不重的完美匹配。 证明 1：当 1=n 时，结论显然。下设 2≥n 。 … … G 1 G 2 G n S G\S 的奇分支 G\S 的偶分支 G v 5 令 {} nn vvvKV 2212 ,,,)( L= ，对每个 12,,2,1 ?= ni L ，构作一个匹配: {}{ }1,,2,1 2 ?== +? njvvvvM jijinii LU , 其中 ji ? 和 ji + 都是 )12mod( ?n 的，易检验每个 i M 都是 G 的完美匹配，且不同的 i M 无公 共边。 证明 2：用平面上正 12 ?n 边形的点代表 1221 ,,, ?n vvv L ，而用其中心点代表 n v 2 点。用直线段 连接每个顶点，即得 n K 2 ， i M 的边为 ni vv 2 和所有与 ni vv 2 垂直的边。 例： 习题五 1． 证明：若图 G 是连通简单图但不是完全图，则 G 中存在三个顶点 u、 v 和 w，使得 )(, GEvwuv ∈ ,而 )(GEuw? 。 2． 证明：一棵树最多只有一个完美匹配。 3． 证明树 G 有完美匹配当且仅当对 )(GVv∈? 都有 1)( =? vGO 。 4． 两人在图 G 上做游戏：交替选择相异的顶点 L,,, 210 vvv ，使得对每个 i vi ,0> 相邻于 1?i v ， 选择最后一个顶点者获胜。证明：第一个选点人有一个得胜策略当且仅当图 G 没有完美匹 配。 §3.3 二部图的匹配 定理 3.3.1 (Hall, 1935) 设 G 是具有二划分 ),( YX 的二部图，则 G 有饱和 X 的匹配当且仅当 对 XS ?? ， SSN ≥)( ，其中 )(SN 表示 S 的所有邻点之集。 证明：必要性。设 G 有饱和 X 的匹配 M ，则对 XS ?? ，因 S 的顶点在 M 下和 )(SN 中 顶点配对，故 SSN ≥)( 。 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 6 v 1 v 3 v 2 v5 v 4 v 6 v 1 v 3 v 2 v 5 v 4 v 6 v 1 v 3 v 2 v5 v 4 6 充分性：设 ),( YXG = 是二部图，且对 XS ?? ， SSN ≥)( 。下用反证法。 假如 G 没有饱和 X 的匹配，则 G 的最大匹配 * M 不能饱和 X 的所有顶点。设 u 是 X 的一 个 * M 不饱和点，并设 |{vA = u 到 v 有 * M 交错路 }。 由于 * M 是最大匹配，故由 Berge 定理， u 是 A 中唯一的 * M 非饱和点。令 XAS I= ， YAT I= 。 注意 }{uS ? 中的顶点在 * M 下与 T 中的顶点一一配对（因 Su∈ ，且对 Tt ∈? ， u 与 t 有 * M 交错路 t P 相连，而且 t 是 * M 饱和的，故交错路 t P 上最后一条边必是 * M 的边，它将 S 中一个 顶点与 t 配对。而且不同的 t 会有 S 中不同的顶点相配，否则会有两条 * M 的边关联到 S 中同一 顶点） 。因此 1?= ST 。 (1) 此外， TSN ?)( （因 T 中顶点通过 S 中顶点与 u 连 * M 交错路） ， 且 TSN ?)( （对 )(SN 中每个顶点 t ,设它是 S 中顶点 s 的邻点,从 u 到 s 的 * M 交错路必可延伸为 u 到 t 的 * M 交错 路） 。故 TSN =)( (2) 由(1)、(2)知： SSTSN <?== 1)( ，这与定理条件矛盾。证毕。 推论 3.3.1 设 ),( YXG = 是二部图，若 X 中每个顶点至少关联 k 条边（ )1≥k 而 Y 中每个顶 点至多关联 k 条边，则 G 中存在饱和 X 的匹配。 证明：由条件知，对 XS ?? ， S 至少关联 || Sk 条边。这 || Sk 条边至少关联 Y 中 || S 个顶点。 即 SSN ≥)( ，由 Hall 定理， G 有饱和 X 的匹配。证毕。 推论 3.3.2.(Frobenius,1917) 具有二划分 ),( YX 的二部图 G 有完美匹配的充分必要条件是 YX = 且对 XS ?? （或 Y ） ，均有 |||)(| SSN ≥ 。 证明：显然。 推论 3.3.3 (K?nig,1916) 设 G 是 k 正则二部图 )0( >k ，则 G 有 k 个边不重的完美匹配。 证明：先证 G 有完美匹配。 X Y S T u M * 的边 7 证法１：设 ),( YXG = 是 k 正则二部图，则 YkGEXk == )( ，因 0>k ，故 YX = ，任 取 XS ? ，令 = 1 E {G 中与 S 关联的边}， = 2 E {G 中与 N(S)关联的边}。则 21 EE ? 。因而 SkEESNk =≥= 12 )( ，即 SSN ≥)( 。由推论 3.3.2,G 有完美匹配。 证法２: 由推论 3.3.1， G 中有饱和 X 的匹配。因 YX = （如前所证） ，故这个匹配就是完美 匹配。 再证 G 中有 k 个边不重的完美匹配（用归纳法） 。 当 1=k 时，显然。 设对所有 k 正则二部图，结论成立。下证对 )1( +k 正则二部图 G ，结论也成立。 设 M 是 G 的一个完美匹配。令 MGG \=′ 。则 G′是 k 正则二部图。由归纳假设， G′中 有 k 个边不重的完美匹配。故 G 中有 1+k 个边不重的完美匹配。证毕。 下一推论是显然的。 推论 3.3.4 完全二部图 kk K , 中存在 k 个边不重的完美匹配。 推论 3.3.5 设 ).( YXG = 是二部图，且 nYX == 。若 2 )( n G ≥δ ，则 G 有完美匹配。 证明(用反证法)：若 G 没有完美匹配，则由推论 3.3.2，存在 φ≠? SXS , ，使 |||)(| SSN < 。 因 G 是二部图且 2 )( n G ≥δ ，故 2 )(|)(||| n GSNS ≥≥> δ ，且 φ≠)(\ SNY （因 |||)(| SSN < |||| YX =≤ ） 。令 )(\ SNYu∈ ，则 SXuN \)( ? ，因此， 22 |||||)(|)()( nn nSXuNudG G =?<?≤=≤δ 。 这与条件矛盾。故 G 有完美匹配。证毕。 例 3.3.1 下图所示的是 14 个大小相同的正方形组成的图形。试证明：不论如何用剪刀沿着图形 中所画的直线对它进行裁剪，总剪不出 7 个由相邻的两个小正方形组成的矩形来。 证明：将图形中方格从 1 到 14 编号。以方格为顶点集作简单图 G = (V, E)，边 )(GEij∈ 当且 仅当 i、 j 所在的方格在图形中相邻（有公共边） 。 注意 G 中每条边对应于原图形中由相邻两个小正方形组成的矩形，故剪出 7 个矩形相当于 在 G 中求由 7 条边组成的匹配。由于有 14 个顶点，故所求的是完美匹配。但这样的匹配是不 存在的。事实上， G 是一个二部图，其二划分为 X={1,3,4,6,9,11,12,14}， Y={2,5,7,8,10,13}。 4 6 75 1 32 8 9 1110 12 13 14 4 1 6 7 8 5 32 9 1110 12 13 14 8 |X| = 8 > 6 = |Y|。由推论 3.3.2，不存在完美匹配。 注 ： G 的 k 正则生成子图称为 G 的 k 因子。若 G 存在无公共边的 k 因子 n HHH ,,, 21 L ， 使得 n HHHG ULUU 21 = ，则称 G 是可 k－因子分解的。 推论 3.2.3 证明了完全图 n K 2 是可 1－因子分解的；推论 3.3.4 证明了完全二部图 nn K , 是可 1－因子分解的；推论 3.3.3 证明了每个 k 正则二部图是可 1－因子分解的。 §3.4 二部图中最大匹配与最大权匹配的算法 一、求完美匹配的匈牙利算法 1.背景与问题 指派问题 （ assignment problem） ：欲安排 n 个人员 n xxx L,, 21 从事 n 项工作 n yyy ,,, 21 L 。已 知每个人能胜任其中一项或几项工作。试问：能否给每个人分配一项他所胜任的工作？若能， 如何求出这种安排？ 图论描述 ：对于一个二部图 G = (X, Y )： X = { n xxx L,, 21 }， Y＝ { n yyy ,,, 21 L }，当且仅当 i x 胜任工作 j y 时， )(GEyx ji ∈ 。问： G 中是否有完美匹配？若有，如何求之？ 2.理论基础 Berge 定理（定理 3.1.1） ：图 G 的匹配 M 是最大匹配的充要条件是 G 中不存在 M 可扩展路。 Hall 定理（定理 3.3.1） ：设 G 是具有二划分 ),( YX 的二部图，则 G 有饱和 X 的匹配当且仅当 对 XS ?? ， SSN ≥)( ，其中 )(SN 表示 S 的所有邻点之集。 3.匈牙利算法 匈牙利算法由匈牙利数学家 Egerváry 首先提出，后来由 Edmonds(1965)基于 Berge 定理和 Hall 定理进行了改进。这种算法既能判定一个二部图中完美匹配是否存在，又能在存在时求出 一个完美匹配。 算法思想 ：从图 G 的任何匹配 M 开始。 若 M 饱和 X，则 M 是 G 的完美匹配。 若 M 不饱和 X，在 X 中选择一个 M 不饱和点 x。若存在以 x 为起点的 M 增广路 P，则由 Berge 定理知 M 不是最大匹配，且 )(PEMM ⊕=′ 是比 M 更大的匹配。用 M′替代 M 重复上 述过程；若 G 中不存在以 x 为起点的 M 增广路，则可找到与 x 由 M 交错路相连的顶点集合 A， 而 XAS I= 满足 |||)(| SSN < （见 Hall 定理的证明） 。由 Hall 定理， G 不存在完美匹配。 匈牙利算法： step0. 任取图 G 的一个匹配 M。 9 step1. 若 M 饱和 X，则停止， M 是 G 的完美匹配。 否则，取 X 中一个 M 不饱和点 x，记 φ== :},{: TxS 。 step2. 若 TSN =)( ，则停止， G 无完美匹配。 （因 ||1|||||)(| SSTSN <?== ） 。 否则取 TSNy \)(∈ 。 step3. 若 y 是 M 饱和的，设 Myz∈ ，令 }{: zSS U= ， }{: yTT U= ，转 step2。 （此时仍保 持 )1|||| ?= ST 。否则，取 M 增广路 ),( yxP ，令 )(: PEMM ⊕= ，转 step1. 例 3.4.1 图 G=(X,Y)及一个匹配 M M增广路 x 1 y 2 x 2 y 1 无完美匹配 注： （ 1）匈牙利算法是多项式时间算法，时间复杂度为 |)||(| EXO ? ； （ 2）匈牙利算法稍加修改可求二部图的最大匹配； （ 3）求任意图的最大匹配的多项式时间算法已由 Edmonds 给出。 二、求最大权匹配的 Kuhn－ Munkres 算法 1.背景与问题 最优指派问题 ：欲安排 n 个人员 n xxx L,, 21 从事 n 项工作 n yyy ,,, 21 L 。已知每个人能胜任其 中一项或几项工作，各人做不同工作的效率不同。求一种工作安排使得总的工作效率达到最大。 图论描述 ：给定赋权完全二部图 G = (X, Y )： X = { n xxx L,, 21 }， Y＝ { n yyy ,,, 21 L }，边 ji xx 有权 ij w （权可以为 0，这表示 i x 不胜任工作 j y ） 。求 G 的一个具有最大权的完美匹配。 2.算法的理论基础 null 顶点标号与可行顶点标号（ feasible vertex labeling） 图 G 的顶点标号是从顶点集到正整数集的一个映射，对于赋权完全图 ),( , wK nn ，若对每条 边 xye = ，均有 )()()( xywylxl ≥+ ，则称这个标号为 ),( , wK nn 的一个可行顶点标号。 例 3.4.2 一个二部图及其可行顶点标号 注 ：可行顶点标号总是存在的。一种平凡的可行标号是： x 2 x 3 x 4 x 5 x 1 y 2 y 3 y 4 y5 y 1 x 2 x 3 x 4 x5 x 1 y 2 y 3 y 4 y 5 y 1 x 2 x 3 x 4 x5 x 1 y 2 y 3 y 4 y5 y 1 1 2 2 1 0 0 1 1 2 2 X Y 10 ? ? ? ∈ ∈ = ∈ Yv Xvvyw vl Yy ,0 ),(max )( 。 null 相等子图 记 nn KG , = ，设 l 是 ),( wG 的一个可行的顶点标号。令 l E ＝ )}()()(|)({ xywylxlGExy =+∈ ， G 中以 l E 为边集的生成子图称为 G 的 l 相等子图，记为 l G 。注意 l G 的顶点集与 G 的顶点集相 同。 例 3.4.3 ? ? ? ? ? ? ? ? ? ? ? ? ? ? = 0010 0442 2022 4553 4 3 2 1 4321 x x x x yyyy w 图 G 中各边的权 图 G 的平凡标号 对应的相等子图 定理 3.4.1 设 l 是图 G 的一个可行顶点标号。若相等子图 l G 有完美匹配 M * ，则 M * 是 G 的最大 权完美匹配。 证明：由于相等子图 l G 是 G 的生成子图，故 l G 的完美匹配 * M 也是 G 的完美匹配，而且 ∑∑ ∈∈ == VvMe vlewMw )()()( * * . 另一方面，对 G 的任何完美匹配 M，有： ∑∑ ∈∈ ≤= VvMe vlewMw )()()( 可见 )()( * MWMW ≥ ，即 * M 是 G 的最大匹配。证毕。 由定理 3.4.1 知，欲求赋权完全二部图的最大权匹配，只需求出某个相等子图 l G 中的完美 匹配即可， 这可用匈牙利方法求得。 问题是， 如果相等子图 l G 中无完美匹配时怎么办？ Kuhn 和 Munkres 给出修改标号的一个方法，使得新的相等子图的最大匹配逐渐扩大，最终得到有完美 匹配的相等子图。 3.算法思想： 首先给出 K n,n 的任意一个可行顶点标号（如平凡标号） ，然后决定相等子图 l G ，在 l G 中执 行匈牙利算法。若在 l G 中找到完美匹配，则由定理 3.4.1，它就是 G 的最大权匹配。否则，匈 牙利算法终止于 XS ? ， YT ? ，且 TSN l G =)( 。令： }\,)()()(min{ TYySxxywylxl l ∈∈?+=α ， (*) 修改标号如下 x 2 x 3 x 4 x 1 y 2 y 3 y 4 y 1 5 0 2 4 1 0 0 0 x 2 x 3 x 4 x 1 y 2 y 3 y 4 y 1 11 ? ? ? ? ? ∈+ ∈? =′ 其它)( )( )( )( ul Tuul Suul ul l l α α 。 (**) 可以检验 l′仍是一个可行标号。 用 l′替代 l。 l G ′ 的边数比 l G 的 多。继续上述过程，直到获得一个相等子图含有完全美匹配为 止。 4. 算法－ Kuhn-Munkres 算法： Step 1. 从任一可行的顶点标号 l 开始，决定 l G . Step 2. 在 l G 中执行匈牙利算法，如果求得完美匹配 M，则 M 即为 G 的最大权匹配，算法 停止；否则，匈牙利算法必终止于某个 XS ? 和 YT ? 使得 TSN l G =)( ，此时转下步。 Step 3. 按 (*)式计算 l α ，按 (**)计算新的可行顶点标号 l′, 以 l′替代 l， 以 l G ′ 替代 l G ，转第 ２步。 例： 3 1 4 2 5 33121 10110 01442 22022 14553 5 4 3 2 1 54321 → → → → → ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? x x x x x yyyyy X x Yy T S x 2 x 3 x 4 x5 x 1 y 2 y 3 y 4 y 5 y 1 2 4 1 3 5 0 0 0 0 0 平凡标号及相应的生成子图 G l , G l 的一个匹配 M x 2 x 3 x 4 x5 x 1 y 2 y 3 y 4 y5 y 1 经一次增广路扩张后发现 G l 无完美匹配 , S={x 1, x 3 ,x 4 },N(S)=T={y 2 ,y 3 }。 l α =min{l(x)+l(y)-w(xy)|x∈S,y?T}。 完全二部图的权矩阵 修改标号后，新的标号及其生成子图 G l ， 当前 G l 的一个完美匹配。 1 1 0 0 0 x 2 x 3 x 4 x5 x 1 y 2 y 3 y 4 y5 y 1 2 3 0 3 4 12 习题六 1. 设 M 和 N 是图 G 中两个不交的匹配， 且 |||| NM > 。 证明： 图 G 中必存在两个不交匹配 M′ 和 N′使得： NMNM UU =′′ ， 1|||| ?=′ MM ， 1|||| +=′ NN 。 2．已知工人 54321 ,,,, xxxxx 做工作 54321 ,,,, yyyyy 的效率 ij w 如下： W=( ij w ) = ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 31241 50122 31550 13210 22143 5 4 3 2 1 54321 x x x x x yyyyy . 试给出一种工作效率最大的派工方案。 参考文献 [1] L.Lovasz and M.D. Plummer, Matching Theory, Annals of Discrete Mathematics, Vol.29, 1986. [2] J.E. Hopcroft and R.E. Karp, An 2 5 n algorithm for maximum matching in bipartite graphs, SIAM on Journal of Computing, 2(1973), pp225-231. [3] Nick Mckeown, The iSLIP scheduling algorithm for input-queued switches, IEEE/ACM Transactions on Networking, 7(2)(1999), pp188-201. [4] P. Giaccone, B. Prabhakar, and D. Shah, Randomized scheduling algorithms for high-aggregate bandwidth switches, IEEE Journal on Selected Areas in Communications, 21(4)(2003), pp546-559.