图论知识及运用举例

图论知识及运用举例1 1概论图论中的“图”是指某类具体事物和这些事物之间的联系。如果我们用点表示这些具体事物，用连接两点的线段(直的或曲的)表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。 图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求图是运筹学(OperationsResearch中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域。下面将要讨论最短路问题、最大流问题、最小费用流问题和匹配问题等。2 2图的基本概念2.1无向图一个无向图(undirectedgraph)G 是由一个非空有限集合 V(G)和 V(G)中某些元素的无序对集合 E(G)构成的二元组，记为 G=(V(G),E(G)。其中V(G)=v1,v2,，Vn称为图 G 的顶点集(vertexset)或节点集(nodeset,V(G)中的每一个元素M(i=1,2,，n)称为该图的一个顶点(vertex)或节点(node);E(G)=e,e2,，嘴称为图 G 的边集(edgeset),E(G)中的每一个元素 Q(即V(G)中某两个元素Vi,Vj的无序对)记为ek=(Vi,Vj)或ek=VM=VjM(k=1,2,，m),被称为该图的一条从va4的边(edge)。当边4=VM时，称M,vj为边Q的端点，并称vj与vi相邻(adjacent)；边4称为与顶点vi,vj关联(incident)。如果某两条边至少有一个公共端点，则称这两条边在图 G 中相邻。边上赋权的无向图称为赋权无向图或无向网络(undirectednetwork)。我们对图和网络不作严格区分，因为任何图总是可以赋权的。一个图称为有限图，如果它的顶点集和边集都有限。图 G 的顶点数用符号|V|或(G)表示，边数用|E|或 aG)表示。当讨论的图只有一个时，总是用 G 来表示这个图。从而在图论符号中我们常略去字母 G,例如，分别用 V,E,v 和名代替 V(G),E(G),v(G)和G)。端点重合为一点的边称为环(loop)。一个图称为简单图(simplegraph),如果它既没有环也没有两条边连接同一对顶点。2.2有向图定义一个有向图(directedgraph或digraph)G 是由一个非空有限集合 V和 V 中某些元素的有序对集合 A 构成的二元组，记为 G=(V,A)。其中V=v1,V2,，Vn称为图 G 的顶点集或节点集，V 中的每一个元素Vi(i=1,2，n)称为该图的一个顶点或节点；A=a1,a2,，am称为图 G 的弧集(arcset),A 中的每一个元素ak(即 V 中某两个元素vi,vj的有序对)记为ak=(M,Vj)或ak=MVj(k=1,2，n),被称为该图的一条从Vi到Vj的弧(arc)。当弧ak=vM时，称Vi为ak的尾(tail),Vj为ak的头(head),并称弧ak为M的出弧(outgoingarc),为vj的入弧(incomingarc)。对应于每个有向图 D,可以在相同顶点集上作一个图条弧，G 有一条有相同端点的边与之相对应。 这个图称为给定任意图 G对于它的每个边，给其端点指定一个顺序,此得到一个有向图，这样的有向图称为 G 的一个定向图。以下若未指明“有向图”三字，“图”字皆指无向图。2.3完全图、二分图每一对不同的顶点都有一条边相连的简单图称为完全图个顶点的完全图记为(若 V(G)=XUY,XY=，|X|Y|#0(这里|X|表示集合X中的元素个数)，X中无相邻顶点对，Y中亦然，则称 G 为二分图(bipartitegraph)；特别地，若寸 xWX,VyWY,则 xyWE(G),则称 G 为完全二分图，记成K凶,Y1。2.4子图图H叫做图 G 的子图(subgraph)subgraph), ,记作 H=G,如果 V(H)=V(G),E(H)cE(G)0若H是 G 的子图，则 G 称为H的母图。G 的支撑子图(spanningsubgraph又成生成子图)是指满足 V(H)=V(G)的子图H。2.5顶点的度设 vWV(G),G 中与v关联的边数(每个环算作两条边)称为v的度(degree)记作 d(v)。若 d(v)是奇数，称v是奇顶点(oddpoint);d(v)是偶数，称v是偶顶G,使得对于D的每D的基础图。反之，从而确定一条弧，由(completegraphbn点(evenpoint)。关于顶点的度，我们有如下结果：1.%2、d(v)=2；v.V(ii)任意一个图的奇顶点的个数是偶数。2.6图与网络的数据结构网络优化研究的是网络上的各种优化模型与算法.为了在计算机上实现网络优化的算法，首先我们必须有一种方法(即数据结构)在计算机上来描述图与网络。一般来说，算法的好坏与网络的具体表示方法，以及中间结果的操作方案是有关系的。这里我们介绍计算机上用来描述图与网络的5种常用表示方法：邻接矩阵表示法、关联矩阵表示法、弧表表示法、邻接表表示法和星形表示法。在下面数据结构的讨论中，我们首先假设 G=(V,A)是一个简单有向图，|V|=n,|A|=m,并假设 V 中的顶点用自然数 1,2,，n 表示或编号，A 中的弧用自然数 1,2,，m 表示或编号。对于有多重边或无向网络的情况，我们只是在讨论完简单有向图的表示方法之后，给出一些说明。(i)邻接矩阵表示法邻接矩阵表示法是将图以邻接矩阵(adjacencymatrix)的形式存储在计算机中。图 G=(V,A)的邻接矩阵是如下定义的：C 是一个nn的0-1 矩阵，即C=(Gj)nnW0,1nZ(i,j)WA,Gi=ja(i,j)更A.也就是说，如果两节点之间有一条弧，则邻接矩阵中对应的元素为1;否则为0。可以看出，这种表示法非常简单、直接。但是，在邻接矩阵的所有 n2个元素中，只有m个为非零元。如果网络比较稀疏，这种表示法浪费大量的存储空间，从而增加了在网络中查找弧的时间。(ii)关联矩阵表示法关联矩阵表示法是将图以关联矩阵(incidencematrix)的形式存储在计算机中.图 G=(V,A)的关联矩阵B是如下定义的：B是一个nm的矩阵，即8=(为).式1,0,1nm,1,jV,k=(i,j)-A,以=1,司 WV,k=(j,i)wA,0,其它.也就是说，在关联矩阵中，每行对应于图的一个节点，每列对应于图的一条弧。如果一个节点是一条弧的起点，则关联矩阵中对应的元素为1;如果一个节点是一条弧的终点，则关联矩阵中对应的元素为1;如果一个节点与一条弧不关联，则关联矩阵中对应的元素为0。对于简单图，关联矩阵每列只含有两个非零元(一个十1,一个_1)。可以看出，这种表示法也非常简单、直接。止匕外，还有邻接表表示法，弧表示法，星形表示法等。2.7轨与连通W7001Vle2ekvk,其中ewE(G),1EiEk,VjwV(G),0jk,e与Vi,Vi关联，称 W 是图 G 的一条道路(walk),k 为路长，顶点v和Vk分别称为 W的起点和终点，而V1,V2,，V称为它的内部顶点。若道路 W 的边互不相同，则 W 称为迹(trail)。若道路 W 的顶点互不相同，则 W 称为轨(path)o称一条道路是闭的，如果它有正的长且起点和终点相同。起点和终点重合的轨叫做圈(cycle)若图 G 的两个顶点u,V间存在道路，则称u和V连通(connected)u,V间的最短轨的长叫做u,v间的距离。记作 d(u,v)0若图 G 的任二顶点均连通，则称 G 是连通图。显然有：(i)图P是一条轨的充要条件是P是连通的，且有两个一度的顶点，其余顶点的度为2;(ii)图 C 是一个圈的充要条件是 C 是各顶点的度均为2的连通图。3应用一最短路问题两个指定顶点之间的最短路径问题如下：给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。以各城镇为图 G 的顶点，两城镇间的直通铁路为图 G 相应两顶点间的边，得图 G。对 G 的每一边 e,赋以一个实数 w(e)直通铁路的长度，称为e的权，得到赋权图 GoG 的子图的权是指子图的各边的权和。 问题就是求赋权图 G 中指定的两个顶点u,V0间的具最小权的轨。这条轨叫做u,V0间的最短路，它的权叫做u0,V0间的距离，亦记作d(u0,v。)。求最短路已有成熟的算法：迪克斯特拉(Dijkstra)算法，其基本思想是按距u。从近到远为顺序，依次求得u。到 G 的各顶点的最短路和距离，直至V0(或直至 G 的所有顶点)，算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。下面是该算法。(i)令l(u0)=0,对vu0,令 l(v)=8,S0=u0,i=0(ii)对每个vwS(S=VS),用minl(v),l(u)-w(uv)u.Si代替 l(v)。计算 minl(v),把达到这个最小值的一个顶点记为 u 卡,令v.SS卅=SUUiQ。.若 i=|V|-1,停止；若 i|V|-1,用 i+1 代替 i,转(ii)。算法结束时，从小到各顶点v的距离由v的最后一次的标号 l(v)给出。在v进入Si之前的标号 l(v)叫T标号，v进入S时的标号 l(v)叫P标号。算法就是不断修改各项点的T标号，直至获得P标号。若在算法运行过程中，将每一顶点获得P标号所由来的边在图上标明，则算法结束时，Uo至各项点的最短路也在图上标本出来了。例1某公司在六个城市c1,c2,，c6中有分公司，从到9的直接航程票价记在下述矩阵的(i,j)位置上。(g 表示无直接航路)，请帮助该公司设计一张城市G到其它城市间的票价最便宜的路线图。一 0 50O0O04025105001520od25001501020004020100102525002010055-1025O0O025550_用矩阵an殉(n 为顶点个数)存放各边权的邻接矩阵，行向量 pb、index1、index2、d 分别用来存放P标号信息、标号顶点顺序、标号顶点索引、最短通路的值。其中分量1当第i顶点已标号pb=；0当第i顶点未标号index?存放始点到第 i 点最短通路中第 i 顶点前一顶点的序号；d(i)存放由始点到第 i 点最短通路的值。求第一个城市到其它城市的最短路径的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:length(a)=0;pb(1)=1;index1=1;index2=ones(1,length(a);d(1:length(a)=M;d(1)=0;temp=1;whilesum(pb)=2index=index(1);endindex2(temp)=index;endd,index1,index2每对顶点之间的最短路径计算赋权图中各对顶点之间最短路径，显然可以调用Dijkstra算法。具体方法是：每次以不同的顶点作为起点，用Dijkstra算法求出从该起点到其余顶点的最短路径，反复执行n次这样的操作，就可得到从每一个顶点到其它顶点的最短路径。这种算法的时间复杂度为O(n3)。第二种解决这一问题的方法是由FloydRW提出的算法，称之为Floyd算法。假设图 G 权的邻接矩阵为A,a11a2a1na21a22a2nA0=:_an1an2ann_来存放各边长度，其中：aH=0i=1,2，n;a。=gi,j 之间没有边，在程序中以各边都不可能达到的充分大的数代a。=WjWj是 i,j 之间边的长度，i,j=1,2n。对于无向图，A 是对称矩阵，aj=2/。Floyd算法的基本思想是：递推产生一个矩阵序列A,A,，人，其中Ak(i,j)表示从顶点Vi到顶点Vj的路径上所经过的顶点序号不大于 k 的最短路径长度。计算时用迭代公式：Ak(i,j)=min(Ak(i,j)A(i,k)A(k,j)k 是迭代次数,i,j,k=1,2,，n。最后，当 k=n 时，人即是各顶点之间的最短通路值。例2最短路问题(SPPshortestpathproblem一名货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。Floyd算法的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);b=a+a;path=zeros(length(b);fork=1:6fori=1:6forj=1:6ifb(i,j)b(i,k)+b(k,j)b(i,j)=b(i,k)+b(k,j);path(i,j)=k;endendendendb,path4 4树基本概念连通的无圈图叫做树， 记之为 To 若图 G 满足 V(G)=V(T),E(T)uE(G),则称T是 G 的生成树。图 G 连通的充分必要条件为 G 有生成树。一个连通图的生成树的个数很多，用E(G)表示 G 的生成树的个数，则有公式公式(Caylay)i(Kn)=nn/。公式.(G)=.(Ge)(Ge)。其中 Ge 表示从 G 上删除边 e,G.e 表示把e的长度收缩为零得到的图。应用一连线问题欲修筑连接n个城市的铁路，已知 i 城与 j 城之间的铁路造价为Cj,设计一个线路图，使总造价最低。连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。构造最小生成树的两种常用算法：prim算法和Kruskal算法。这里重点介绍prim算法。设置两个集合P和 Q,其中P用于存放 G 的最小生成树中的顶点， 集合 Q 存放 G 的最小生成树中的边。令集合P的初值为P=必(假设构造最小生成树时，从顶点v1出发)，集合Q的初值为Q=60prim算法的思想是，从所有peP,vEV-P的边中，选取具有最小权值的边 pv,将顶点v加入集合P中，将边 pv 加入集合 Q 中，如此不断重复，直到 P=V 时，最小生成树构造完毕，这时集合 Q 中包含了最小生成树的所有边。prim算法如下：P=vj,Q=中；pv=minw(pv,pP,vV-PP=PvQ=Qpvend例3用prim算法求右图的最小生成树。我们用result3M的第一、二、三行分别表示生成树边的起点、终点、权集合Matlab程序如下：(ii)whileP=Vclc;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);whilelength(result)=length(a)-1temp=a(p,tb);temp=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)=;endresultEulerEuler图和HamiltonHamilton图基本概念定义经过 G 的每条边的迹叫做 G 的Euler迹； 闭的Euler迹叫做Euler回路或E回路；含Euler回路的图叫做Euler直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。定理(i)G 是Euler图的充分必要条件是 G 连通且每顶点皆偶次。dG 是Euler图的充分必要条件是 G 连通且 G=UCi,G是圈，i1E(C”E(Cj)=G(ij)。G 中有Euler迹的充要条件是 G 连通且至多有两个奇次点。定义包含 G 的每个顶点的轨叫做Hamilton(哈密顿)轨； 闭的Hamilton轨叫做Hamilton圈或H圈；含Hamilton圈的图叫做Hamilton图。直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。6.2Euler回路的Fleury算法1921年，Fleury给出下面的求Euler回路的算法。FleuryFleury算法：10 0Vv0eV(G),令亚0=v0O2假设迹WieM已经选定，那么按下述方法从E-s,，e中选取边ei书:e.和M相关联；（ii）除非没有别的边可选择，否则e+不是Gi=G-e：,e的割边（cutedge）（所谓割边是一条删除后使连通图不再连通的边）。3。当第2步不能再执行时，算法停止。6.3Hamilton例题例4从北京（Pe）乘飞机到东京（T）、纽约（N）、墨西哥城（M）、伦敦（L）、巴黎（Pa出城市做旅游，每城市恰去一次再回北京，应如何安排旅游线，使旅程最短？各城市之间的航线距离如下表：LMNPaPeTLP5635215160M5621577870Nr35r213668168Pa2157365161Per5178685113T6070686113解：编写程序如下：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=51:46;L=length(c1);flag=1;whileflag0flag=0;form=1:L-3forn=m+2:L-1ifa(c1(m),c1(n)+a(c1(m+1),c1(n+1)0flag=0;form=1:L-3forn=m+2:L-1ifa(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);endendendendsum1=0;fori=1:L-1sum1=sum1+a(c1(i),c1(i+1);endifsum1sumsum=sum1;circle=c1;endcircle,sum