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

1、第七章 图与网络分析模型选讲,一、图论的基本知识,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,v4 E(G)= e1,e2,e3,e4,e5,e6 e3=(v1,v3),若图G是的边是有方向的，称G是有向图，有向图的边称为有向边或弧。,常用术语 边和它的两端点称为互相关联. 与同一条边关联的两个端点称 为相邻的顶点，与同一个顶点 点关联的两条边称为相邻的边. 3)端点重合为一点的边称为环.,4)

2、 若一对顶点之间有两条以上的边联结，则这些边称为重边 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,

3、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网络

4、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 *，使得对所有可行流

5、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 0 0 0 7.1 0 0 3.6 0 0 0 0 0 0 0 0 0 0 3.4 0 0 0 0 0

6、4.9 0 7.4 0 0 0 2.4 0 0 0 7.2 5.7 0 0 0 0 3.8 0 0 0 0 5.3 4.5 0 0 0 0 0 3.8 0 0 6.7 0 0 0 0 0 0 0 0 7.4 0 0 0 0 0 0 0 0 0,sets: node/1.9/; arc(node,node):c,f; Endsets OBJmax=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

7、; for(arc:bnd(0,f,c);,data: c= 0 2.5 0 5.6 6.1 0 0 0 0 0 0 7.1 0 0 3.6 0 0 0 0 0 0 0 0 0 0 3.4 0 0 0 0 0 4.9 0 7.4 0 0 0 2.4 0 0 0 7.2 5.7 0 0 0 0 3.8 0 0 0 0 5.3 4.5 0 0 0 0 0 3.8 0 0 6.7 0 0 0 0 0 0 0 0 7.4 0 0 0 0 0 0 0 0 0; enddata,该程序运行结果： 最大流：14.2 F(1,2)=2.5, F(1,4)=5.6,F(1,5)=6.1,F(2,3)=3.4,F

8、(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 0 0 0 7.1 0 0 3.6 0 0 0 0 0 0 0 0 0 0 3.4 0 0 0 0 0 4.9 0 7.4 0 0 0 2.4 0 0 0 7.2 5.7 0 0 0 0 3.8 0 0 0 0 5.3 4.5 0 0 0 0 0 3.8 0 0 6.7 0 0 0 0 0 0 0 0 7.4 0 0 0 0 0 0 0 0

9、 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,clear 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,

10、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， 问他应按怎样的次序访问这些城市，能

11、使得总旅费最少？ 用图论语言描述：在赋权图中，寻找一条经过所有节点，并回到原点的最短路。 包含图G的每个顶点的路称为哈密顿路；闭的哈密顿路称为哈密顿圈。 到目前为止，TSP问题还没有有效解决方法，现有的方法都是寻找近似最优的哈密顿圈，常用方法有边替换法、遗传算法、模拟退火法、蚁群算法等。,引入0-1变量：xij=,1，由第i城市进入第j城市，且i j,0，其它,目标函数：,对规模不大的TSP问题可将其转化为数学规划问题：,j=1,2,3,n,i=1,2,3,n,到此得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP来说并不充分， 仅仅是必要条件。 例如：,以上两个条件都满

12、足，但它显然不是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,

13、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,

14、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

15、.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,

16、 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.10000 X( 1, 4) 1.000000 X( 2, 1) 1.000000 X( 3, 2) 1.000000 X( 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

17、,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)上各边

18、的权数之和，,最短路问题需要求出： （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.6 45