1、1 1第六章 离散模型6.1 层次分析法层次分析法6.2 图论模型图论模型2 2 一般地说，确定性离散模型包括的范围很广，除差分方程模型外，用层次分析法、图论、对策论、网络流等数学工具都可以建立离散模型.本章选择涉及数学知识不太深，并在实际中应用较广的层次分析法和图论法进行详细分析.3 3层次分析法(AnalyticHierarchyProcess，简称AHP)是美国运筹学家T.L.Saaty教授于20世纪70年代初期提出的一种多准则决策方法.它是对一些较为复杂、较为模糊的问题作出决策的简易方法，特别适用于那些难于完全定量分析的问题.6.1 层次分析法层次分析法4 46.1.1 层次分析法的基
2、本原理与步骤层次分析法的基本原理与步骤人们在进行社会的、经济的以及科学管理领域问题的系统分析中，面临的常常是一个由相互关联、相互制约的众多因素构成的复杂而又缺少定量数据的系统.层次分析法为这类问题的决策和排序提供了一种简洁而实用的建模方法.运用层次分析法建模，大体上可按下面四个步骤进行：(1)建立递阶层次结构模型；(2)构造出各层次中的所有判断矩阵；(3)层次单排序及一致性检验；(4)层次总排序及一致性检验.5 5下面分别说明这四个步骤的实现过程.1.递阶层次结构的建立与特点递阶层次结构的建立与特点应用AHP分析决策问题时，首先要把问题条理化、层次化，构造出一个有层次的结构模型.在这个模型下，
3、复杂问题被分解为元素的组成部分，这些元素又按其属性及关系形成若干层次.上一层次的元素作为准则对下一层次的有关元素起支配作用.这些层次可以分为三类：最高层、中间层和最低层.最高层：这一层次中只有一个元素，一般它是分析问题的预定目标或理想结果，因此也称为目标层.6 6中间层：这一层次中包含了为实现目标所涉及的中间环节，它可以由若干个层次组成，包括所需考虑的准则、子准则，因此也称为准则层.最低层：这一层次包括了为实现目标可供选择的各种措施、决策方案等，因此也称为措施层或方案层.递阶层次结构中的层次数与问题的复杂程度及需要分析的详尽程度有关，一般地，层次数不受限制.每一层次中各元素所支配的元素一般不超
4、过9个.这是因为支配的元素过多会给两两比较判断带来困难.下面结合一个实例来说明递阶层次结构的建立.7 7例例1 假期旅游有P1、P2和P3共3个旅游胜地供人们选择，试确定一个最佳地点.在此问题中，人们会根据诸如景色、费用、居住、饮食和旅途条件等一些准则去反复比较3个候选地点.可以建立如图6-1所示的层次结构模型.8 8图 6-19 92.构造判断矩阵构造判断矩阵层次结构反映了因素之间的关系，但准则层中的各准则在目标衡量中所占的比重并不一定相同，在决策者的心目中，它们各占有一定的比例.在确定影响某因素的诸因子在该因素中所占的比重时，遇到的主要困难是这些比重常常不易定量化.此外，当影响某因素的因子
5、较多，直接考虑各因子对该因素有多大程度的影响时，常常会因考虑不周全、顾此失彼而使决策者提出与实际认为的重要性程度不相一致的数据，甚至有可能提出一组隐含矛盾的数据.10 10设现在要比较n个因子Xx1，xn对某因素Z的影响大小，怎样比较才能提供可信的数据呢？Saaty等人建议可以采取对因子进行两两比较，建立成对比较矩阵.即每次取两个因子xi和xj，以aij表示xi和xj对Z的影响大小之比，全部比较结果用矩阵A(aij)nn表示，称A为ZX之间的成对比较判断矩阵(简称判断矩阵).容易看出，若xi与xj对Z的影响之比为aij，则xj与xi对Z的影响之比应为aji1aij.11 11定义6.1 若矩阵
6、A(aij)nn满足：aij0；aji1aij(i，j1，2，n)，则称矩阵A(aij)nn为正互反矩阵(易见aii1(i1，n).关于如何确定aij的值，Saaty等建议引用数字19及其倒数作为标度.表6-1列出了19标度的含义.12 12表表 6-113 13从心理学观点来看，分级太多会超越人们的判断能力，既增加了作判断的难度，又容易因此而提供虚假数据.Saaty等人还用实验方法比较了在各种不同标度下人们判断结果的正确性.实验结果也表明，采用19标度最为合适.最后应该指出，一般地，作n(n1)/2次两两判断是必要的.有人认为把所有元素都和某个元素比较，即只作n1个比较就可以了.这种做法的弊
7、病在于，任何一个判断的失误均可导致不合理的排序，而个别判断的失误对于难以定量的系统往往是难以避免的.进行n(n1)/2次比较可以提供更多的信息，通过各种不同角度的反复比较，从而导出一个合理的排序.14 143.层次单排序及一致性检验层次单排序及一致性检验判断矩阵A对应于最大特征值max的特征向量W，经归一化后即为同一层次相应因素对于上一层次某因素相对重要性的排序权值，这一过程称为层次单排序.上述构造成对比较判断矩阵的方法虽能减少其它因素的干扰，较客观地反映出一对因子影响力的差别，但综合全部比较结果时，其中难免包含一定程度的非一致性.如果比较结果是前后完全一致的，则矩阵A的元素还应当满足：aij
8、ajkaik(6.1.1)nkji,2,1,15 15 定义定义6.2 满足关系式(6.1.1)的正互反矩阵称为一致矩阵.需要检验构造出来的(正互反)判断矩阵A是否严重地非一致，以便确定是否接受A.定理定理6.1 正互反矩阵A的最大特征根max必为正实数，其对应特征向量的所有分量均为正实数；A的其余特征值的模均严格小于max.16 16定理定理6.2 若A为一致矩阵，则A必为正互反矩阵；A的转置矩阵AT也是一致矩阵；A的任意两行成比例，比例因子大于零，从而R(A)1(同样，A的任意两列也成比例)；A的最大特征值maxn，其中n为矩阵A的阶，A的其余特征根均为零；17 17若A的最大特征值max
9、对应的特征向量为W(w1，wn)T，则，即jiijwwa nji,2,1,111122221212Annnnnnwwwwwwwwwwwwwwwwww轾犏犏犏犏犏犏=犏犏犏犏犏犏犏臌18 18 定理定理6.3 n阶正互反矩阵A为一致矩阵当且仅当其最大特征根maxn，且当正互反矩阵A非一致时，必有maxn.根据定理6.3，我们可以由max是否等于n来检验判断矩阵A是否为一致矩阵.由于特征根连续地依赖于aij，故max比n大得越多，A的非一致性程度也就越严重，max对应的标准化特征向量也就越不能真实地反映出Xx1，xn在对因素Z的影响中所占的比重.因此对决策者提供的判断矩阵有必要作一致性检验，以决定
10、是否能接受它.19 19对判断矩阵的一致性进行检验的步骤如下：计算一致性指标CI：查找相应的平均随机一致性指标RI.对n1，9，Saaty给出了RI的值，如表6-2所示.1maxnnCI2020 RI的值是这样得到的，用随机方法构造500个样本矩阵：随机地从19及其倒数中抽取数字构造正互反矩阵，求得最大特征根的平均值max，并定义表 6-221 21 计算一致性比例CR:当CR0.10时，认为判断矩阵的一致性是可以接受的，否则应对判断矩阵作适当修正.1RImaxnnRICICR 22224.层次总排序及一致性检验层次总排序及一致性检验上面我们得到的是一组元素对其上一层中某元素的权重向量.我们最
11、终要得到各元素，特别是最低层中各方案对于目标的排序权重，从而进行方案选择.总排序权重是要自上而下地将单准则下的权重进行合成.2323设上一层次(A层)包含A1，Am共m个因素，它们的层次总排序权重分别为a1，am.又设其后的下一层次(B层)包含n个因素B1，Bn，它们关于Aj的层次单排序权重分别为b1j，bnj(当Bi与Aj无关联时，bij0).现求B层中各因素关于总目标的权重，即求B层各因素的层次总排序权重b1，bn，计算按表6-3所示方式进行，即(i1，n)mjjijiabb12424表 6-32525对层次总排序也需作一致性检验，检验仍像层次总排序那样由高层到低层逐层进行.这是因为虽然各
12、层次均已经过层次单排序的一致性检验，各成对比较判断矩阵都已具有较为满意的一致性.但当综合考察时，各层次的非一致性仍有可能积累起来，引起最终分析结果较严重的非一致性.2626设B层中与Aj相关的因素的成对比较判断矩阵在单排序中经一致性检验，求得单排序一致性指标为CI(j)(j1，m)，相应的平均随机一致性指标为RI(j)(CI(j)、RI(j)已在层次单排序时求得)，则B层总排序随机一致性比例为：当CR0.10时，认为层次总排序结果具有较满意的一致性并接受该分析结果.mjjmjjajaj11)RI()CI(CR27276.1.2 层次分析法的应用层次分析法的应用在应用层次分析法研究问题时，遇到的
13、主要困难有两个：(1)如何根据实际情况抽象出较为贴切的层次结构；(2)如何将某些定性的量作比较，接近实际以定量化处理.层次分析法对人们的思维过程进行了加工整理，提出了一套系统分析问题的方法，为科学管理和决策提供了较有说服力的依据.但层次分析法也有其局限性，主要表现在：(1)它在很大程度上依赖于人们的经验，主观因素的影响很大，它至多只能排除思维过程中的严重非一致性，却无法排除决策者个人可能存在的严重片面性.2828(2)比较、判断过程较为粗糙，不能用于精度要求较高的决策问题.AHP至多只能算是一种半定量(或定性与定量结合)的方法.AHP方法经过几十年的发展，许多学者针对AHP的缺点进行了改进和完
14、善，形成了一些新理论和新方法，像群组决策、模糊决策和反馈系统理论等近几年来成为该领域的一个新热点.在应用层次分析法时，建立层次结构模型是十分关键的一步，下面再分析一个实例，以便说明如何从实际问题中抽象出相应的层次结构.2929例例2 学生挑选合适工作的问题.经双方恳谈，已有三个单位表示愿意录用某毕业生，该生根据已有信息建立了一个层次结构模型，如图6-2所示.解解 首先构造出各层次中的所有判断矩阵.准则层：3561241121221132211111533444153611141112415311131111332221BBBBBBABBBBBB3030图 6-231 31 方案层：311211
15、1422133134121CBCCCCC3212115141223141521CBCCCCC3312131132137317131BCCCCCC3412131211357513711CBCCCCC3232层次总排序如表6-4所示.531212113777117111BCCCCCC631211721397911111BCCCCCC3333根据层次总排序权值，该毕业生最满意的工作为工作1.表表 6-43434图论的发展已有200多年的历史，它发源于18世纪普鲁士的柯尼斯堡七桥问题(Seven Bridges Problem).18世纪初普鲁士的柯尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7
16、座桥横跨河上，把全镇连接起来.当地居民热衷于一个难题：是否存在一条路线，可不重复地走遍七座桥(如图6-3).欧拉用点表示岛和陆地，两点之间的连线表示连接它们的桥，将河流、小岛和桥简化为一个网络，把七桥问题化成判断连通网络能否一笔画出的问题.他不仅解决了此问题，且给出了连通网络可一笔画出的充要条件是它们是连通的，且奇顶点(通过此点弧的条数是奇数)的个数为0或2.6.2 图论模型图论模型3535图 6-33636图论中所谓的“图”是指某类具体事物和这些事物之间的联系.如果我们用点表示这些具体事物，用连接两点的线段(直的或曲的)表示两个事物的特定的联系，就得到了描述这个“图”的几何形象.图论为任何一
17、个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解.下面首先简要介绍图的一些基本概念.37376.2.1 图的基本概念图的基本概念1.无向图无向图一个无向图G是由一个非空有限集合V(G)和V(G)中某些元素的无序对集合E(G)构成的二元组，记为G(V(G)，E(G).其中V(G)v1，v2，vn称为图G的顶点集或节点集，V(G)中的每一个元素vi(i1，2，n)称为该图的一个顶点；E(G)e1，e2，em称为图G的边集，E(G)中的每一个元素ek(即V(G)中某两个元素vi、vj的无序对)记为ek(vi，vj)或ekvivjvjvi(k1，2，m)
18、，被称为该图的一条从vi到vj的边.3838当边ekvivj时，称vi、vj为边ek的端点，并称vj与vi相邻；边ek称为与顶点vi、vj关联.如果某两条边至少有一个公共端点，则称这两条边在图G中相邻.边上赋权的无向图称为赋权无向图.一个图称为有限图，如果它的顶点集和边集都有限.图G的顶点数用符号|V|或(G)表示，边数用|E|或(G)表示.当讨论的图只有一个时，总是用G来表示这个图.从而在图论符号中我们常略去字母G，例如，分别用V，E，和代替V(G)，E(G)，(G)和(G).端点重合为一点的边称为环.一个图称为简单图，如果它既没有环也没有两条边连接到同一对顶点.39392.完全图与二部图完
19、全图与二部图每一对不同的顶点都有一条边相连的简单图称为完全图.n个顶点的完全图记为Kn.若V(G)XY，XY，|X|Y|0(这里|X|表示集合X中的元素个数)，X中无相邻顶点对，Y中亦然，则称G为二部图；特别地，若xX，yY，且xyE(G)，则称G为完全二部图，记成K|X|，|Y|.40403.子图子图图H叫做图G的子图，记作HG，如果V(H)V(G)，E(H)E(G).若H是G的子图，则G称为H的母图.G的生成子图是指满足V(H)V(G)的子图H.41 414.顶点的度顶点的度设vV(G)，G中与v关联的边数(每个环算作两条边)称为v的度，记作d(v).若d(v)是奇数，则称v是奇顶点；若d
20、(v)是偶数，则称v是偶顶点.关于顶点的度，我们有如下结果：vVd(v)2；任意一个图的奇顶点的个数是偶数.42425.图的矩阵表示图的矩阵表示这里我们介绍计算机上用来描述图的两种常用表示方法：邻接矩阵表示法和关联矩阵表示法.在下面数据结构的讨论中，我们首先假设G(V，E)是一个简单有向图，|V|n，|E|m，并假设V中的顶点用自然数1，2，n表示或编号，E中的弧用自然数1，2，m表示或编号.对于有多重边或无向网络的情况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明.43431)邻接矩阵表示法邻接矩阵表示法是将图以邻接矩阵的形式存储在计算机中.邻接矩阵表示了点与点之间的关系.一个图G
21、(V，E)的邻接矩阵A(aij)nn，其中，也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0.可以看出，这种表示法非常简单、直接.1,0,iji jijvvEcvvE4444例例1 对于图6-4所示的图G，可以用邻接矩阵表示为：01100101000001001000001104545 图 6-446462)关联矩阵表示法关联矩阵表示法是将图以关联矩阵(incidencematrix)的形式存储在计算机中.赋权图G(V，E)的关联矩阵A(aij)nn，其中，(),0,ijijijijW vvvvEavvEij4747 6.轨与连通轨与连通若Wv0e1v1e2ekvk，其中
22、eiE(G)，1ik，vjV(G)，0jk，ei与vi1、vi关联，则称W是图G的一条道路，k为路长，顶点v0和vk分别称为W的起点和终点，而v1，v2，vk1称为它的内部顶点.若道路W的边互不相同，则称W为迹.若道路W的顶点互不相同，则称W为轨.称一条道路是闭的，如果它的起点和终点相同.起点和终点重合的轨叫做圈(cycle).4848若图G的两个顶点u、v间存在道路，则称u和v连通.u、v间的最短轨的长叫做u、v间的距离，记作d(u，v).若图G的任二顶点均连通，则称G是连通图.显然有：(1)图P是一条轨的充要条件是P是连通的，且有两个一度的顶点，其余顶点的度为2；(2)图C是一个圈的充要条
23、件是C是各顶点的度均为2的连通图.49496.2.2 最短路径问题最短路径问题1.两个指定顶点之间的最短路径两个指定顶点之间的最短路径问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线.以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G.对G的每一边e，赋以一个实数w(e)直通铁路的长度，称为e的权，得到赋权图G.G的子图的权是指子图的各边的权和.问题就是求赋权图G中指定的两个顶点u0、v0间的具最小权的轨.这条轨叫做u0、v0间的最短路，它的权叫做u0、v0间的距离，亦记作d(u0，v0).5050求最短路已有成熟的算法迪克斯特拉(
24、Dijkstra)算法，其基本思想是按距u0从近到远为顺序，依次求得u0到G的各顶点的最短路和距离，直至v0(或直至G的所有顶点)，算法结束.为避免重复并保留每一步的计算信息，采用了标号算法.下面是该算法的具体内容.令l(u0)0，对vu0，令l(v)，S0u0，i0.对每个，用)()(),(minuvwulvliSuiSv)(iiSVS 51 51代替l(v).计算，把达到这个最小值的一个顶点记为ui1，令Si1Siui1 若i|V|1，停止；若i|V|1，用i1代替i，转.)(minvliSv5252算法结束时，从u0到各顶点v的距离由v的最后一次的标号l(v)给出.在v进入Si之前的标号
25、l(v)叫T标号，v进入Si后的标号l(v)叫P标号.算法就是不断修改各项点的T标号，直至获得P标号.若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，u0至各项点的最短路径也在图上标示出来了.5353例例2 某公司在六个城市c1，c2，c6中有分公司，从ci到cj的直接航程票价记在下述矩阵的(i，j)位置上(表示无直接航路).请帮助该公司设计一张城市c1到其它城市间的票价最便宜的路线图.0552525105501020252510010204020100152520150501025405005454 用矩阵ann(n为顶点个数)存放各边权的邻接矩阵，行向量pb(i
26、)、index1、index2、d(i)分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值.其中各分量含义如下：pb(i)1(当第i顶点已标号)0(当第i顶点未标号)；index1(i):存在第i个进入永久标号集的顶点；index2(i)：存放始点到第i点最短通路中第i顶点前一顶点的序号；d(i)：存放由始点到第i点最短通路的值.顶点未标号当第顶点已标号当第iiipb01)(5555求第一个城市到其它城市的最短路径的MATLAB程序如下：clear；clc；M10000；a(1，:)0，50，M，40，25，10；a(2，:)zeros(1，2)，15，20，M，25；a(3，:
27、)zeros(1，3)，10，20，M；a(4，:)zeros(1，4)，10，25；a(5，:)zeros(1，5)，55；a(6，:)zeros(1，6)；aaa；5656pb(1:length(a)0；pb(1)1；index11；index2ones(1，length(a)；d(1:length(a)M；d(1)0；temp1；whilesum(pb)2indexindex(1)；end index2(temp)index；endd，index1，index258582.每对顶点之间的最短路径每对顶点之间的最短路径计算赋权图中各对顶点之间的最短路径，显然可以调用Dijkstra算法.具
28、体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每一个顶点到其它顶点的最短路径.这种算法的时间复杂度为O(n3).第二种解决这一问题的方法是由FloydRW提出的算法，称之为Floyd算法.5959假设图G权的邻接矩阵为A0，且用来存放各边的长度，其中：aij0(i1，2，n)；aij(i，j之间没有边，在程序中以各边都不可能达到的充分大的数代替)；aijwij(wij是i，j之间边的长度，i，j1，2，n).对于无向图，A0是对称矩阵，aijaji.1112121222012Annnnnnaaaaaaaaa轾犏犏犏
29、=犏犏犏臌6060Floyd算法的基本思想是：递推产生一个矩阵序列A0，A1，Ak，An，其中Ak(i，j)表示从顶点vi到顶点vj的路径上所经过的顶点序号不大于k的最短路径长度.计算时用迭代公式：Ak(i，j)minAk1(i，j)，Ak1(i，k)Ak1(k，j)k是迭代次数，i，j，k1，2，n.最后，当kn时，An即是各顶点之间的最短通路值.61 61例例3 用Floyd算法求解例2.矩阵path用来存放每对顶点之间最短路径上所经过的顶点的序号.Floyd算法的MATLAB程序如下：clear；clc；M10000；a(1，:)0，50，M，40，25，10；a(2，:)zeros(1
30、，2)，15，20，M，25；a(3，:)zeros(1，3)，10，20，M；a(4，:)zeros(1，4)，10，25；6262a(5，:)zeros(1，5)，55；a(6，:)zeros(1，6)；baa；pathzeros(length(b)；fork1:6 fori1:6forj1:6 ifb(i，j)b(i，k)b(k，j)b(i，j)b(i，k)b(k，j)；path(i，j)k；6363 endend endendb，path64646.2.3 邮递员问题邮递员问题定义定义6.3 经过G的每条边的迹叫做G的Euler迹；封闭的Euler迹叫做Euler回路或E回路；含Eul
31、er回路的图叫做Euler图.直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点.定理定理6.4()G是Euler图的充分必要条件是G连通且每顶点皆偶次.(2)G是Euler图的充分必要条件是G连通且，Ci是圈，E(Ci)E(Cj)(ij).diiCG16565()G中有Euler迹的充要条件是G连通且至多有两个奇次点.1921年，Fleury给出了下面的求Euler回路的算法.6666(1)v0V(G)，令W0v0.(2)假设迹Wiv0e1v1eivi已经选定，那么按下述方法从Ee1，ei中选取边ei1：ei1和vi相关联；除非没有别
32、的边可选择，否则ei1不是GiGe1，ei的割边(所谓割边，是指一条删除后使连通图不再连通的边).6767(3)当第(2)步不能再执行时，算法停止.邮递员问题可描述为：一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他的投递行程最短.上述邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小.显然，若此连通赋权图是Euler图，则可用Fleury算法求出Euler回路，此回路即为所求.6868对于非Euler图，1973年，Edmonds和Johnson给出下面的解法：设G是连通赋权图.()求V0v
33、|vV(G)，d(v)1(mod2).()对每对顶点u，vV0，求d(u，v)(d(u，v)是u与v的距离，可用Floyd算法求得).()构造完全赋权图 ，以V0为顶点集，以d(u，v)为边uv的权.()求 中权之和最小的完美对集M.()求M中边的端点之间的在G中的最短轨.|0VK|0VK6969()在(5)中求得的每条最短轨上的每条边添加一条等权的所谓“倍边”(即共端点且共权的边)，记其为G.()在(6)中得到的图G上求Euler回路，此即为邮递员问题的解.上述问题可推广为多邮递员问题，即：邮局有k(k2)位投递员，同时投递信件，全城街道都要投递，完成任务后返回邮局，如何分配投递路线，使得完
34、成投递任务的时间最早？我们把这一问题记成kPP.7070kPP的数学模型如下：G(V，E)是连通图，v0V(G)，求G的回路C1，Ck，使得()v0V(Ci)(i1，2，k)；()()min)(max)(1iCEekiew).()(1GECEiki71 71.6.2.4 旅行商问题旅行商问题定义定义6.4 包含G的每个顶点的轨叫做Hamilton(哈密顿)轨；封闭的Hamilton轨叫做Hamilton圈或H圈；含Hamilton圈的图叫做Hamilton图.直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次即能回到出发点的那种图，亦即不重复地行遍所有的顶点再回到出发点.一名推销员准
35、备前往若干城市推销产品，然后回到他的出发地.如何为他设计一条最短的旅行路线(从驻地出发，恰好经过每个城市一次，最后返回驻地)？这个问题称为旅行商问题.用图论来描述就是在一个赋权完全图中，7272找出一个有最小权的Hamilton圈.称这种圈为最优圈，与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法.所以希望有一个方法以获得相当好(但不一定最优)的解.7373一个可行的方法是首先求一个Hamilton圈C，然后适当修改C以得到具有较小权的另一个Hamilton圈.修改的方法叫做改良圈算法.设初始圈Cv1v2vnv1.()对于1i1jn，构造新的Hamilton圈:Cijv1v2vi
36、vjvj1vj2vi1vj1vj2vnv1它是由C中删去边vivi1和vjvj1，添加边vivj和vi1vj1而得到的.若w(vivj)w(vi1vj1)07979flag0；form1:L3fornm2:L1 ifa(c1(m)，c1(n)a(c1(m1)，c1(n1)0flag0；form1:L3fornm2:L1 ifa(c1(m)，c1(n)a(c1(m1)，c1(n1).a(c1(m)，c1(m1)a(c1(n)，c1(n1)flag1；81 81 c1(m1:n)c1(n:1:m1)；endend endendsum10；fori1:L1 sum1sum1a(c1(i)，c1(i1
37、)；endifsum1|M|的对集M，则M称为最大对集；若G中有一轨，其边交替地在对集M内外出现，则称此轨为M的交错轨.交错轨的起止顶点都未被许配时，此交错轨称为可增广轨.8383若把可增广轨上在M外的边纳入对集，把M内的边从对集中删除，则被许配的顶点数增加2，对集中的“对儿”增加一个.1957年，贝尔热(Berge)得到最大对集的充要条件如下：定理6.5 M是图G中的最大对集当且仅当G中无可增广轨M.1935年，霍尔(Hall)得到下面的许配定理：定理6.6 G为二分图，X与Y是顶点集的划分，G中存在把X中顶点皆许配的对集的充要条件是，SX，则|N(S)|S|，其中N(S)是S中顶点的邻集.
38、由上述定理可以得出：8484推论1：若G是k(k0)正则2分图，则G有完美对集.所谓k正则图，即每顶点皆k度的图.由此推论得出下面的婚配定理：8585定理6.7 每个姑娘都结识k(k1)位小伙子，每个小伙子都结识k位姑娘，则每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚.人员分派问题等实际问题可以化成对集来解决.人员分派问题：工作人员x1，x2，xn去做n件工作y1，y2，yn，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？8686这个问题的数学模型是：G是二分图，其顶点集划分为V(G)XY，X1x1，xn，Y1y1
39、，yn，当且仅当xi适合做工作yi时，xiyiE(G)，求G中的最大对集.解决这个问题可以利用1965年埃德门兹(Edmonds)提出的匈牙利算法.8787匈牙利算法：()从G中任意取定一个初始对集M.()若M把X中的顶点皆许配，停止，M即完美对集；否则取X中未被M许配的一顶点u，记Su，T.()若N(S)T，停止，无完美对集；否则取yN(S)T.()若y是被M许配的，设yzM，SSz，TTy，转()；否则，取可增广轨P(u，y)，令M(ME(P)(E(P)M)，转().把以上算法稍加修改就能够用来求二分图的最大对集.8888最优分派问题：在人员分派问题中，工作人员适合做的各项工作当中，效益未
40、必一致，我们需要制定一个分派方案，使公司总效益最大.这个问题的数学模型是：在人员分派问题的模型中，图G的每边加了权w(xiyj)0，表示xi干yj工作的效益，求加权图G上的权最大的完美对集.解决这个问题可以用库恩曼克莱斯(KuhnMunkres)算法.为此，我们要引入可行顶点标号与相等子图的概念.8989定义6.6 若映射l:V(G)R，满足xX，yY，有l(x)l(y)w(x，y)则称l是二分图G的可行顶点标号.令Elxy|xyE(G)，l(x)l(y)w(xy)称以El为边集的G的生成子图为相等子图，记作Gl.可行顶点标号是存在的.例如，(xX)l(y)0(yY);),(max)(Xxxy
41、wxlYy9090 定理定理6.8 Gl的完美对集即为G的权最大的完美对集.Kuhn-Munkres算法:()选定初始可行顶点标号l，确定Gl，在Gl中选取一个对集M.()若X中顶点皆被M许配，停止，M即G的权最大的完美对集；否则，取Gl中未被M许配的顶点u，令Su，T.91 91()若，转(4)；若，取)()()(min,xywylxlTySxl其它),(,)(,)()(vlTvvlSvvlvlll,ll llGG TSNlG)(TSNlG)(9292 ()选中一顶点y，若y已被M许配，且yxM，则SSz，TTy，转()；否则，取Gl中一个M可增广轨P(u，y)，令M(ME(P)(E(P)M)转().其中，是Gl中S的相邻顶点集.TSNlG)()(SNlG
