第5章图论与网络规划模型.

第5章图论与网络规划模型图论作为离散数学的一个重要分支，在工程技术、自然科学和经济管理中许多方面都能提供有力的数学模型来解决实际问题。比如，哥尼斯堡七桥问题、中国邮递员问题、四色定理等等。图论方法已经成为数学模型中的重要方法。许多难题由于归结为图论问题被巧妙地解决。第5章图论与网络规划模型5.1图的基本概念5.2最短路问题与最大流问题5.3最优连线问题与旅行商问题5.1.1图的定义5.1图的基本概念图G是一个偶对（V,E），其中V(G)={v1,v2,…,vn}为图的顶点集（vertexset），E(G)={e1,e2,…,en}为图的边集（edgeset）或弧集（常用A表示）,记ek=(vi,vj)(k=1,2,…,m)。若ek是无序对，则称G为无向图（undirectedgraph）；若ek=(vi,vj)是有序对，则称G为有向图（directedgraph），vi为的起点，vj为的终点，称去掉有向图的方向得到的图为基础图（underlyinggraph）。5.1.1图的定义一个图称为有限图，如果它的顶点集和边集都有限。图G的顶点数用符号|V|表示，边数用|E|表示。端点重合为一点的边称为环(loop)。连接两个相同顶点的边的条数称为边的重数，重数大于1的边称为重边(multi-edges)。在有向图中，两个顶点相同但方向相反的边称为对称边(symmetricedge)。一个图称为简单图(simplegraph)，如果它既没有环也没有重边。5.1.2完全图、二分图、子图每一对不同的顶点都有一条边相连的简单图称为完全图(completegraph)。n个顶点的完全图记为Kn；完全图的定向图称为竞赛图。若V(G)=X∪Y，X∩Y=空集，|X||Y|≠0,X中无相邻顶点对，Y中亦然，则称G为二分图(bipartitegraph)；特别地，若对任意的x∈X,y∈Y，都有xy∈E(G)，则称G为完全二分图，记成K|X|,|Y|。G的支撑子图是指满足V(H)=V(G)的子图。若H是G的子图，则G称为H的母图。GH图H叫做图G的子图，记作，如果)()(GVHV5.1.3顶点的度设v∈V(G)，G中与v关联的边数（每个环算作两条边）称为v的度(degree)，记作d(v)。若d(v)是奇数，称v是奇度顶点(oddpoint)；若d(v)是偶数，称v是偶度顶点(evenpoint)。对有向图，以v为起点的有向边数称为v的出度(out-degree)，记作d+(v)；以为终点的有向边数称为的入度(in-degree)，记作d－(v)；顶点的度d(v)=d+(v)+d－(v)。5.1.4迹、路、圈与连通无向图G的一条途径(walk)是指一个有限的非空序列W=v0e1v1e2…ekvk，其中ei∈E(G)，1≤i≤k，vj∈V(G)，0≤j≤k，ei与vi-1vi关联，称k为W的长(length)。若途经的边互不相同，则称W为迹(trail)；若途径的顶点互不相同，则称W为路(path)；如果v0=vk，并且没有其他相同的顶点，则称W为圈(cycle)。若图G的两个顶点u,v间存在道路，则称u和v连通(connected)。u,v间的最短轨的长叫做u,v间的距离。记作d(u,v)。若图G的任二顶点均连通，则称G是连通图。5.1.5图与网络的数据结构为了在计算机上实现网络优化的算法，首先我们必须有一种方法（即数据结构）在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。首先假设G=(V,A)是一个简单有向图，|V|=n,|A|=m，并假设V中的顶点用自然数1,2,…,n表示或编号，A中的弧用自然数1,2,…,m表示或编号。5.1.5图与网络的数据结构-邻接矩阵表示法邻接矩阵表示法是将图以邻接矩阵（adjacencymatrix）的形式存储在计算机中。图G=(V,A)的邻接矩阵是如下定义的：C是一个n×n的矩阵，即nnnnijcC}1,0{)(.),(,0,),(,1AjiAjicij5.1.5图与网络的数据结构-邻接矩阵表示法对于下图所示的有向图，可以用邻接矩阵表示为0110010100000100100000110对于网络中的权，也可以用类似邻接矩阵的矩阵表示。只是此时一条弧所对应的元素不再是1，而是相应的权而已。无向图的邻接矩阵为对称阵。邻接矩阵举例•n支球队循环赛，每场比赛只计胜负，没有平局.•根据比赛结果排出各队名次.方法1.寻找按箭头方向通过全部顶点的路径.123456312456146325方法2.计算得分：无法排名2,3队,4,5队无法排名!6支球队比赛结果……32，45排名132456合理吗?1队胜4场，2,3队各胜3场，4,5队各胜2场，6队胜1场.123(1)123(2)1234(1)1234(2)1234(3)1234(4)循环比赛的结果——竞赛图3个顶点的竞赛图名次{1，2，3}{(1,2,3)}并列{1,2,3,4}{2,(1,3,4)}{(1,3,4),2}4个顶点的竞赛图名次{(1,2),(3,4)}{1,2,3,4}?竞赛图~每对顶点间都有边相连的有向图123412341234(1)(2)(3)1234(4)竞赛图的3种形式•具有唯一的完全路径，如(1)；•双向连通图——任一对顶点存在两条有向路径相互连通，如(4)；•其他，如(2)，(3).竞赛图的性质•必存在完全路径；•若存在唯一的完全路径，则由它确定的顶点顺序与按得分排列的顺序一致，如(1).4个顶点的竞赛图TeAes)1,,1,1(,级得分向量1~)1,1,2,2()1(TAes级得分向量2~)2,1,2,3()1()2(TAss0001100011000110AEvvEvvajijiij,0,11234(4)双向连通竞赛图G=(V,E)的名次排序邻接矩阵Tnssss),,,(21得分向量TTss)3,3,5,5(,)3,2,3,3()4()3(eAAsskkk)1()(?,)(kskTTss)8,5,8,9(,)5,3,6,8()6()5(TTss)13,9,17,21(,)9,8,13,13()8()7(双向连通竞赛图的名次排序•对于n(3)个顶点的双向连通竞赛图，存在正整数r，使邻接矩阵A满足Ar0，A称素阵.eAAsskkk)1()(0001100011000110A排名为{1，2，4，3}sskk)(,)(归一化后Ts)230.0,167.0,280.0,323.0(,4.1用s排名1234(4){1,2,3,4}?•素阵A的最大特征根为正单根，对应正特征向量s，且seAkkklim000100100100110000001010111000111010A,)1,2,2,3,3,4()1(Ts1234566支球队比赛结果Ts)104.0,150.0,113.0,231.0,164.0,238.0(,232.2排名次序为{1，3，2，5，4，6}32,45排名132456?,)9,12,7,16,10,15()3(Ts,)3,4,3,9,5,8()2(TsTs)16,25,21,32,28,38()4(1:4分;2,3:3分;4,5:2分;6:1分.5.2.1最短路问题5.2最短路问题与最大流问题背景：给定连接若干城市的铁路网，寻求从指定城市到各城去的最短道路。数学模型：图为一赋权图，对任给的，寻求路，使得}),(min{)),((00的路到取自所有vvPPWvvPW其中是路上各边权之和。这一问题可用Dijkstra算法解决。STA1A2A3B1B2C1C2633665874678956例1在纵横交错的公路网中，货车司机希望找到一条从一个城市到另一个城市的最短路。下图表示的是公路网,节点表示货车可以停靠的城市，弧上的权表示两个城市之间的距离(百公里)。那么,货车从城市S出发到达城市T，如何选择行驶路线，使所经过的路程最短?STA1A2A3B1B2C1C2633665874678956分析假设从S到T的最优行驶路线P经过城市C1,则P中从S到C1的子路也一定是从S到C1的最优行驶路线;假设P经过城市C2,则P中从S到C2的子路也一定是从S到C2的最优行驶路线.因此,为得到从S到T的最优行驶路线,只需先求出从S到Ck(k=1,2)的最优行驶路线,就可方便地得到从S到T的最优行驶路线。同样,为了求出从S到Ck(k=1,2)的最优行驶路线,只需要先求出从S到Bj(j=1,2)的最优行驶路线;为了求出从S到Bj(j=1,2)的最优行驶路线,只需要先求出从S到Ai(i=1,2,3)的最优行驶路线.而S到Ai(i=1,2,3)的最优行驶路线是很容易得到的(实际上,此例中S到Ai(i=1,2,3)只有唯一的道路)。分析STA1A2A3B1B2C1C2633665874678956此例中可把从S到T的行驶过程分成4个阶段,即S→Ai(i=1,2或3),Ai→Bj(j=1或2),Bj→Ck(k=1或2),Ck→T.记d(Y,X)为城市Y与城市X之间的直接距离(若这两个城市之间没有道路直接相连，则可以认为直接距离为∞)，用L(X)表示城市S到城市X的最优行驶路线的路长:0;1min,,.2YXLSLXLYdYXXS本例的计算1231123321233112221221216,3,3;min6,8,7107;min5,6,474;min6,8158;min7,9169;min5,6205.LALALALBLALALALALBLALALALALCLBLBLBLCLBLBLBLTLCLCLCSTA1A2A3B1B2C1C2633665874678956所以,从S到T的最优行驶路线的路长为20.进一步分析以上求解过程,可以得到从S到T的最优行驶路线为S→A3→B2→C1→T.这种计算方法在数学上称为动态规划(DynamicProgramming)本例的LINGO求解“CITIES”(城市):一个基本集合(元素通过枚举给出)L:CITIES对应的属性变量(我们要求的最短路长)“ROADS”(道路):由CITIES导出的一个派生集合(请特别注意其用法),由于只有一部分城市之间有道路相连，所以不应该把它定义成稠密集合，将其元素通过枚举给出，这就是一个稀疏集合。D:稀疏集合ROADS对应的属性变量(给定的距离)本例的LINGO求解从模型中还可以看出：这个LINGO程序可以没有目标函数，这在LINGO中，可以用来找可行解(解方程组和不等式组)。在数据段对L进行赋值，只有L(S)=0已知，后面的值为空(但位置必须留出来，即逗号“，”一个也不能少，否则会出错)。如果这个语句直接写成“L=0；”，语法上看也是对的，但其含义是L所有元素的取值全部为0，所以也会与题意不符。本例的LINGO求解虽然集合CITIES中的元素不是数字，但当它以CITIES(I)的形式出现在循环中时，引用下标I却实际上仍是正整数，也就是说I指的正是元素在集合中的位置(顺序)，一般称为元素的索引(INDEX)。在@for循环中的过滤条件里用了一个函数“@index”,其作用是返回一个元素在集合中的索引值，这里@index(S)=1(即元素S在集合中的索引值为1)，所以逻辑关系式“I#GT#@index(S)”可以可以直接等价地写成“I#GT#1”。