《matlab编程 - 第七章 图与网络分析模型选讲》由会员分享，可在线阅读，更多相关《matlab编程 - 第七章 图与网络分析模型选讲（61页珍藏版）》请在金锄头文库上搜索。
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是有向图，有向图的 边称为有向边或弧。 常用术语 1)边和它的两端点称为互相关联. 2)与同一条边关联的两个端点称 为相邻的顶点，与同一个顶点 1)点关联的两条边称为相邻的边. 2)3)端点重合为一
2、点的边称为环. 4) 若一对顶点之间有两条以上的边联结，则这些边 称为重边 5)既没有环也没有重边的图，称为简单图 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 6) 若图G的每一条边e 都赋以一个实数w(e)， 称w(e)为边e的权，G连同边上的权称为赋权图 , 记为：G(V,E,W)， W=w(e)| eE v1 v2 v3 v4 5 3 2 7) 图G的中顶点的个数， 称为图G的阶；图中与某 个顶点相关联的边的数目， 称为该顶点的度。 8）完全图：若无向图的任 意两个顶点之间都存在着一 条边，称此图为完全图。 2.图的矩阵表示 邻接矩阵: (以下均假设图为简单图).
3、图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的汇
4、， 若顶点v 既不是源也不是汇，称为v中间顶点。 v2 v4 v1 v3 vs vt 4 8 3 7 5 7 3 7 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)的中间顶点， 有： v2 v4 v1 v3 vs vt 4 8 3 7 5 7 3 7 网络的总流量为从源vs 流出的总流量： 流入汇vt 总流量： 定义：设网络G(V,E)为相容
5、网络，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分组交换技术在计算机网络中发挥着重要作用，信 息从源节点到目的节点不再需要一条固定的路径，而是 将其分割为几组，通过不同的路径传输到目的节点，目 的节点再重新组合还原文件。现考察如图所示的网络， 图中两节点间的数字表示两交换机间可用的带
6、宽，此时 从节点1到节点9的最大带宽为多少？ v2 v5 v1v3 v8 2.5 v9 v4 v7 v6 7.1 3.4 6.1 5.62.4 3.6 3.8 7.4 4.9 5.7 7.2 5.3 4.5 3.8 6.7 7.4 设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 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
7、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 v2 v5 v1v3 v8 2.5 v9 v4 v7 v6 7.1 3.4 6.1 5.62.4 3.6 3.8 7.4 4.9 5.7 7.2 5.3 4.5 3.8 6.7 7.4 sets: node/19/; 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
8、; 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 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
9、.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, v2 v5 v1v3 v8 2.5 v9 v4 v7 v6 7.1 3.4 6.1 5.62.4 3.6 3.8 7.4 4.9 5.7 7.2 5.3 4.5 3.8 6.7 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
10、 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 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中求最大流的命令： graphmaxf
11、low(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,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(bio
12、graph(flowmat,name,ShowWeights,on) 三、旅行售货员问题（TSP问题） 一个旅行商，从城市1出发，要遍访城市1,2,3,n 各一次，最后返回城市1。若从城市i到j的旅费为cij， 问他应按怎样的次序访问这些城市，能使得总旅费 最少？ 用图论语言描述：在赋权图中，寻找一条经过所有 节点，并回到原点的最短路。 包含图G的每个顶点的路称为哈密顿路；闭的哈密 顿路称为哈密顿圈。 到目前为止，TSP问题还没有有效解决方法，现有 的方法都是寻找近似最优的哈密顿圈，常用方法有边 替换法、遗传算法、模拟退火法、蚁群算法等。 引入0-1变量：xij= 1，由第i城市进入第j城市，
13、且i j 0，其它 目标函数： 对规模不大的TSP问题可将其转化为数学规划问题： j=1,2,3,n i=1,2,3,n 1 2 3 4 5 6 到此得到了一个模型，它是一个指派问题的整数规 划模型。但以上两个条件对于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个城市间的旅行费用（见表
14、） 问他应按怎样的次序访问这些城市，能使得总旅费最 少？ 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,
15、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 /19/: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)=8); for(city(i)|
