对集的充要条件是，ScX,则N(S)S引，其中N(S)是S中顶点的邻集。 由上述定理可以得出： 推论1：若G是k次(k>0)正则2分图，则G有完美对集。 所谓k次正则图，即每顶点皆k度的图。 由此推论得出下面的婚配定理： 定理4每个姑娘都结识k(k≥1)位小伙子，每个小伙子都结识k位姑娘，则每位 姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。 人员分派问题等实际问题可以化成对集来解决。 人员分派问题：工作人员x,x2 去做n件工作，乃 ,每人话合做其 作钱几作，能香每人郑有一合适合的工作？如果不能多几人可以有适合的 这个问题的数学模型是：G是二分图，顶点集划分为V(G)=XUY X={x,.,x},Y={,.,yn},当且仅当x,适合做工作y,时，xy,∈E(G),求 G中的最大对集」 解决这个问题可以利用1965年埃德门兹(Edmonds)提出的牙利算法。 饲牙利算法： (i)从G中任意取定一个初始对集M ()若M把X中的顶点皆许配，停止，（即完美对集：否则叫取X中未被（许 配的一顶点u,记S={u,T=中。 (i)若N(S)=T,停止，无完美对集：否则取v∈N(S)-T (iw)若y是被M许配的，设zeM,S=SU{,T=TU以，转(i) 否则，取可增广轨P(u,y),令M=(M-E(P)U(E(P)-M,转(i)。 把以上算法相加修改就能够用来求二分图的最大完美对集。 最优分派问题：在人员分派问题中，工作人员适合做的各项工作当中，效益未必 致，我们需要制 个分派方案，使公司总效益最力 这个问题的数学模型是：在人员分派问题的模型中，图G的每边加了权 (x,y,)≥0，表示x,干y,工作的效益，求加权图G上的权最大的完美对集。 解决这个问题可以用库恩一曼克莱斯(Kuhn-Munkres)算法。为此，我们要引入 可行顶点标号与相等子图的概念。 定义若映射l:V(G)→R,满足x∈X,yeY, 1x)+10)2w(, 则称1是二分图G的可行顶点标号 E=xy xyEE(G)(x)+(y)=w(xy) 称以E,为边集的G的生成子图为相等子图，记作G, 可行顶点标号是存在的。例如 I(x)=maxw(xy),xeX: 1（y)=0, y∈Y。 定理5G,的完美对集即为G的权最大的完美对集。 Kuhn-Munkres算法 -83
-83- 对集的充要条件是，∀S ⊂ X ，则| N(S) |≥| S |，其中 N(S) 是 S 中顶点的邻集。 由上述定理可以得出： 推论 1：若G 是k 次（k > 0) 正则 2 分图，则G 有完美对集。 所谓k 次正则图，即每顶点皆k 度的图。 由此推论得出下面的婚配定理： 定理 4 每个姑娘都结识k(k ≥ 1) 位小伙子，每个小伙子都结识k 位姑娘，则每位 姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。 人员分派问题等实际问题可以化成对集来解决。 人员分派问题：工作人员 n x , x , , x 1 2 L 去做n 件工作 n y , y , , y 1 2 L ，每人适合做其 中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工 作？ 这个问题的数学模型是： G 是二分图，顶点集划分为 V (G) = X UY ， { , , } 1 n X = x L x ， { , , } 1 n Y = y L y ，当且仅当 i x 适合做工作 j y 时，x y E(G) i j ∈ ，求 G 中的最大对集。 解决这个问题可以利用 1965 年埃德门兹(Edmonds)提出的匈牙利算法。 匈牙利算法： （i）从G 中任意取定一个初始对集 M 。 （ii）若 M 把 X 中的顶点皆许配，停止，M 即完美对集；否则取 X 中未被 M 许 配的一顶点u ，记 S = {u}，T = Φ 。 （iii）若 N(S) = T ，停止，无完美对集；否则取 y ∈ N(S) − T 。 （iv）若 y 是被 M 许配的，设 yz ∈ M ， S = S U{z}，T = T U{y}，转（iii）； 否则，取可增广轨 P(u, y) ，令 M = (M − E(P)) U(E(P) − M ) ，转（ii）。 把以上算法稍加修改就能够用来求二分图的最大完美对集。 最优分派问题：在人员分派问题中，工作人员适合做的各项工作当中，效益未必一 致，我们需要制定一个分派方案，使公司总效益最大。 这个问题的数学模型是：在人员分派问题的模型中，图 G 的每边加了权 w(xi y j) ≥ 0 ，表示 i x 干 j y 工作的效益，求加权图G 上的权最大的完美对集。 解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres）算法。为此，我们要引入 可行顶点标号与相等子图的概念。 定义 若映射l :V(G) → R ，满足∀x ∈ X , y ∈Y ， l(x) + l( y) ≥ w(x, y) ， 则称l 是二分图G 的可行顶点标号。令 E {xy | xy E(G),l(x) l( y) w(xy)} l = ∈ + = ， 称以 El 为边集的G 的生成子图为相等子图，记作Gl 。 可行顶点标号是存在的。例如 l(x) max w(xy), x X; y Y = ∈ ∈ l( y) = 0, y ∈Y 。 定理 5 Gl 的完美对集即为G 的权最大的完美对集。 Kuhn-Munkres 算法
()选定初始可行顶点标号1，确定G,在G,中选取一个对集M。 ()若X中顶点皆被M许配，停止，M即G的权最大的完美对集：否则，取G 中未被M许配的顶点u,令S={,T=中。 im若N。(S)pT,转(iv):若N。(S)=T,取 a=min ((x)+)-w(xy). [I(v)-a.vES I(v)=(v)+a,vET, 其它 1=1,G=G1 (iw)选NG,(S)-T中一顶点y,若y已被M许配，且zeM,则S=SU{, T=TU{以，转(m):否则，取G,中一个M可增广轨P(，)，令 M=(M-E(P))U(E(P)-M), 转(ii) 其中N。(S)是G,中S的相邻顶点集。 s6 Euler图和Hamilton图 61其本概念 定义经过G的每条边的迹叫做G的Euler迹：闭的Euler迹叫做Euler回路或E 回路：含Euler回路的图叫做Euler图。 直观地讲，Eule图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即 不重复地行遍所有的边再回到出发点 定理6()G是Euler图的充分必要条件是G连通且每顶点皆偶次。 (i)G是Euler图的充分必要条件是G连通且G=UC,C,是圈， E(C,)nE(C)=Di≠). (ii)G中有Euler迹的充要条件是G连通且至多有两个奇次点。 定义包含G的每个顶点的轨叫做Hamilton(哈密顿)轨：闭的Hamilton轨叫做 Hamilton圈或H圈：含Hamilton图的图叫做Hamilton图。 直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种 图，即不重复地行遍所有的项点再回到出发点。 leury给出下面的求Euler回路的算法 Fleury算 1°v。∈V(G),令W。='o· 2”假设迹W,=9y.e,y已经选定，那么按下述方法从E-{,.,e,}中选取 边e1: (i)e和y,相关联 -84
-84- （i）选定初始可行顶点标号l ，确定Gl ，在Gl 中选取一个对集 M 。 （ii）若 X 中顶点皆被 M 许配，停止，M 即G 的权最大的完美对集；否则，取Gl 中未被 M 许配的顶点u ，令 S = {u}， T = Φ 。 (iii)若 N S T Gl ( ) ⊃ ，转（iv）；若 N S T Gl ( ) = ，取 min { ( ) ( ) ( )} , l x l y w xy x S y T l = + − ∈ ∉ α ， ⎪ ⎩ ⎪ ⎨ ⎧ + ∈ − ∈ = ( ), 其它 ( ) , ( ) , ( ) l v l v v T l v v S l v l l α α ， l = l ，Gl Gl = 。 （iv）选 N S T Gl ( ) − 中一顶点 y ，若 y 已被 M 许配，且 yz ∈ M ，则 S = S U{z}， T = T U{y}，转（iii）；否则，取Gl 中一个 M 可增广轨 P(u, y) ，令 M = (M − E(P)) U(E(P) − M ) ， 转（ii）。 其中 N (S) Gl 是Gl 中 S 的相邻顶点集。 §6 Euler 图和 Hamilton 图 6.1 基本概念 定义 经过G 的每条边的迹叫做G 的 Euler 迹；闭的 Euler 迹叫做 Euler 回路或 E 回路；含 Euler 回路的图叫做 Euler 图。 直观地讲，Euler 图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即 不重复地行遍所有的边再回到出发点。 定理 6 （i）G 是 Euler 图的充分必要条件是G 连通且每顶点皆偶次。 （ ii ） G 是 Euler 图的充分必要条件是 G 连通且 U d i G Ci =1 = ， Ci 是圈， E(C ) E(C ) (i j) i I j = Φ ≠ 。 （iii）G 中有 Euler 迹的充要条件是G 连通且至多有两个奇次点。 定义 包含G 的每个顶点的轨叫做 Hamilton(哈密顿)轨；闭的 Hamilton 轨叫做 Hamilton 圈或 H 圈；含 Hamilton 圈的图叫做 Hamilton 图。 直观地讲，Hamilton 图就是从一顶点出发每顶点恰通过一次能回到出发点的那种 图，即不重复地行遍所有的顶点再回到出发点。 6.2 Euler 回路的 Fleury 算法 1921 年，Fleury 给出下面的求 Euler 回路的算法。 Fleury 算法： 1o . ( ) ∀v0 ∈V G ，令 0 0 W = v 。 2o . 假设迹 i i i W v e v Le v = 0 1 1 已经选定，那么按下述方法从 { , , } 1 i E − e L e 中选取 边 i+1 e ： （i） i+1 e 和 i v 相关联；