Matlab编程-第七章图与网络分析模型选讲.ppt

第七章 图与网络分析模型选讲,一、图论的基本知识,1.图的概念定义 图G(V,E)是指一个二元组(V(G),E(G)，其中:(1)V(G)=v1,v2,vn是非空有限集，称为顶点集，(2)E(G)是V(G)中的元素对(vi,vj)组成的集合称为边集。,图G：,V(G)=v1,v2,v3,v4E(G)=e1,e2,e3,e4,e5,e6e3=(v1,v3),若图G是的边是有方向的，称G是有向图，有向图的边称为有向边或弧。,常用术语边和它的两端点称为互相关联.与同一条边关联的两个端点称为相邻的顶点，与同一个顶点点关联的两条边称为相邻的边.3)端点重合为一点的边称为环.,4)若一对顶点之间有两条以上的边联结，则这些边称为重边5)既没有环也没有重边的图，称为简单图,6)若图G的每一条边e 都赋以一个实数w(e)，称w(e)为边e的权，G连同边上的权称为赋权图,记为：G(V,E,W)，W=w(e)|eE,7)图G的中顶点的个数，称为图G的阶；图中与某个顶点相关联的边的数目，称为该顶点的度。8）完全图：若无向图的任意两个顶点之间都存在着一条边，称此图为完全图。,2.图的矩阵表示邻接矩阵:(以下均假设图为简单图).图G的邻接矩阵是表示顶点之间相邻关系的矩阵：A=(aij)，,若vi与vj相邻,若vi与vj不相邻,或权值，,或，,其中：,v1,v2,v3,v4,v1,v2,v3,v4,5,4,3,1,无向图G,邻接矩阵A=(aij),有向图G,邻接矩阵A=(aij),v1,v2,v3,v4,v1,v2,v3,v4,5,4,3,1,二、最大流问题,定义：设G(V,E)为有向图，若在每条边e上定义一个非负权c，则称图G为一个网络，称c为边e的容量函数，记为c(e)。若在有向图G(V,E)中有两个不同的顶点vs与vt，若顶点vs只有出度没有入度，称vs为图G的源，若顶点vt只有入度没有出度，称为G的汇，若顶点v 既不是源也不是汇，称为v中间顶点。,v2,v4,v1,v3,vs,vt,4,8,3,7,5,7,3,7,设u,v网络G(V,E)的相邻顶点，边(u,v)上的函数f(u,v)称为边(u,v)上的实际流量；若对网络G(V,E)的任意相邻顶点u,v 均成立：0 f(u,v)c(u,v)，称该网络为相容网络。,若v为网络G(V,E)的中间顶点，,有：,网络的总流量为从源vs 流出的总流量：,流入汇vt 总流量：,定义：设网络G(V,E)为相容网络，u,v是G的相邻顶点，G的容量函数为c(u,v)，实际流量函数为f(u,v)，vs 和vt分别为G(V,E)的源和汇，V(f)为从源vs流出的总流量，,若：,则称该网络称为守恒网络。守恒网络中的流 f 称为可行流。,若存在一个可行流f*，使得对所有可行流 f 都有V(f*)V(f)成立，则称f*为最大流。,最大流模型：,s.t:,例7.1分组交换技术在计算机网络中发挥着重要作用，信息从源节点到目的节点不再需要一条固定的路径，而是将其分割为几组，通过不同的路径传输到目的节点，目的节点再重新组合还原文件。现考察如图所示的网络，图中两节点间的数字表示两交换机间可用的带宽，此时从节点1到节点9的最大带宽为多少？,设fij为从vi到vj的实际流量，得一个9阶方阵：F=(fij),记容量矩阵为C=,0 2.5 0 5.6 6.1 0 0 0 00 0 7.1 0 0 3.6 0 0 00 0 0 0 0 0 0 3.4 00 0 0 0 4.9 0 7.4 0 00 2.4 0 0 0 7.2 5.7 0 00 0 3.8 0 0 0 0 5.3 4.50 0 0 0 0 3.8 0 0 6.70 0 0 0 0 0 0 0 7.40 0 0 0 0 0 0 0 0,sets:node/1.9/;arc(node,node):c,f;EndsetsOBJmax=flow;for(node(i)|i#ne#1#and#i#ne#9:sum(node(j):f(i,j)=sum(node(j):f(j,i);sum(node(j):f(1,j)=flow;sum(node(j):f(j,9)=flow;for(arc:bnd(0,f,c);,data:c=0 2.5 0 5.6 6.1 0 0 0 00 0 7.1 0 0 3.6 0 0 00 0 0 0 0 0 0 3.4 00 0 0 0 4.9 0 7.4 0 00 2.4 0 0 0 7.2 5.7 0 00 0 3.8 0 0 0 0 5.3 4.50 0 0 0 0 3.8 0 0 6.70 0 0 0 0 0 0 0 7.40 0 0 0 0 0 0 0 0;enddata,该程序运行结果：最大流：14.2F(1,2)=2.5,F(1,4)=5.6,F(1,5)=6.1,F(2,3)=3.4,F(2,6)=1.5,F(3,8)=3.4,F(4,5)=3.3,F(4,7)=2.3,F(5,2)=2.4,F(5,6)=7,F(6,8)=4,F(6,9)=4.5,F(7,9)=2.3,F(8,9)=7.4,0 2.5 0 5.6 6.1 0 0 0 00 0 7.1 0 0 3.6 0 0 00 0 0 0 0 0 0 3.4 00 0 0 0 4.9 0 7.4 0 00 2.4 0 0 0 7.2 5.7 0 00 0 3.8 0 0 0 0 5.3 4.50 0 0 0 0 3.8 0 0 6.70 0 0 0 0 0 0 0 7.40 0 0 0 0 0 0 0 0 x=1,1,1,2,2,3,4,4,5,5,5,6,6,6,7,7,8,9;y=2,4,5,3,6,8,5,7,2,6,7,3,8,9,6,9,9,9;z=2.5,5.6,6.1,7.1,3.6,3.4,4.9,7.4,2.4,7.2,5.7,3.8,5.3,4.5,3.8,6.7,7.4,0;,Matlab中求最大流的命令：graphmaxflow(f,a,b),clc,clearx=1,1,1,2,2,3,4,4,5,5,5,6,6,6,7,7,8,9;y=2,4,5,3,6,8,5,7,2,6,7,3,8,9,6,9,9,9;z=2.5,5.6,6.1,7.1,3.6,3.4,4.9,7.4,2.4,7.2,5.7,3.8,5.3,4.5,3.8,6.7,7.4,0;f=sparse(x,y,z)flow,flowmat=graphmaxflow(f,1,9)name1(1:9,1)=v;name2=int2str(1:9);name=cellstr(strcat(name1,name2);view(biograph(flowmat,name,ShowWeights,on),三、旅行售货员问题（TSP问题）,一个旅行商，从城市1出发，要遍访城市1,2,3,n各一次，最后返回城市1。若从城市i到j的旅费为cij，问他应按怎样的次序访问这些城市，能使得总旅费最少？用图论语言描述：在赋权图中，寻找一条经过所有节点，并回到原点的最短路。包含图G的每个顶点的路称为哈密顿路；闭的哈密顿路称为哈密顿圈。到目前为止，TSP问题还没有有效解决方法，现有的方法都是寻找近似最优的哈密顿圈，常用方法有边替换法、遗传算法、模拟退火法、蚁群算法等。,引入0-1变量：xij=,1，由第i城市进入第j城市，且i j,0，其它,目标函数：,对规模不大的TSP问题可将其转化为数学规划问题：,j=1,2,3,n,i=1,2,3,n,到此得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP来说并不充分，仅仅是必要条件。例如：,以上两个条件都满足，但它显然不是TSP的解，它存在两个子巡回。,则可以避免产生子巡回。,若在原模型上添加变量ui，并附加下面形式的约束条件：,目标函数：,s.t：,i=2,3,n,i,j=1,2,3,n,j=1,2,3,n,i=1,2,3,n,TSP问题的数学规划模型：,例7.2(TSP问题)已知9个城市间的旅行费用（见表）问他应按怎样的次序访问这些城市，能使得总旅费最少？,0,3.1,5.2,4.3,5.2,6.5,8.8,7.3,5.9,3.1,0,4.8,8.1,9.3,8.7,6.4,4.5,7.2,5.2,4.8,0,7.7,9.5,4.9,5.3,6.6,6.8,4.3,8.1,7.7,0,7.3,11.2,10.8,9.7,8.8,5.2,9.3,9.5,7.3,0,10.5,11.3,7.9,9.4,6.5,8.8,4.9,11.2,10.5,0,6.1,5.8,7.5,8.8,6.4,5.3,10.8,11.3,6.1,0,6.6,4.9,7.3,4.5,6.6,9.7,7.9,5.8,6.6,0,5.8,5.9,7.2,6.8,8.8,9.4,7.5,4.9,5.8,0;,城市编号 1 2 3 4 5 6 7 8 9,1 2 3 4 5 6 7 8 9,s.t：,i,j=1,2,3,n,sets:city/1.9/:u;link(city,city):c,x;endsets OBJmin=sum(link:c*x);for(city(j):sum(city(i)|i#ne#j:x(i,j)=1);for(city(i):sum(city(j)|j#ne#i:x(i,j)=1);for(city(i)|i#gt#1:for(city(j)|j#gt#1#and#i#ne#j:u(i)-u(j)+9*x(i,j)=0);for(link:bin(x);,data:c=0,3.1,5.2,4.3,5.2,6.5,8.8,7.3,5.9,3.1,0,4.8,8.1,9.3,8.7,6.4,4.5,7.2,5.2,4.8,0,7.7,9.5,4.9,5.3,6.6,6.8,4.3,8.1,7.7,0,7.3,11.2,10.8,9.7,8.8,5.2,9.3,9.5,7.3,0,10.5,11.3,7.9,9.4,6.5,8.8,4.9,11.2,10.5,0,6.1,5.8,7.5,8.8,6.4,5.3,10.8,11.3,6.1,0,6.6,4.9,7.3,4.5,6.6,9.7,7.9,5.8,6.6,0,5.8,5.9,7.2,6.8,8.8,9.4,7.5,4.9,5.8,0;enddata,Objective value:49.10000X(1,4)1.000000X(2,1)1.000000 X(3,2)1.000000X(4,5)1.000000 X(5,8)1.000000 X(6,3)1.000000 X(7,6)1.000000 X(8,9)1.000000 X(9,7)1.000000,按如下次序：1,4,5,8,9,7,6,3,2,1 访问这些城市时总费用最小，最小费用：49.1,ei与vi-1和vi关联，称 为图G的,四、最短路问题,道路与轨道：在图G(V,E)中，设,一条道路，k为路长，v0为道路P的起点vt为终点，各边相异的道路称为行迹，顶点不同且边也不同的道路称为轨道（路径）。最短路问题：对赋权图G(V,E,W)，在连接指定起点v0与终点vt的所有轨道P中，寻找一条权数之和最小的轨道。,数学模型：设图G(V,E,W),顶点v0,vtV,边 e E，w(e)为边e的权数，P(v0,vt)是起点为v0终点为vt为任意一条轨道，所有这些轨道的全体记为：S(P)W(P)为轨道P(v0,vt)上各边的权数之和，,最短路问题需要求出：（1）权数之和最小的轨道（2）该轨道的权数之和求解此问题的方法有：Dijkstra算法、floyd算法，遗传算法、模拟退火、蚁群算法等。,Dijkstra算法：（算法具体内容略）是用来求指定两点A与B之间的最短路的，在matlab中使用命令graphshortestpath实现。调用格式：dist,path=graphshortestpath(DG,A,B)dist：A与B之间的最短路的长度 path：A与B之间的最短路的路径 DG：权数邻接矩阵由权数邻接矩阵画图的命令：view(biograph(DG,ShowWeights,on),例7.3 某地10个点v1,v2,v10间的道路连接情况为：,相邻点 距离 相邻点 距离 相邻点 距离 相邻点 距离12:4.2，13:5.6，14:6.5 23:3.5，25:6.5，27:15.2 34:3.8，35:5.4，36:7.645:5.1，46:5.1，47:8.8，48:12.356:4.7，57:5.2，59:7.667:6.3，68:3.9，69:5.278:6.9，79:3.5，710:6.389:6.8，810:5.9，910:5.8,求由v1到v10间的最短路。,clc,clearx=1:8,1:8,1:7,9,4,10;y=2:9,3,5,5:10,4,7,6,7,9,9,10,10,8,10;,w=4.2,3.5,3.8,5.1,4.7,6.3,6.9,6.8,5.6,6.5,5.4,5.1,5.2,3.9,3.5,5.9,6.5,15.2,7.6,8.8,7.6,5.2,6.3,5.8,12.3,0;,相邻点 距离 相邻点 距离 相邻点 距离 相邻点 距离12:4.2，13:5.6，14:6.5 23:3.5，25:6.5，27:15.2 34:3.8，35:5.4，36:7.645:5.1，46:5.1，47:8.8，48:12.356:4.7，57:5.2，59:7.667:6.3，68:3.9，69:5.278:6.9，79:3.5，710:6.389:6.8，810:5.9，910:5.8,W=sparse(x,y,w);B=W+W;dist,path=graphshortestpath(B,1,10)ids=v1,v2,v3,v4,v5,v6,v7,v8,v9,v10;h=view(biograph(W,ids,ShowArrows,off,ShowWeights,on)set(h.Nodes(path),Color,1,0.5,0.5)edges=getedgesbynodeid(h,get(h.Nodes(path),ID);set(edges,LineColor,0,1,0)set(edges,LineWidth,2),dist=21.4000path=1 4 6 8 10,floyd算法：设图G(V,E,W)的权邻接矩阵为：其中 当vi与vj之间没有边相连时，取 当vi与vj之间有边时，取 wij 为该边的权。对于无向图G，邻接矩阵D0是对称矩阵。,(3)递推产生一个矩阵序列D0,D1,Dn(4)为最短路距离矩阵，,floyd算法的步骤：（求有n个节点的图的最短路距离矩阵Dn的步骤）(1)初值k=0，,为vi到vj的最短路的距离。,(2)计算,建立最短路径矩阵R的步骤：（1）,(3)递推产生一个矩阵序列R0,R1,Rn,(4)矩阵R=Rn为最短路径矩阵,查找最短路路径的方法：,若 则 是点vi与到点vj最短路径的途中点，,(1)向起点vi与追溯：,得：,(2)向终点vj与追溯：,得：,(3)点vi与到点vj最短路路径：,例7.4 求右图中加权图的任意两点间的最短距离与最短路径.,0,4,5,6,64,0,35,0,8,5,8,0,6,96,5,6,0,76,3,9,7,0,0,4,5,6,64,0,35,0,8,5,8,0,6,96,5,6,0,76,3,9,7,0,(1)k=1:,0,4,5,6,64,0,9,10,35,9,0,8,5,11,8,0,6,96,10,5,6,0,76,3,11,9,7,0,1 2 3 4 5 6 1 2 1 4 1 6 1 1 3 4 5 1 1 2 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6,1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6,0,4,5,6,64,0,9,10,35,9,0,8,5,11,8,0,6,96,10,5,6,0,76,3,11,9,7,0,(2)k=2:,得:,1 2 3 4 5 6 1 2 1 4 1 6 1 1 3 4 5 1 1 2 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6,1 2 3 4 5 6 1 2 1 4 1 6 1 1 3 4 5 1 1 2 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6,0,4,5,6,64,0,9,10,35,9,0,8,5,11,8,0,6,96,10,5,6,0,76,3,11,9,7,0,(3)k=3:,0 4 5 13 6 6 4 0 9 17 10 3 5 9 0 8 5 11 13 17 8 0 6 9 6 10 5 6 0 7 6 3 11 9 7 0,1 2 3 3 5 6 1 2 1 3 1 6 1 1 3 4 5 1 3 3 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6,(4)k=4:,得:,1 2 3 3 5 6 1 2 1 3 1 6 1 1 3 4 5 1 3 3 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6,0 4 5 13 6 6 4 0 9 17 10 3 5 9 0 8 5 11 13 17 8 0 6 9 6 10 5 6 0 7 6 3 11 9 7 0,1 2 3 3 5 6 1 2 1 3 1 6 1 1 3 4 5 1 3 3 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6,0 4 5 13 6 6 4 0 9 17 10 3 5 9 0 8 5 11 13 17 8 0 6 9 6 10 5 6 0 7 6 3 11 9 7 0,(5)k=5:,0 4 5 12 6 6 4 0 9 16 10 3 5 9 0 8 5 11 12 16 8 0 6 9 6 10 5 6 0 7 6 3 11 9 7 0,1 2 3 5 5 6 1 2 1 5 1 6 1 1 3 4 5 1 5 5 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6,0 4 5 12 6 6 4 0 9 16 10 3 5 9 0 8 5 11 12 16 8 0 6 9 6 10 5 6 0 7 6 3 11 9 7 0,1 2 3 5 5 6 1 2 1 5 1 6 1 1 3 4 5 1 5 5 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6,(6)k=6:,0 4 5 12 6 6 4 0 9 12 10 3 5 9 0 8 5 11 12 12 8 0 6 9 6 10 5 6 0 7 6 3 11 9 7 0,1 2 3 5 5 6 1 2 1 6 1 6 1 1 3 4 5 1 5 6 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6,1 2 3 5 5 6 1 2 1 6 1 6 1 1 3 4 5 1 5 6 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6,0 4 5 12 6 6 4 0 9 12 10 3 5 9 0 8 5 11 12 12 8 0 6 9 6 10 5 6 0 7 6 3 11 9 7 0,故从v4到v2的最短路：,途中点:v6,从v6向前追溯：,得:v4 v6,0 4 5 12 6 6 4 0 9 12 10 3 5 9 0 8 5 11 12 12 8 0 6 9 6 10 5 6 0 7 6 3 11 9 7 0,1 2 3 5 5 6 1 2 1 6 1 6 1 1 3 4 5 1 5 6 3 4 5 6 1 1 3 4 5 6 1 2 1 4 5 6,得:v4 v6,从v6向后追溯：,得:v4 v6 v2,floyd算法的程序实现方法：(1)输入带权的邻接矩阵：,(2)赋初值：对所有的i与j，d(i,j)w(i,j),r(i,j)j,k 1,(3)更新d(i,j)与r(i,j)：对所有的i与j，若d(i,k)+d(k,j)d(i,j),则d(i,j)d(i,k)+d(k,j),r(i,j)k,(4)若k=n停止；否则kk+1 转(3),例7.5 出租车的最短行驶路线问题某地的出租车公司为了更好地服务，向顾客承诺“出租车走最短的行驶路线，方便快捷。”乘客上车后告知司机目的地，出租车电脑就可以计算出到达目的地的最短行驶路线，下图给出该地的交通路线示意图，要求：(1)编写用floyd算法求50个节点中任意两个节点间的最短路径matlab函数。(2)调用所编写的函数，求出从标号为22的地点到标号为44的地点的最短行驶路线。,function d,path=floydg(a,sp,ep)n=size(a,1);D=a;R=zeros(n);for j=1:n R(:,j)=j;endfor k=1:n for i=1:n for j=1:n if D(i,k)+D(k,j)D(i,j)D(i,j)=D(i,k)+D(k,j);R(i,j)=k;end end endend,解(1),c0=R(sp,ep);L1=c0;c=c0;while R(sp,c)=c c=R(sp,c);L1=c,L1;endb=c0;L2=;while R(b,ep)=ep b=R(b,ep);L2=L2,b;endd=D(sp,ep);path=sp,L1,L2,ep;end,(2)输入带权的邻接矩阵：D,命令窗口：d,path=floydg(D,22,44),d=2410path=Columns 1 through 12 22 24 28 31 33 38 41 42 43 47 45 44,五、最小生成树问题,树：连通且不含圈的无向图称为树常用T表示.树中的边称为树枝.树中度为1的顶点称为树叶.,支撑树：设图G(V,E)，若T是树，且称树T是图G的支撑（生成）树。,最小生成树：赋权连通图G的所有支撑树中，其各边权之和最小的支撑树，称为连通图G的最小生成树。解决最小生成树的常用方法：克鲁斯卡尔算法、普利姆算法。,普利姆（Prim）算法：,设置两个集合P和Q，其中P、Q分别用于存放最小生成树的顶点和边，P的初值为P=v1，Q的初值为Q=。普利姆算法的基本思想：从所有的边中，选取一条具有最小权值的边uv，将顶点v加入到集合P中，将边uv加入到集合Q中，不断重复下去，直到P=V中止。,普利姆（Prim）算法：,设置两个集合T和Q，其中T、Q分别用于存放最小生成树的顶点和边，T的初值为T=v1，Q的初值为Q=。普利姆算法的基本思想：从所有 的边uv中，,选取一条具有最小权值的边uv，将顶点v加入到集合T中，再将从集合S中剔除，将边uv加入到集合Q中，不断重复下去，直到T=V中止。,T=v2,S=v1,v3,v4,v5,v6,v7,Q=v2v6,Q=v2v6,v2v1,T=v2,v6,T=v2,v6,v1,T=v2,v6,v1,v3,Q=v2v6,v2v1,v1v3,T=v2,v6,v1,v3,v5,Q=v2v6,v2v1,v1v3,v3v5,T=v2,v6,v1,v3,v5,v7,T=v2,v6,v1,v3,v5,v7,v4,最生成小树为Tree=v2v6,v2v1,v1v3,v3v5,v6v7,v7v4 最小生成树的权为27。,例7.6 求右图的最小生成树,Q=v2v6,v2v1,v1v3,v3v5,v6v7,Q=v2v6,v2v1,v1v3,v3v5,v6v7,v7v4,普利姆（Prim）算法的matlab实现：,function A,B,Tch=primg(w,a)%w:权矩阵，a：起始点编号n=length(w);T=a;S=setdiff(1:n,T);A=;B=;L=;w(w=0)=inf;k1=1;k2=n-1;while k1n min=inf;for m1=1:k1 for m2=1:k2 t=w(T(m1),S(m2);if tmin min=t;s1=T(m1);s2=S(m2);end end end,T=T,s2;S=setdiff(S,s2);A=A,s1;B=B,s2;L=L,min;k1=length(T);k2=length(S);endTch=sum(L);end,例7.7 某单位有10个下属部门，均不在同一地点办公，为了实现部门之间的资源共享，该单位打算对原有网络进行改造，将所有各部门通过光缆连接组成园区网。根据前期的考察预测，各部门间的光缆连接费用如下表，试问该单位应如何铺设光纤能使得成本最低，且保证所属单位之间的连通？,clc,clearw=0,33,51,52,38,61,61,49,53,51;33,0,44,71,48,51,60,50,49,41;51,44,0,66,43,58,62,34,35,55;52,71,66,0,62,56,61,37,49,48;38,48,43,62,0,55,52,40,28,49;61,51,58,56,55,0,53,39,49,49;61,60,62,61,52,53,0,55,50,56;49,50,34,37,40,39,55,0,64,46;53,49,35,49,28,49,50,64,0,48;51,41,55,48,49,49,56,46,48,0a=input(输入起始点标号a=);A,B,tch=primg(w,a),A=1 1 5 9 3 8 8 2 9B=2 5 9 3 8 4 6 10 7tch=335,