对集的充要条件是,VScX,则N(S)≥|S|,其中N(S)是S中顶点的邻集。 由上述定理可以得出 推论1:若G是k次(k>0)正则2分图,则G有完美对集 所谓k次正则图,即每顶点皆k度的图 由此推论得出下面的婚配定理 定理4每个姑娘都结识k(k≥1)位小伙子,每个小伙子都结识k位姑娘,则每位 姑娘都能和她认识的一个小伙子结婚,并且每位小伙子也能和他认识的一个姑娘结婚。 人员分派问题等实际问题可以化成对集来解决。 人员分派问题:工作人员x1,x2…,xn去做n件工作y1,y2,…,yn,每人适合做其 中一件或几件,问能否每人都有一份适合的工作?如果不能,最多几人可以有适合的工 这个问题的数学模型是:G是二分图,顶点集划分为V(G)=XUY X={x1…,x},={y1,…,yn},当且仅当x适合做工作y时,xy∈E(G),求 G中的最大对集。 解决这个问题可以利用1965年埃德门兹( amends提出的匈牙利算法。 匈牙利算法 (i)从G中任意取定一个初始对集M。 (i)若M把X中的顶点皆许配,停止,M即完美对集;否则取X中未被M许 配的一顶点,记S={l},T=Φ。 (i)若N(S)=T,停止,无完美对集;否则取y∈N(S)-T。 (iv)若y是被M许配的,设y∈M,S=SU{},T=TU{y},转(ⅲi) 否则,取可增广轨P(u,y),令M=(M-E(P)∪(E(P)-M),转(i) 把以上算法稍加修改就能够用来求二分图的最大完美对集 最优分派问题:在人员分派问题中,工作人员适合做的各项工作当中,效益未必 致,我们需要制定一个分派方案,使公司总效益最大。 这个问题的数学模型是:在人员分派问题的模型中,图G的每边加了权 r(xy)≥0,表示x干y,工作的效益,求加权图G上的权最大的完美对集。 解决这个问题可以用库恩一曼克莱斯(Kuhn- Munkres)算法。为此,我们要引入 可行顶点标号与相等子图的概念。 定义若映射l:(G)→R,满足Vx∈X,y∈Y, l(x)+l(y)≥w(x,y), 则称l是二分图G的可行顶点标号。令 E=(xylxyEE(G), 1(x)+l(y)=w(xy)) 称以E为边集的G的生成子图为相等子图,记作G1 可行顶点标号是存在的。例如 l(x)=maxw(xy).x∈X l(y)=0, 定理5G的完美对集即为G的权最大的完美对集。 Kuhn- Munkres算法
-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 算法
(i)选定初始可行顶点标号l,确定G,在G1中选取一个对集M。 (i)若X中顶点皆被M许配,停止,M即G的权最大的完美对集;否则,取G1 中未被M许配的顶点,令S={l,T=Φ (i)若NG(S)→T,转(ⅳ);若N(S)=T,取 a=min(/(x)+1(y)-w(xy)) (y)-a1,∈S ()={v)+a,v∈r l(v),其它 (iv)选NG(S)-7中一顶点y,若y已被M许配,且y∈M,则S=SU{} T=TU{y},转(ⅲ):否则,取G/中一个M可增广轨P(u,y),令 M=(M-E(P)∪(E(P)-M) 转(ⅱi)。 其中N(S)是G1中S的相邻顶点集。 §6 Euler图和 Hamilton图 61基本概念 定义经过G的每条边的迹叫做G的 Euler迹;闭的 Euler迹叫做 Euler回路或E 回路;含 Euler回路的图叫做 Euler图 直观地讲, Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图,即 不重复地行遍所有的边再回到出发点 定理6(i)G是 Euler图的充分必要条件是G连通且每顶点皆偶次。 (ⅱ)G是Eder图的充分必要条件是G连通且G=∪c,C是圈 E(C7)∩E(C)=d≠)。 (ⅲi)G中有 Euler迹的充要条件是G连通且至多有两个奇次点。 定义包含G的每个顶点的轨叫做 Hamilton(哈密顿)轨;闭的 Hamilton轨叫做 Hamilton圈或H圈:含 Hamilton圈的图叫做 Hamilton图。 直观地讲, Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种 图,即不重复地行遍所有的顶点再回到出发点。 62 Euler回路的 Fleury算法 1921年,Feuy给出下面的求 Euler回路的算法 Fleury算法: 1°.Vvo∈V(G),令W=Vo 2°.假设迹W=vev1…eν已经选定,那么按下述方法从E-{e1…,e1}中选取 边 (i)e+和v相关联; 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 相关联；