1、图与网络模型及方法 概论图论起源于18世纪。第一篇图论论文是瑞士数学家欧拉于1736 年发表的“哥尼斯堡的七座桥”。1847年，克希霍夫为了给出电网络方程而引进了“树”的概念。1857年，凯莱在计数烷的同分异构物时，也发现了“树”。哈密尔顿于1859年提出“周游世界”游戏，用图论的术语，就是如何找出一个连通图中的生成圈。近几十年来，由于计算机技术和科学的飞速发展，大大地促进了图论研究和应用，图论的理论和方法已经渗透到物理、化学、通讯科学、建筑学、生物遗传学、心理学、经济学、社会学等学科中。图得概念：图论中所谓的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点
2、的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。例子：哥尼斯堡七桥问题：在哥尼斯堡有七座桥将普莱格尔河中的两个岛及岛与河岸联结起来问题是要从这四块陆地中的任何一块开始通过每一座桥正好一次，再回到起点 可以通过试验去尝试解决这个问题，但该城居民的任何尝试均未成功。欧拉为了解决这个问题，采用了建立数学模型的方法。他将每一块陆地用一个点来代替，将每一座桥用连接相应两点的一条线来代替，从而得到一个有四个“点”，七条“线”的“图”。问题成为从任一点出发一笔画出七条
3、线再回到起点。欧拉考察了一般一笔画的结构特点，给出了一笔画的一个判定法则：这个图是连通的，且每个点都与偶数线相关联，将这个判定法则应用于七桥问题，得到了“不可能走通”的结果，不但彻底解决了这个问题，而且开创了图论研究的先河。图论的应用：图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。图与网络优化的一些基本问题：例1 最短路问题（SPPshortest path problem）一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因
4、此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。例2 公路连接问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路的成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？例3 指派问题（assignment problem）一家公司经理准备安排名员工去完成项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报是不同的。如何分配工作方案可以使总回报最大？例4 中国邮
5、递员问题（CPPchinese postman problem）一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？由于这一问题是我国管梅谷教授1960年首先提出的，所以国际上称之为中国邮递员问题。例5 旅行商问题（TSPtraveling salesman problem）一名推销员准备前往若干城市推销产品。如何为他（她）设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这一问题的研究历史十分悠久，通常称之为旅行商问题。例6 运输问题（transportation problem）某种原材料
6、有个产地，现在需要将原材料从产地运往个使用这些原材料的工厂。假定每个产地的产量和家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？上述问题有两个共同的特点：一是它们的目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学上把这种问题称为最优化或优化（optimization）问题；二是它们都易于用图形的形式直观地描述和表达，数学上把这种与图相关的结构称为网络（network）。与图和网络相关的最优化问题就是网络最优化或称网络优化（netwok optimization）问题。所以上面例子中介绍的问题都是网络优化问题。由于多数网络
7、优化问题是以网络上的流（flow）为研究的对象，因此网络优化又常常被称为网络流（network flows）或网络流规划等 图与网络的基本概念 无向图：一个无向图(undirected graph)G是由一个非空有限集合 和 中某些元素的无序对集合构成的二元组，记为 。其中 称为图的顶点集（vertex set）或节点集（node set），中的每一个元素称为该图的一个顶点（vertex）或节点（node）；称为图的边集（edge set），中的每一个元素 (即中某两个元素 的无序对)记为 或 ，被称为该图的一条从 到 的边（edge）。,)(21nvvvGV)(GV)(GV)(),(GEGV
8、G)(GV,)(21meeeGE)(GEkejivv,),(jikvve ijjikvvvve),2,1(mkivjv当边 时，称 为边 的端点，并称与 相邻（adjacent）；边 称为与顶点 关联（incident）。如果某两条边至少有一个公共端点，则称这两条边在图 中相邻。),(jikvve jivv,kejivv,kejivv,G边上赋权的无向图称为赋权无向图或无向网络（undirected network）。我们对图和网络不作严格区分，因为任何图总是可以赋权的。一个图称为有限图有限图，如果它的顶点集和边集都有限。图的顶点数用符号 或 表示，边数用 或 表示。|V)(G|E)(G端点重
9、合为一点的边称为环环(loop)。一个图称为简单图简单图(simple graph)，如果它既没有环也没有两条边连接同一对顶点。有向图：当图的边集中的边是顶点的有序对时，这时候就称为这些边是有方向的。从而原来的无向图也就成为这儿的有向图。顶点的度：一个顶点的度是与这个顶点相关联的边的数目。在有向图的情形下，一个顶点的度还分为顶点入度和顶点出度两种情形。顶点的入度是与这个顶点相关联的并且指向这个顶点的边的数目。顶点的出度是与这个顶点相关联的并且方向远离这个顶点的边的数目。图与网络的数据结构网络优化研究的是网络上的各种优化模型与算法为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结
10、构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中，我们首先假设 是一个简单有向图，并假设中的顶点用自然数 表示或编号，中的弧用自然数 表示或编号。对于有多重边或无向网络的情况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。),(AVG mAnV|,|n,2,1Am,2,1（i）邻接矩阵表示法邻接矩阵表示法是将图以邻接矩阵（adjacency matrix）的形式存储在计算机中。图
11、的邻接矩阵是如下定义的：是一个 的 矩阵，即),(AVG Cnn10nnnnijcC1,0)(.),(,0,),(,1AjiAjicij也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1；否则为0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有 个元素中，只有 个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。2nm例7 对于上图所示的图，可以用邻接矩阵表示为 0110010100000100100000110，同样，对于网络中的权，也可以用类似邻接矩阵的矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。如果网络中每
12、条弧赋有多种权，则可以用多个矩阵表示这些权。（ii）关联矩阵表示法关联矩阵表示法是将图以关联矩阵（incidence matrix）的形式存储在计算机中图 的关联矩阵 是如下定义的：是一个 的矩阵，即),(AVG BBmnmnmnikbB1,0,1)(.,0,),(,1,),(,1其它AijkVjAjikVjbik也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关上联矩阵中对应的元素为1；如果一个节点是一条弧的终点，则关联矩阵中对应的元素为-1；如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。对于简单图，关联矩阵每列只含有两个非零元（
13、一个+1，一个-1）。可以看出，这种表示法也非常简单、直接。但是，在关联矩阵的所有nm个元素中，只有2m个为非零元。如果网络比较稀疏，这种表示法也会浪费大量的存储空间。但由于关联矩阵有许多特别重要的理论性质，因此它在网络优化中是非常重要的概念。例8 对于例7所示的图，如果关联矩阵中每列对应弧的顺序为(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)，则关联矩阵表示为:1110000010110100010110100000110100000011同样，对于网络中的权，也可以通过对关联矩阵的扩展来表示。例如，如果网络中每条弧有一个权，我们可以把关联矩阵
14、增加一行，把每一条弧所对应的权存储在增加的行中。如果网络中每条弧赋有多个权，我们可以把关联矩阵增加相应的行数，把每一条弧所对应的权存储在增加的行中。（iii）弧表示法弧表表示法将图以弧表（arc list）的形式存储在计算机中。所谓图的弧表，也就是图的弧集合中的所有有序对。弧表表示法直接列出所有弧的起点和终点，共需 2m个存储单元，因此当网络比较稀疏时比较方便。此外，对于网络图中每条弧上的权，也要对应地用额外的存储单元表示。例如，例7所示的图，假设弧(1,2)，(1,3)，(2,4)，(3,2)，(4,3)，(4,5)，(5,3)和(5,4)上的权分别为8，9，6，4，0，3，6和7，则弧表表
15、示如下：起点11234455终点23423534权89640367为了便于检索，一般按照起点、终点的字典序顺序存储弧表，如上面的弧表就是按照这样的顺序存储的。（iv）邻接表表示法邻接表表示法将图以邻接表（adjacency lists）的形式存储在计算机中。所谓图的邻接表，也就是图的所有节点的邻接表的集合；而对每个节点，它的邻接表就是它的所有出弧。邻接表表示法就是对图的每个节点，用一个单向链表列出从该节点出发的所有弧，链表中每个单元对应于一条出弧。为了记录弧上的权，链表中每个单元除列出弧的另一个端点外，还可以包含弧上的权等作为数据域。图的整个邻接表可以用一个指针数组表示。例如，例7所示的图，邻
16、接表表示为这是一个5维指针数组，每一维（上面表示法中的每一行）对应于一个节点的邻接表，如第1行对应于第1个节点的邻接表（即第1个节点的所有出弧）。每个指针单元的第1个数据域表示弧的另一个端点（弧的头），后面的数据域表示对应弧上的权。如第1行中的“2”表示弧的另一个端点为2（即弧为（1,2），“8”表示对应弧(1,2)上的权为8；“3”表示弧的另一个端点为3（即弧为(1,3)），“9”表示对应弧（1，3）上的权为9。又如，第5行说明节点5出发的弧有(5,3)、(5,4)，他们对应的权分别为6和7。对于有向图，一般用 表示节点 的邻接表，即节点 的所有出弧构成的集合或链表（实际上只需要列出弧的另一
17、个端点，即弧的头）。例如上面例子，等。这种记法我们在本书后面将会经常用到。)(iAii3,2)1(A，4,3)5(A（v）星形表示法星形（star）表示法的思想与邻接表表示法的思想有一定的相似之处。对每个节点，它也是记录从该节点出发的所有弧，但它不是采用单向链表而是采用一个单一的数组表示。也就是说，在该数组中首先存放从节点1出发的所有弧，然后接着存放从节点2出发的所有孤，依此类推，最后存放从节点出发的所有孤。对每条弧，要依次存放其起点、终点、权的数值等有关信息。这实际上相当于对所有弧给出了一个顺序和编号，只是从同一节点出发的弧的顺序可以任意排列。此外，为了能够快速检索从每个节点出发的所有弧，我
18、们一般还用一个数组记录每个节点出发的弧的起始地址（即弧的编号）。在这种表示法中，可以快速检索从每个节点出发的所有弧，这种星形表示法称为前向星形（forward star）表示法。例如，在例7所示的图中，仍然假设弧（1,2），（l,3），（2,4），（3,2），（4,3），（4,5），（5,3）和（5,4）上的权分别为8，9，6，4，0，3，6和7。此时该网络图可以用前向星形表示法表示如下：节点对应的出弧的起始地址编号数组（记为）节点号i起始地址)(ipoint123456134679记录弧信息的数组弧编号12345678起点11234455终点23423534权89640367在数组中，其元素
19、个数比图的节点数多1（即n+1），且一定有 ，。对于节点 ，其对应的出弧存放在弧信息数组的位置区间为 1)1(point，1)1(mnpoint i 1)1(),(ipointipoint如果 ，则节点没有出弧。这种表示法与弧表表示法也非常相似，“记录弧信息的数组”实际上相当于有序存放的“弧表”。只是在前向星形表示法中，弧被编号后有序存放，并增加一个数组（）记录每个节点出发的弧的起始编号。)1()(ipointipointpoint前向星形表示法有利于快速检索每个节点的所有出弧，但不能快速检索每个节点的所有入弧。为了能够快速检索每个节点的所有入孤，可以采用反向星形（reverse star）表
20、示法：首先存放进入节点1的所有孤，然后接着存放进入节点2的所有弧，依此类推，最后存放进入节点的所有孤。对每条弧，仍然依次存放其起点、终点、权的数值等有关信息。同样，为了能够快速检索从每个节点的所有入弧，我们一般还用一个数组记录每个节点的入孤的起始地址（即弧的编号）。例如，例7所示的图，可以用反向星形表示法表示为如下形式：节点对应的入弧的起始地址编号数组（记为）节点号123456起始地址113689)(irpointi记录弧信息的数组弧编号12345678终点22333445起点31145524权48906763如果既希望快速检索每个节点的所有出弧，也希望快速检索每个节点的所有入弧，则可以综合采
21、用前向和反向星形表示法。当然，将孤信息存放两次是没有必要的，可以只用一个数组（trace）记录一条弧在两种表示法中的对应关系即可。例如，可以在采用前向星形表示法的基础上，加上上面介绍的数组和如下的数组即可。这相当于一种紧凑的双向星形表示法如下所示：两种表示法中的弧的对应关系（记为）反向法中弧编号j正向法中弧编号)(jtrace1234567841257836对于网络图的表示法，我们作如下说明 星形表示法和邻接表表示法在实际算法实现中都是经常采用的。星形表示法的优点是占用的存储空间较少，并且对那些不提供指针类型的语言（如 FORTRAN语言等）也容易实现。邻接表表示法对那些提供指针类型的语言（如
22、C语言等）是方便的，且增加或删除一条弧所需的计算工作量很少，而这一操作在星形表示法中所需的计算工作量较大（需要花费 计算时间）。有关“计算时间”的观念是网络优化中需要考虑的一个关键因素。)(mO 当网络不是简单图，而是具有平行弧（即多重弧）时，显然此时邻接矩阵表示法是不能采用的。其他方法则可以很方便地推广到可以处理平行弧的情形。上述方法可以很方便地推广到可以处理无向图的情形，但由于无向图中边没有方向，因此可能需要做一些自然的修改。例如，可以在计算机中只存储邻接矩阵的一半信息（如上三角部分），因为此时邻接矩阵是对称矩阵。无向图的关联矩阵只含有元素0和+1，而不含有-1，因为此时不区分边的起点和终
23、点。又如，在邻接表和星形表示法中，每条边会被存储两次，而且反向星形表示显然是没有必要的，等等。轨与连通 kkveevevW2110 ，其中 ，。其中与 关联。W称为图G的一条道路，k为路长。顶点 称为W的起点和终点。)(GEeiki 1)(GVvjkj 0ieiivv,10vkv若道路W的边互不相同，则W称为迹(trail)。若道路W的顶点互不相同，则W称为轨(path)。称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做圈.若图G的两个顶点u,v间存在道路，则称u和v连通(connected)。U,v间的最短轨的长叫做U,v间的距离。记作d(u,v)。若图G的任二顶点均
24、连通，则称G是连通图。应用v两个指定顶点之间的最短距离00,vu问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线 以各城镇为图G的顶点，两城镇间的直通铁路为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数w(e)直通铁路的长度，称为e的权，得到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图中指定的两个顶点 间的具最小权的轨。这条轨叫做 间的最短路，它的权叫做 间的距离，亦记作 。00,vu00,vu),(00vud求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距 从近到远为顺序，依次求得 到的各顶点的
25、最短路和距离，直至 （或直至G的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法.下面是该算法。0u0u0v (i 令 ，对 ，令 ，。0)(0ul0uv)(vl00uS 0i(ii)对每个 （），用 代替 。计算 ，把达到这个最小值的一个顶点记为 ，令 。iSviiSVS)()(),(minuvwulvliSu)(vl)(minvliSv1iu11iiiuSS(iii).若 ，停止；若 ，用 代替 ，转(ii)。1|Vi1|Vi1ii算法结束时，从 到各顶点的距离由 的最后一次的标号给出。在 进入 之前的标号叫T标号，进入 时的标号叫P标号。算法就是不断修改各项点的T标
26、号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，至各项点的最短路也在图上标示出来了。0u)(vlviSviS0u例9 某公司在六个城市中有分公司 ，从 到 的直接航程票价记在下述矩阵的 位置上。（表示无直接航路），请帮助该公司设计一张城市 到其它城市间的票价最便宜的路线图。621,cccicjc),(ji1c055252510550102025251001020402010015252015050102540500用矩阵 （n为顶点个数）存放各边权的邻接矩阵，行向量 、分别用来存放 标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量 ；
27、存放始点到第 点最短通路中第 顶点前一顶点的序号；存放由始点到第 点最短通路的值。nnapb1index2indexP顶点未标号当第顶点已标号当第iiipb01)()(2iindexii)(idi求第一个城市到其它城市的最短路径的Matlab程序如下：clear;clc;M=10000;a(1,:)=0,50,M,40,25,10;a(2,:)=zeros(1,2),15,20,M,25;a(3,:)=zeros(1,3),10,20,M;a(4,:)=zeros(1,4),10,25;a(5,:)=zeros(1,5),55;a(6,:)=zeros(1,6);a=a+a;pb(1:leng
28、th(a)=0;pb(1)=1;index1=1;index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;while sum(pb)=2 index=index(1);end index2(temp)=index;endd,index1,index2 连通的无圈图叫做树，记之为 。若图 满足 ，则称 是 的生成树。图 连通的充分必要条件为 有生成树。一个连通图的生成树的个数很多，用 表示 的生成树的个数，则有公式TG)()(TVGV)()(GETETGGG)(GG)()()(eGeGG其中 表示从 上删除边 ，表示把 的长度收缩为零得到的图。
29、eG GeeGe应用连线问题:欲修筑连接 个城市的铁路，已知城 与城 之间的铁路造价为 ，设计一个线路图，使总造价最低。nijijC下面介绍构造最小生成树的两种常用算法。prim算法构造最小生成树算法构造最小生成树设置两个集合 和 ,其中 用于存放的最小生成树中的顶点，集合 存放的最小生成树中的边。令集合 的初值为 （假设构造最小生成树时，从顶点 出发），集合 的初值为 。prim算法的思想是，从所有 ，的边中，选取具有最小权值的边 ，将顶点 加入集合 中，将边 加入集合 中，如此不断重复，直到 时，最小生成树构造完毕，这时集合 中包含了最小生成树的所有边。PQPQP1vP 1vQQPpPVv
30、pvvPpvQVP Q例11 用prim算法求右图的最小生成树。我们用的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab程序如下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;a=a;zeros(2,7);a=a+a;a(find(a=0)=M;result=;p=1;tb=2:length(a);while length(result)=length(a)-1 temp=a(p,tb);te
31、mp=temp(:);d=min(temp);jb,kb=find(a(p,tb)=d);j=p(jb(1);k=tb(kb(1);result=result,j;k;d;p=p,k;tb(find(tb=k)=;endresult例12 用Kruskal算法构造例11的最小生成树。我们用 存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号 改记为此边的另一序号 ，同时把后面边中所有序号为 的改记为 。此方法的几何意义是：将序号 的这个顶点收缩到顶点 ，顶点 不复存在。后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。nindex2uvuvu
32、vuMatlab程序如下：clc;clear;M=1000;a(1,2)=50;a(1,3)=60;a(2,4)=65;a(2,5)=40;a(3,4)=52;a(3,7)=45;a(4,5)=50;a(4,6)=30;a(4,7)=42;a(5,6)=70;i,j=find(a=0)&(a=M);b=a(find(a=0)&(a=M);data=i;j;b;index=data(1:2,:);loop=max(size(a)-1;result=;while length(result)v2 index(find(index=v1)=v2;else index(find(index=v2)=v
33、1;end data(:,flag)=;index(:,flag)=;endresult 匹配问题 定义定义 若 ，与 无公共端点（），则称 为图 的一个对集；中的一条边的两个端点叫做在对集中相配；中的端点称为被许配；中每个顶点皆被许配时，称为完美对集；中已无使 的对集 ，则称 为最大对集；若中有一轨，其边交替地在对集 内外出现，则称此轨为 的交错轨，交错轨的起止顶点都未被许配时，此交错轨称为可增广轨。)(GEM Meeji,iejeji MMGGGG|MM MMMMM若把可增广轨上在 外的边纳入对集，把 内的边从对集中删除，则被许配的顶点数增加2，对集中的“对儿”增加一个。MM1957年，贝
34、尔热(Berge)得到最大对集的充要条件：定理定理2 是图 中的最大对集当且仅当 中无 可增广轨。MGGM1935年，霍尔(Hall)得到下面的许配定理：定理定理3 为二分图，与 是顶点集的划分，中存在把 中顶点皆许配的对集的充要条件是，则 ，其中 是 中顶点的邻集。GXYGXXS|)(|SSN)(SNS由上述定理可以得出：推论推论1：若 是 （)正则2分图，则 有完美对集。Gk)0kG应用应用人员分派问题：人员分派问题：工作人员 去做 件工作 ，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？nxxx,21nnyyy,21这个问题的数学模型是：是二
35、分图，顶点集划分为 ，当且仅当 适合做工作 时，求 中的最大对集 GYXGV)(,11nxxX,11nyyYixiy)(GEyxiiG解决这个问题可以利用1965年埃德门兹(Edmonds)提出的匈牙利算法。i）从 中任意取定一个初始对集 。（ii）若 把 中的顶点皆许配，停止，即完美对集；否则取 中未被许配的一顶点 ，记 ，。（iii）若 ，停止，无完美对集；否则取 。（iv）若 是被 许配的，设 ，转（iii）；否则，取可增广轨 ，令 ，转（ii）。GMXMMXuuS TTSN)(TSNy)(yMMyzzSSyTT),(yuP)()(MPEPEMM最优分派问题：分派问题：在人员分派问题中，
36、工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。这个问题的数学模型是：在人员分派问题的模型中，图 的每边加了权 ，表示 干工作 的效益，求加权图 上的权最大的完美对集。Gix0)(jiyxwjyG解决这个问题可以用库恩曼克莱斯（Kuhn-Munkres）算法。为此，我们要引入可行顶点标号与相等子图的概念。定义定义 若映射 ，满足 ，则 称是二分图 的可行顶点标号。令 ，称以 为边集的 的生成子图为相等子图，记作 。RGVl)(:YyXx,),()()(yxwylxllG)()()(),(|xywylxlGExyxyEllEGlG可行顶点标号是存在的。例如
37、;),(max)(XxxywxlYyYyyl ,0)(定理定理5 的的完美对集即为 的权最大的完美对集。lGGKuhn-Munkres算法算法（i）选定初始可行顶点标号 ，确定 ，在 中选取一个对集 。（ii）若 中顶点皆被许配，停止，即的权最大的完美对集；否则，取中未被许配的顶点 ，令 ，。(iii)若 ，转（iv）；若 ，取 ，。（iv）选 中一顶点 ，若 已被 许配，且 ，则 ，转（iii）；否则，取 中一个 可增广轨，令 ，转（ii）。其中 是 中 的相邻顶点集。llGlGMXMlGuuS TTSNlG)(TSNlG)()()()(min,xywylxlTySxl其它),(,)(,)(
38、)(vlTvvlSvvlvlllll llGG TSNlG)(yyMMyxzSSyTTlGM),(yuP)()(MPEPEMM)(SNlGlGS Euler图和Hamilton图 基本概念 定义定义 经过的每条边的迹叫做的Euler迹；闭的Euler迹叫做Euler回路或回路；含Euler回路的图叫做Euler图。直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。定理定理7 （i）是Euler图的充分必要条件是 连通且每顶点皆偶次。（ii）是Euler图的充分必要条件是 连通且 ，是圈，。（iii）中有Euler迹的充要条件是 连通且
39、至多有两个奇次点。GGGGdiiCG1iCGG定义定义 包含的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton轨叫做Hamilton圈或 圈；含Hamilton圈的图叫做Hamilton图。H直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。6.2 Euler回路的Fleury算法1921年，Fleury给出下面的求Euler回路的算法。Fleury算法：算法：1.，令 。2.假设迹 已经选定，那么按下述方法从 中选取边：（i）和 相关联；（ii）除非没有别的边可选择，否则不是 的割边(cut edge)。
40、(所谓割边是一条删除后使连通图不再连通的边)。3.当第2步不能再执行时，算法停止。)(0GVv 00vW iiivevevW110,1ieeE1ieiv,1iieeGG6.3 应用6.3.1 邮递员问题中国邮递员问题一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。上述中国邮递员问题的数学模型是：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小。显然，若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求。6.3.2 旅行商（TSP）问题一名推销员准备前往若干城市推销产品，然后
41、回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？这个问题称为旅行商问题。用图论的术语说，就是在一个赋权完全图中，找出一个有最小权的Hamilton圈。称这种圈为最优圈。与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。一个可行的办法是首先求一个Hamilton圈，然后适当修改以得到具有较小权的另一个Hamilton圈。修改的方法叫做改良圈算法。设初始圈 。121vvvvCn（i）对于 ，构造新的Hamilton圈:,它是由中删去边 和 ，添加边 和 而得到的。若 ，则以 代替 ，
42、叫做 的改良圈。（ii）转（i），直至无法改进，停止 nji1112112121vvvvvvvvvvvCnjjijjjiij1iivv1jjvvjivv11jivv)()()()(1111jjiijijivvwvvwvvwvvwijCCijCC用改良圈算法得到的结果几乎可以肯定不是最优的。为了得到更高的精确度，可以选择不同的初始圈，重复进行几次算法，以求得较精确的结果。例13 从北京（Pe）乘飞机到东京(T)、纽约(N)、墨西哥城(M)、伦敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表：LMNPaPeTL5635215160
43、M5621577870N3521366868Pa2157365161Pe5178685113T6070686113解：编写程序如下：clc,cleara(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;a(3,4)=36;a(3,5)=68;a(3,6)=68;a(4,5)=51;a(4,6)=61;a(5,6)=13;a(6,:)=0;a=a+a;c1=5 1:4 6;L=length(c1);flag=1;while flag0 flag=0;for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)0 flag=0;for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1).a(c1(m),c1(m+1)+a(c1(n),c1(n+1)flag=1;c1(m+1:n)=c1(n:-1:m+1);end end endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endif sum1sum sum=sum1;circle=c1;endcircle,sum
