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

第七章图与网络分析模型选讲一、图论的基本知识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)与同一条边关联的两个端点称为相邻的顶点，与同一个顶点点关联的两条边称为相邻的边.3)端点重合为一点的边称为环.4)若一对顶点之间有两条以上的边联结，则这些边称为重边．5)既没有环也没有重边的图，称为简单图．v1v2v3v4v5e1e2e3e4e5e66)若图G的每一条边e都赋以一个实数w(e)，称w(e)为边e的权，G连同边上的权称为赋权图,记为：G(V,E,W)，W={w(e)|e∈E}v1v2v3v45327)图G的中顶点的个数，称为图G的阶；图中与某个顶点相关联的边的数目，称为该顶点的度。8）完全图：若无向图的任意两个顶点之间都存在着一条边，称此图为完全图。2.图的矩阵表示邻接矩阵:(以下均假设图为简单图).图G的邻接矩阵是表示顶点之间相邻关系的矩阵：A=(aij)，01ija若vi与vj相邻若vi与vj不相邻或权值，或∞，其中：v1v2v3v40010001111010110Av1v2v3v45431040314305150A无向图G邻接矩阵A=(aij)有向图G邻接矩阵A=(aij)v1v2v3v4v1v2v3v454310000001110000010A00314050A二、最大流问题定义：设G(V,E)为有向图，若在每条边e上定义一个非负权c，则称图G为一个网络，称c为边e的容量函数，记为c(e)。若在有向图G(V,E)中有两个不同的顶点vs与vt，若顶点vs只有出度没有入度，称vs为图G的源，若顶点vt只有入度没有出度，称为G的汇，若顶点v既不是源也不是汇，称为v中间顶点。v2v4v1v3vsvt48375737v2v4v1v3vsvt48375737设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)的中间顶点，Vuvuf),(Vwwvf),(有：v2v4v1v3vsvt48375737网络的总流量为从源vs流出的总流量：VwswvffV),()(流入汇vt总流量：VutvuffV),()(定义：设网络G(V,E)为相容网络，u,v是G的相邻顶点，G的容量函数为c(u,v)，实际流量函数为f(u,v)，vs和vt分别为G(V,E)的源和汇，V(f)为从源vs流出的总流量，若：Vuuvf),(Vuvuf),(ttssvvfVvvvvvfV),(,,0),(则称该网络称为守恒网络。守恒网络中的流f称为可行流。若存在一个可行流f*，使得对所有可行流f都有V(f*)≥V(f)成立，则称f*为最大流。最大流模型：)(maxfVs.t:VvijVvjijjvvfvvf),(),(,),(0ijjicvvf),(VvvjisivvfV),(Vvvvvitsi,,,0tvvfV),(例7.1分组交换技术在计算机网络中发挥着重要作用，信息从源节点到目的节点不再需要一条固定的路径，而是将其分割为几组，通过不同的路径传输到目的节点，目的节点再重新组合还原文件。现考察如图所示的网络，图中两节点间的数字表示两交换机间可用的带宽，此时从节点1到节点9的最大带宽为多少？v2v5v1v3v82.5v9v4v7v67.13.46.15.62.43.63.87.44.95.77.25.34.53.86.77.4设fij为从vi到vj的实际流量，得一个9阶方阵：F=(fij)记容量矩阵为C=02.505.66.10000007.1003.600000000003.4000004.907.40002.40007.25.700003.800005.34.5000003.8006.7000000007.4000000000v2v5v1v3v82.5v9v4v7v67.13.46.15.62.43.63.87.44.95.77.25.34.53.86.77.4)(maxfVVujiVuijjjff9),(9,1,01),(ifViifV,0CF..tssets:node/1..9/;arc(node,node):c,f;Endsets[OBJ]max=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));)(maxfVVujiVuijjjff9),(9,1,01),(ifViifV,0CF..tsdata:c=02.505.66.10000007.1003.600000000003.4000004.907.40002.40007.25.700003.800005.34.5000003.8006.7000000007.4000000000;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,v2v5v1v3v82.5v9v4v7v67.13.46.15.62.43.63.87.44.95.77.25.34.53.86.77.402.505.66.10000007.1003.600000000003.4000004.907.40002.40007.25.700003.800005.34.5000003.8006.7000000007.4000000000x=[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≠j0，其它目标函数：niniijijxcz11min对规模不大的TSP问题可将其转化为数学规划问题：,11niijxj=1,2,3,…,n,11njijxi=1,2,3,…,n123456到此得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于TSP来说并不充分，仅仅是必要条件。例如：以上两个条件都满足，但它显然不是TSP的解，它存在两个子巡回。则可以避免产生子巡回。若在原模型上添加变量ui，并附加下面形式的约束条件：，1nnxuuijji.12nji,20nui目标函数：niniijijxcz11mins.t：,11niijx,11njijx,1nnxuuijji,2nji,20nuii=2,3,…,n,1,0ijxi,j=1,2,3,…,nj=1,2,3,…,ni=1,2,3,…,nTSP问题的数学规划模型：例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;城市编号1234567891234567899191miniiijijxczs.t：,191iijx,191jijx,89ijjixuu,70iu,1,0ijx,ji),92(ji,jii,j=1,2,3,…,nsets:city/1..9/:u;link(city,city):c,x;endsets[OBJ]min=@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)|i#gt#1:u(I)=7;u(i)=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