《图论及其应用ppt19》由会员分享，可在线阅读，更多相关《图论及其应用ppt19（33页珍藏版）》请在金锄头文库上搜索。
1、Email: 图论及其应用任课教师：杨春数学科学学院1本次课主要内容(一)、匈牙利算法(二)、最优匹配算法匈牙利算法与最优匹配算法2(一)、匈牙利算法1、偶图中寻找完美匹配(1) 、问题设G=(X, Y), |X|=|Y|, 在G中求一完美匹配M.(2) 、基本思想从任一初始匹配M0出发，通过寻求一条M0可扩路P，令 M1=M0E(P), 得到比M0更大的匹配M1(近似于迭代思想)。(3) 、M可扩扩路的寻找方法1965年，Edmonds首先提出: 用扎根于M非饱和点u的M 交错树的生长来求M可扩路。3定义1 设G=(X, Y), M是G的匹配，u是M非饱和点。称 树H是G的扎根于点u的M交错
2、树,如果：1) u V(H)； 2) 对任意v V(H), (u, v)路是M交错路 。 x1x2x3x4y2y1y3y4G=(X, Y)x3x2x4y4y3y2扎根 x3 的M交错树扎根于M非饱和点u的M交错树的生长讨论：4假如扎根于M非饱和点u的M交错树为H。它有两种情形 ：情形1 除点u外，H中所有点为M饱和点，且在M上配对；x4ux2y4y3y2扎根 u 的M交错树Hx5情形2 H包含除u外的M非饱和点。x4ux2y4y3y2扎根 u 的M交错树H对于情形1，令S=V(H)X, T=V(H)Y,显然：1) 若N(S)=T, 由于S - u中点与T中点配对，所以有：|T|=|S|-1,
3、于是有： |N(S)| = |S|-1 |S|.由Hall定理，G中不存 在完美匹配；52) 若令y N(S) T, 则在树H中存在点x与y邻接。因为H的所有 点，除u外，均在M下配对。所以，或者x=u，或者x与H的某 一顶点配对，但无论哪种情况，都有xux2y4y3y2扎根 u 的M交错树Hx5yxux2y4y3y2扎根 u 的M交错树Hx5y当然，y可能为M饱和点，也可能为M非饱和点。6若y为M饱和点，可设yz M,则加上顶点y及z和边xy与yz生 长H，得到情形1；xux2y4y3y2扎根 u 的M交错树Hx5yz若y为M非饱和点，加上顶点y和边xy生长H，得到情形2.xux2y4y3y
4、2扎根 u 的M交错树Hx5y7后一情况下找到一条M可扩路，可以对匹配进行一次修改 ，过程的反复进行，最终判定G是否有完美匹配或者求出完美 匹配。根据上面讨论，可以设计求偶图的完美匹配算法。(4) 、偶图完美匹配算法匈牙利算法。设M是初始匹配。H是扎根于M非饱和点u的交错树。 令：S=V(H)X, T=V(H)Y。(a) 、若M饱和X所有顶点，停止。否则，设u为X中M 非饱和顶点，置S=u,T=;(b) 、若N(S)=T, 则G中不存在完美匹配。否则设 y N(S) T.(c ) 若y为M饱和点，且y z M, 置S=Sz, T=Ty, 转(b)。否则，设P为M可扩路，置M1=ME(P)，转转
5、(a).8例1 讨论下图G=(X, Y)是否有完美匹配。x1x2x3x4x5y1y2y3y4y5G=(X, Y)解：取初始匹配 M=x1y2, x2y3。(a) S=x3,T=;x1x2x3x4x5y1y2y3y4y5G=(X, Y)9(b ) N(S)= y2, y3,N(S)T, 取y2 N(S)-T(c) y2为M非饱和点，加上y2和边x3y2生长树H。此时 ，置M=ME(P)=x1y1, x2y3, x3y2x1x2x3x4x5y1y2y3y4y5G=(X, Y)x3y2x1x2x3x4x5y1y2y3y4y5G=(X, Y)10(a) S=x4,T=;x1x2x3x4x5y1y2y3
6、y4y5G=(X, Y)(b ) N(S)= y2, y3,N(S)T, 取y2 N(S)-T(c) y2为M饱和点，y2x3 M。此时，置S=Sx3T=Ty2。(b ) N(S)= y2, y3 T，取y3 N(S)-Tx4y2x311(c) y3为M饱和点，x2y3 M。此时，置S=Sx2T=Ty3。(b ) N(S)= y2, y3 T，取y3 N(S)-Tx1x2x3x4x5y1y2y3y4y5G=(X, Y)(b ) N(S)= y2, y3 =T，所以，G无完美匹配。(5) 、匈牙利算法复杂性分析121) 、最多循环|X|次可以找到完美匹配；2) 、初始匹配最多扩张|X|次可以找到
7、完美匹配；3) 、每次生长树的生长至多2|X|-1次。所以，算法复杂性为O(|X|3),是好算法。2、偶图中寻找最大匹配问题：在一般偶图图上求最大匹配M.分析：使用匈牙利算法求完美匹配时，当在扎根于M 非饱和点u的交错树上有|N(S)|S|时时，由Hall定理，算法 停止。要求出最大匹配，应该继续检查应该继续检查 X-S是否为为空， 如果不为为空，则检查则检查 是否在其上有M非饱饱和点。一直到 所有M非饱饱和点均没有M可扩扩路才停止。13偶图中寻找最大匹配算法：设M是G=(X, Y)的初始匹配。(1) 置S=, T=;(2) 若X-S已经M饱和，停止；否则，设u是X-S中的一 非饱和顶点，置S
8、=Su。(3) 若N(S)=T,转(5)；否则，设y N(S)-T。(4) 若y是M饱和的，设yz M,置S=Sz, T=T y,转(3);否则，存在(u, y)交错路是M可扩路P,置 M=ME(P),转(1).(5) 若X-S=,停止；否则转(2).14(二)、最优匹配算法1 、问题设G=(X, Y)是边赋权完全偶图，且X=x1, x2,xn Y=y1, y2,yn, wij=w(xiyj)。在G中求出一个具有最大 权值的完美匹配。由于Kn,n有n!个不同完美匹配，所以枚举计算量是n!。在匈牙利算法的基础上，Kuhn（1955）与Munkres(1957)提 出了上面问题的好算法。2 、可行
9、顶点标号与相等子图15定义2 设G=(X, Y), 若对任意的x X, y Y,有：称 l 是赋权完全偶图G的可行顶点标号。对于任意的赋权完全偶图G，均存在G的可行顶点标号 。事实上，设：则 l 是G的一个可行顶点标号。16定义3 设 l 是赋权完全偶图G=(X, Y)的可行顶点标号， 令：称Gl = G El为G的对应于l 的相等子图。例如，设如下矩阵是赋权完全偶图G的权值矩阵并注 明了一种可行顶点标号l。0000054213x1x2x3x4x5y1y2y3y4y5G l=(X, Y)17定理 设 l 是赋权完全偶图G=(X, Y)的可行顶点标号， 若相等子图Gl有完美匹配M*,则M*是G的
10、最优匹配。证明：设M*是Gl的完美匹配，则：又设M是G的任一完美匹配，则：所以，w (M*)w (M)。即M*是G的最优优匹配。18根据上面定理，如果找到一种恰当可行顶点标号，使得 对应的相等子图有完美匹配M*,则求出了G的最优匹配。Kuhn采用顶点标号修改策略，找到了求最优匹配好算 法，介绍如下：给一初始顶点标号l ,在Gl中任选一个匹配M。(1) 若X是M饱和的，则M是最优匹配。否则，令u是一 个M非饱和点，置：S=u,T=。(2) 若 ，转(3)。否则，计算：19给出新的可行顶点标号，在新标号下重新开始。(3) 在NGl (S)-T中选择点y。若y是M饱和的，yz M, 则置S=Sz,T
11、=Ty转(2)。否则，设P是Gl中M 可扩路，置M=ME(P),转(1).注：该算法把匈牙利算法用于其中，主要是用来判定 和求完美匹配。20例2，设如下矩阵是赋权完全偶图G的权值矩阵，求出 其最优匹配。解：给出初始可行顶点标号 l 为：000005421321对应的相等子图Gl为：给出初始匹配M为：x1x2x3x4x5y1y2y3y4y5G l=(X, Y)x1x2x3x4x5y1y2y3y4y5G l=(X, Y)22(1) u=x4为M非饱和顶点。置：x1x2x3x4x5y1y2y3y4y5G l=(X, Y)(2)(3) 取：y2为饱和顶点，y2x1 M,于是：(2) (3) 取：y3为
12、饱和顶点，y3x3 M,于是：23x1x2x3x4x5y1y2y3y4y5G l=(X, Y)(2) 于是修改标号：由 得新标号为： 0110043203x1x2x3x4x5y1y2y3y4y5G l=(X, Y)24继续使用算法后得：x1x2x3x4x5y1y2y3y4y5G l=(X, Y)最优匹配权值为14.例3 证明：K6n-2有一个3因子分解。证明：K6n-2= K 2(3n-1) , 所以，可以分解为6n-3个边不重 的1因子之和。而任意3个1因子可以并成一个3因子。所 以，共可以并成2n-1个3因子。即K6n-2可以分解为2n-1个3 因子的和。25例4 证明：对n1,K4n+1
13、有一个4因子分解。证明：K4n+1= K 2(2n)+1 , 所以，可以分解为2n个边不重 的2因子之和。而任意2个2因子可以并成一个4因子。所 以，共可以并成n个4因子。即K4n+1可以分解为n个4因子 的和。例5 设H是有限群，K是H的子群。证明：存在元素 h1,h2,hn H,使得h1K, h2K, , hnK都是K的左陪集。而 Kh1, Kh2, , Khn都是K的右陪集。注: (1)上面结论是群论学家Hall的一个结论。群论是近 世代数的重要组成部分。在数学、计算机科学、理论物 理学(量子场论)中都有重要应用。是数学领域里最引人关 注的方向和主流研究方向之一。创立者伽罗瓦。26(2)
14、 伽罗瓦 (1811 -1832) 中学时受到数学老师里沙的影 响而对数学产生极大兴趣。里沙对教学工作十分负责，且 具有很高数学才能，但把精力耗在了学生身上，欣慰的是 培养了好几位欧洲杰出数学家。中学时的伽罗瓦 在里沙帮 助下创立了群论。群论是19世纪最突出的数学成就。在法国历史上著名的1830年的“七月革命”中 ，伽罗瓦两 次入狱，成为坚强斗士。1832年5月，21岁的他因为反动 派设下的爱情圈套，被迫决斗至死。这是他犯下的草率的 错误。27证明：由陪集的性质：H中的任意两个左(右)陪集,要 么相等，要么没有共同元素。所以H可按某子群的左(右) 陪集，划分为左(右)陪集族。如果K是H的子群，
15、则aK或 者Kb的元素个数等于K中元素个数。设|K|=k。且假设设子群K在群H中的指数为为n。我们们构 造偶图图G=(X, Y)如下：X表示H关于K的左陪集族，Y表示H关于K的右陪集族 。对于x X, y Y, x与y间连接 l 条边，当且仅当左陪集 x和右陪集y有l个共同元素。显然G是k正则偶图，于是存在完美匹配M。 |M|=n在M中的边ei的两端点的陪集中选取共同元素hi, 则这 些元素为所求。(1in）。28匹配在矩阵中的应用1、矩阵与偶图设A=(aij)是n阶方阵。构造偶图G=(X, Y)如下：X表示行集合，Y表示列集合。X中元素xi与Y中元素yj 连线，当且仅当aij0y1y2y3y4y5x1x3x2x4x5x1x2x3x4x5y1y2y3y4y5G w=(X, Y)292、下面研究detA和GA=(X, Y)之间关系若|S|=n, 则则在A中存在n行，这这n行中至多有n-1列元非 零，而其余的-n+1列中每个元素为为零。即得到A中有一 个 零子阵阵。30于是有如下定理：31作业P117-118 习题4 ： 1332Thank You !33
