?M?? ?K? 。
引理5.3 设M与K分别为G中的匹配与覆盖，如果 ?M? = ?K?
则M为最大匹配，K为最小覆盖。 （证明：略）
*
*
~?M?=?K? 。
证明：设G的2-划分为（X，Y）。记
*
U = { u ? X ? u为M-不饱和的 }
*
Z = { v ? V ? ? M-交错（u，v）-路 } S = Z?X， T = Z?Y 。
**
与定理5.2之证明类似，我们有： T中每顶点都是M-饱和的；T与S\\U中顶点在M下相匹配；N(S) = T。 记
~定理5.3 (Konig?s theorem,1931) 设 M，K分别为偶图G的最大匹配和最小覆盖，则
*
~~K= (X\\S) ? T 。
~~易见，G中每边至少有一端在K 中，即K 为G 的覆盖（不然，与N(S) = T相矛盾）。又，显然，
~*
?M?=?K? 。
再由引理5.3知为最小覆盖。 ? 习题
5.2.1 证明：一个5?5方格棋盘去掉其对角上的两个1?1方格之后，不可能用1?2长方格恰好添满。
5.2.2 (a) 证明：偶图G有完美匹配当且仅当对 所有S ? V 都有 ?N(S)?? ?S? 。 (b) 举例说明：去掉偶图这个条件之后，上述不成立。 5.2.3 对于k > 0，证明： (a) 每个k-正则偶图都是1-可因子分解的；
*
(b) 每个2k-正则图都是2-可因子分解的 。 5.2.4 设A1 ，A2 ，??，An 是某集S的子集。 族（A1 ，A2 ，??，An）的一个相异代表系是指S的一个子集{ a1 ，a2 ，??，an }使 ai ? Ai （1? i ? n），且 ai ? aj （当i?j）。证明：（A1 ，A2 ，??，An）有一个相异代表系 当且仅当
?
?A?? ?J? ? J ? {1,2,...,n} 。
ii?J 5.2.5 矩阵的一行或一列统称一条线。证明：一（0,1)-矩阵中 ，含所有1元素的线的最小条数 = 两两都不在相同线上的1元素的最大个数。
5.2.6 (a) 证明：Hall定理的一个推广：偶图G =（X,Y; E) 的最大匹配的边数是 ?X? - max{ ?S?-?N(S)? } 。
S?X (b) 试证：若G 为简单偶图，且?X?=?Y?=n 及 ? > (k-1)n ，则G有边数为k的匹配。
*
5.2.7 由Konig定理推导Hall定理。
*
5.2.8 若非负实数矩阵Q的每行元素之和均为1，每列元素之和也均为1，则称Q为双随机矩阵。称一矩阵为置换矩阵如果它是每行和每列均恰只有一个1元素的 （0，1）矩阵（∴是双随机的）。证明：
(a) 每个双随机矩阵一定是个方阵； (b) 每个双随机矩阵Q都可表为置换矩阵的凸线性组合，即 Q = c1 P1 +c2 P2 +??+ck Pk 。
其中每个Pi都是置换矩阵，每个ci都是非负实数，且
?ci?1ki?1 。
5.2.9 若偶图G=(X,Y,E)中，X中每顶点的度?Y中每顶点的度，则G有使X每顶点都饱和的匹配。
*
5.2.10 设偶图G=(X,Y,E)中，Y?为匹配M在Y中的端点集，则存在G的最大匹配M，其端点集包含Y?。
26
完美匹配
称H为G的奇分支（odd component） ? H为G的分支，且其顶点数为奇数。 称H为G的偶分支（even component） ? ??。 记 o(G) = G中奇分支数。
定理5.4 ( Tutte,1947) G有完美匹配
? o(G-S) ? ?S? ? S ? V (*) 证明：（Lavasz证法）只要对简单图情形加以证明即可。 ? ： 设G有完美匹配M。对任S ? V，令 G1 ，??，Gn 为G-S中的奇分支。因每个Gi的顶点数都是奇数，每个Gi中至少 有一顶点u i 与S中一顶点vi 在M 下相匹配。从而
o(G-S) = n = ?{v1 ，??，vn}? ? ?S? 。
*
? ： 反证。假设存在图G 满足条件（*），但不含完美匹配。令G 为G的不含完美匹配的极大生
*
成母图。由于G-S是G-S的生成子图，
*
o(G-S) ? o(G-S) ? ?S? ? S ? V 。 ***
即G满足条件（*），又，上式中令S=?得o(G)=0，因此 ?(G)=偶数。 令
U?{v?V(G*)dG*(v)???1?。
因G不含完美匹配，U ? V。
*
断言 G-S是一些完全图的不相交并。
**
从而，由于 o(G-U) ? ?U? ， G-U中至多有?U?个奇分支。于是，由断言易见， **
G 中有完美匹配，这与G 之假设矛盾。
*
来证断言 反证。假设G-U有一分支不是完全图，则其中一定存在3个顶点x，y，z使
**
xy, yz ? E(G) ， 而 xz?E(G)
**
又，因 y ? U，一定存在 w ?V(G-U) 使 yw ? E(G)。 令
**
M1 与 M2 分别为 G+xz 与 G+yw中的完美匹配。
*
考虑 G+{xz，yw} 中 M1?M2 的边导出子图 H 。显然，H中顶点的度都是2，因而H是一些圈的不相交并。且每圈都是偶圈，由M1 与M2 的边交错组成。
情况1 xz与yw不在H的同一圈中：
*
设yw在圈C上，则C中所有M1 边及C外所有M2 边一起构成G 的一个完美匹配，矛盾。 情况2 xz与yw同在H的某一圈C上：
不妨设x，y，w，z以这顺序出现于C上。这时，C的yw??z节中的所有M1 边，及不在
*
该节中的所有M2 边，以及边yz ，一起构成G 的一个完美匹配，矛盾。?
推论5.4 (Peterson,1891) 每一不含割边的3-正则图都有一完美匹配。
证明：对任S ? V，令 G1 ，??，Gn 为G-S中的所有奇分支。记mi 为一端在Gi中而另一端在S中的边数。则
mi?v?V(Gi)?d(v)?2?(G)?3?(G)?2?(G)?奇数。
iii但G中无割边，因此mi ? 3。从而
3?S?=
?d(v)??mv?Si?1ni?3n 。
∴ ?S? ? n = o(G-S) ? S ? V。
故由定理5.4，G有完美匹配。 ?
习题
*
5.3.1 用Tutte定理推导Hall定理。
5.3.2 推广推论5.4：若G是（k-1）边连通的k-正则图，且? 是偶数，则G有完美匹配。 5.3.3 设G为一树，证明： G有完美匹配 ? o(G-v) = 1 ? v ? V 。
27
*
5.3.4 证明Tutte定理的推广： G的最大匹配的边数 = (? -d)/2 ，其中 d?max{o(G?S)?S} （C.Berge)
S?V
人员分派问题
问题 n个工人x1 ，??，xn 及n个工作y1 ，??，yn ，已知每个工人都胜任一些工作。能否使每个工人都分派到一件他所胜任的工作？（ （the personnel）assignment prob.)
解 在偶图G=(X,Y,E),?X?=?Y?, 中求出其完美匹配（若存在的话）。 Hungarian method (Edmonds,1965) 以任一匹配M作为开始。（可取M=?）
① 若M饱和X的每个顶点，停止（M为完美匹配）。否则，取X中M-不饱和顶点u， S?{u}，T?? 。
② 若N(S)?T,转到③；否则，N(S)=T,停止（无完美匹配）。 ③ 取 y ? N(S)\\T 。若y为M-饱和的，设 yz ? M ，则 S?S?{z} ， T?T?{y} ， 回到②；否则，存在M-可扩路P。 M?M?E(P) ， 并回到① 。
注1 算法用生长“以u为根的M-交错树”的方法 ，来系统地搜索M-可扩路。树中除u外都是M-饱和的，直到碰到第一个 M-不饱和的顶点时，即得一M-可扩路。当树不能再生长下去时，即为N(S)=T之时。
注2 本算法是个‘好’算法： 从一个M到下一个，至多进行?X?次搜索运算；M至多扩大?X?次 。
习题
5.4.1 试述如何利用Hungarian算法求偶图的最大匹配。
Optimal assignment problem
问题 求赋权图G = Kn，n 的最大权匹配。
称l为（feasible vertex labelling)（f.v.l.) ? l为V上的实函数，且满足：
l(x)+l(y) ? w(xy) ? x ? X， y ? Y 。
w(xy)}?l(x)?max{y?Y例。 下面是一可行顶点标号： ?l(y)?0?记
x?Xy?Y
El?xy?El(x)?l(y)?w(xy)??
Gl (相等子图，equality subgraph）
? 以El为边集的G的生成子图。
**定理5.5 设偶图G的可行顶点标号l使Gl 包含一完美匹配M，则M是G的最优匹配。 证明：显然，M也是G的完美匹配，且
*w(M*)?e?M*?w(e)??l(v) 。
v?V但对G的任一完美匹配M有
28
*w(M)?因此w(M)? w(M)，即M是G的最优匹配。 ?
下面是求最优匹配算法的基本思想 ： 任取一f.v.l. l作为开始。定Gl ，并在Gl 上任取一匹配M作为开始的匹配。用Hungarian算法在Gl 上找完美匹配。若找到，它就是G的最优匹配；否则Hungarian算法停止于某匹配M?（不是完美匹配）及一M?交错树H，它不能再“生长”。将l适当修改成新的f.v.l. l：使G~仍包含M?及H，且H在G~中又可继续“生长”。重复上述过程。 ll
Kuhn-Munker algorithm （1955，1957；Edmonds改写（1967））
以任f.v.l. l作为开始。定Gl ，并在Gl 上任取一匹配M作为开始的匹配。 ① 若M饱和X的每个顶点，则M为最优匹配，停止；否则，任取一M-不饱和顶点u， S?{u}， T?? 。
② 若NGl(S)? T，转到③；否则，NGl(S)=T。计算
e?M*?w(e)??l(v) 。
v?V~
l(x)?l(y)?w(xy)} ?l = min{x?S~y?T及f.v.l. l ：
v?S?l(v)??l~? l??l(v)??lv?T
?l(v)其它?~ l? l ， Gl ? G~ 。 l
③ 选取 y?NGl(S)\\T，若y为M-饱和的，则存在 yx?M ， 作
S??S?{x}， T?T?{y}，
并转到② ；否则，令P为Gl中的M-可扩-(u,y)路， M?M?E(P) ， 并转到① 。
2
注1 算法中每计算一次新的Gl的计算量为O(?)；在找到M-可扩路之前，至多进行 ?X?次 搜索（每次可能作一次新的Gl的计算）；而初始匹配M至多扩大?X?次。因此是个‘好’算法（计算复
4
杂性为O(?) )
注2 本算法也可用于解人员分派问题。
习题
5.5.1 所谓n×n矩阵的一条对角线是指它的任n个两两不同行、不同列元素的集合。对角线的权是指它的n个元素的和。试找出下列矩阵的最小权对角线：
?4?7??8??6??4565658512137107910911?4??6? （答：权=30） ?7?8??
29
边着色 边色数
前提 本章只讨论无环图。
k-边着色（k-edge colouring）C
? k种色在图G的边集上的一种分配。 ? C是E(G)的一个k-划分，即 C =（E1 ，。。。，Ek） （注：允许Ei=? ） 边着色C是正常的 ? 每个Ei都是G的一个匹配。 G为k-边可着色的（k-edge colurable）
? G有一正常k-边着色。
? 存在E(G)的一个k-划分 C =（E1 ，，使每个Ei 都 。。。，Ek） 是G的一个匹配。 （注：允许Ei=? ）
（显然，G为k-边可着色的 ? G为l-边可着色的 （l ? k） ）
G的边色数（edge chromatic number） ??(G) = min{ k ? G为k-边可着色的} G为k-边色的（k-edge chromatic） ? ??(G) = k。
例。 n个人举行一些两两会谈，每次会谈用一个单元时间。问最少要多少单元时间，才能安排完所有会谈？
例。Peterson图有 ?? = 4。 显然， ?? ? ? 。
称色i表现（rrepresented）于顶点v
? 与v相关联的某一边有色i。
引理6.1.1 设连通图G不是奇圈，则G有一2-边着色，使该二色表现于G的每个 度? 2的顶点。
证明：不妨设G为非平凡的。 (A) 若G为Euler图：
① 若G 为一圈： 则G为偶圈，从而G的一个正常2-边着色满足要求。 ② 若G不是个圈：则一定存在顶点v0 ，使d(v0)? 4 (∵Euler图每个顶点的度均为偶数）。 令 v0 e1 v1 e2 。= v0 ）。令 E1 与 E2 分别为Euler环游中下标为奇数与偶。。e? v? 为G一的Euler环游 （ v?
数的边子集。则G 的2-边着色 C=（E1，E2）满足要求。
(B) 若G为非Euler环游 ：往G中加一新顶点v0 ，并将v0 与G中每个度为奇数顶点都用一新边连起来，得图G? 。显然，G?为一Euler图 。令v0 e1 v1 e2 。v? （ v? = v0 ）为G的一Euler。。e? 环游 。与(A)②一样定义 C =（E1，E2），易见
C? = ( E1 ? E，E2 ? E）
满足要求。 ?
记号 c(v) = 边着色C表现于v的不同颜色数。 显然， c(v) ? d(v) ? v ? V 。
C为正常边着色 ? c(v) = d(v) ? v ? V 。
称G的k-边着色C? 为其k-边着色C的一个改进 ?
?c'(v)??c(v) 。
v?Vv?VC为最优k-边着色（optimal k-edge colouring） ? C不能再改进 。
30