第六节匹配、欧拉及哈密尔顿问题

《第六节匹配、欧拉及哈密尔顿问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、第六节匹配问题、欧拉环游和哈密尔顿环游6.1匹配问题定义若MuE(G),耳与◎无公共端点(心j),则称M为图G的一个对集；M中的一条边的两个端点叫做在对集M中相配；M中的端点称为被M许配;G中每个顶点皆被M许配时,M称为完美对集;G中已无使IMbIMI的对集W,则M称为最大对集；若G中有一轨，其边交替地在对集M内外出现，则称此轨为M的交错轨,交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。若把可增广轨上在M外的边纳入对集，把M内的边从对集中删除，则被许配的顶点数增加2,对集中的“对儿”增加一个。1957年，贝尔热

2、(Berge)得到最大对集的充要条件：定理2M是图G中的最大对集当且仅当G中无M可增广轨。1935年，霍尔(Hall)得到下面的许配定理：定理3G为二分图，X与Y是顶点集的划分，G中存在把X屮顶点皆许配的对集的充要条件是,/SuX,贝i」IN(S)ASI,其中N(S)是S中顶点的邻集。由上述定理可以得岀：推论1：若G是k(R〉0)正则2分图，则G有完美对集。所谓£止则图，即每顶点皆£度的图。山此推论得出下面的婚配定理：定理4每个姑娘都结识k(k>l)位小伙子，每个小伙子都结识k位姑娘，则每位姑娘都能和她认识的一个小

3、伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。人员分派问题等实际问题町以化成对集来解决。人员分派问题：工作人员“,兀2「・，£去做〃件工作…,儿，每人适合做其中一件或儿件，问能否每人都有一份适合的工作？如果不能，最多儿人可以有适合的工作？这个问题的数学模型是：G是二分图，顶点集划分为V(G)=XUY，X严｛无,,齐-｛儿，…，儿｝，当且仅当小适合做工作X时，xj;€E(G),求G中的最人对集。解决这个问题可以利用1965年埃德门兹(Edmonds)捉出的匈牙利算法。匈牙利算法：(i)从G中任意取定一个初始对集M

4、o(ii)若M把X中的顶点皆许配，停止，M即完美对集；否则取X中未被M许配的一顶点％,记S=｛u｝,T=①。(iii)若N(S)=T,停止，无完美对集；否则取ywN(S)_T。(i)若y是被M许配的,设yzwM,S=SU{z},T=TJ{y}t转(iii)；否则,取可增广轨P(u,y),令M=(M-E(P))U(E(P)—M),转(ii)。把以上算法稍加修改就能够用來求二分图的最大対集。最优分派问题：在人员分派问题屮，工作人员适合做的各项工作当屮，效益未必-•致,我们需要制定一个分派方案，使公司总效益最人。这个问题

5、的数学模型是：在人员分派问题的模型中，图G的每边加了权vv(x,y.)>0,表示兀・干儿工作的效益，求加权图G上的权最大的完美对集。解决这个问题可以用库恩一曼克莱斯(KuhmMunkres)算法。为此，我们要引入可行顶点标号与相等子图的概念。定义若映射1:V(G)tR，满足l(x)+l(y)>w(x9y)f则称/是二分图G的可行顶点标号。令Ei={xyxyeE(G),/(x)+l(y)=w(xy)},称以E为边集的G的生成了图为相等了图，记作G,o可行顶点标号是存在的。例如/(x)=maxvv(xy),xeX;ye

6、K心)=0,yeY.定理5G/的完美对集即为G的权最大的完美对集。Kuhn-Munkres算法(i)选定初始可行顶点标号/,确定在G,中选取一个对集(ii)若X中顶点皆被M许配，停止，M即G的权最大的完美对集；否则，取G,中未被M许配的顶点比，令S={u},7=①。(iii)若NgS)二T,转(iv)；若N('S)=T,取a.=minIZ(x)+Z(y)-w(xy)},xeS.yeT/(V)-VGS/(v)=

7、U{z},T=TU{y}，转(iii);否则，取G,中一个M可增广轨P(u,y),令M=(M-E(P))U(E(P)-M),转(ii)o其中f(S)是G,中S的相邻顶点集。6.2Euler图和Hamilton图定义经过G的每条边的迹叫做G的Eulei•迹；闭的Euler迹叫做Euler回路或£*回路;含Euler回路的图叫做Euler图。直观地讲，Eulei■图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。定理7(i)G是Euler图的充分必要条件是G连通目.每顶点皆偶次。d

8、(ii)G是Euler图的充分必要条件是G连通H.G=JCi,G是圈，/=1E(C,.)n£(C.)=①(心力。(iii)G中冇Euler迹的充要条件是G连通R至多冇两个奇次点。定义包含G的每个顶点的轨叫做Hamilton(哈密顿)轨;闭的Hamilton轨叫做Hamilton圈或//圈；含Hamilton圈的图叫做Hamilton图。直观地