第七章 图与网络分析模型选讲

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,v4E(G)= e1,e2,e3,e4,e5,e6e3=(v1,v3)1若图若图G的边是有方向的，称的边是有方向的，称G是有向图，有向图的边是有向图，有向图的边称为有向边或弧。称

2、为有向边或弧。常用术语常用术语 边和它的两端点称为互相边和它的两端点称为互相关联关联. 与同一条边关联的两个端点称与同一条边关联的两个端点称为为相邻相邻的顶点，与同一个顶点的顶点，与同一个顶点点关联的两条边称为点关联的两条边称为相邻相邻的边的边.3)端点重合为一点的边称为端点重合为一点的边称为环环.4) 若一对顶点之间有两条以上的边联结，则这些边若一对顶点之间有两条以上的边联结，则这些边称为称为重边重边5)既没有环也没有重边的图，称为既没有环也没有重边的图，称为简单图简单图 v1v2v3v4v5e1e2e3e4e5e626) 若图若图G的每一条边的每一条边e 都赋以一个实数都赋以一个实数w(e

3、)，称称w(e)为边为边e的的权权，G连同边上的权称为连同边上的权称为赋权图赋权图 ,记为：记为：G(V,E,W)， W=w(e)| eEv1v2v3v45327) 图图G的中顶点的个数，的中顶点的个数， 称为图称为图G的阶；图中与某的阶；图中与某个顶点相关联的边的数目，个顶点相关联的边的数目，称为该顶点的度。称为该顶点的度。8）完全图：若无向图的任）完全图：若无向图的任意两个顶点之间都存在着意两个顶点之间都存在着一条边，称此图为完全图。一条边，称此图为完全图。32.图的矩阵表示图的矩阵表示邻接矩阵邻接矩阵: (以下均假设图为简单图以下均假设图为简单图). 图图G的邻接矩阵是表示顶点之间相邻关

4、系的矩阵：的邻接矩阵是表示顶点之间相邻关系的矩阵： A=(aij)， 01ija若若vi与与vj相邻相邻若若vi与与vj不相邻不相邻或权值，或权值，或或，其中：其中：4v1v2v3v4 0010001111010110Av1v2v3v45431 040314305150A无向图无向图G邻接矩阵邻接矩阵A=(aij)5有向图有向图G邻接矩阵邻接矩阵A=(aij)v1v2v3v4v1v2v3v45431 0000001110000010A 00314050A6二、最大流问题二、最大流问题定义：设定义：设G(V,E)为有向图，若在每条边为有向图，若在每条边e上定义一个非上定义一个非负权负权c，则称图

5、，则称图G为一个网络，称为一个网络，称c为边为边e的容量函数，的容量函数，记为记为c(e)。若在有向图若在有向图G(V,E)中有两个不同的顶点中有两个不同的顶点vs与与vt ，若顶点若顶点vs只有出度没有入度，称只有出度没有入度，称vs为图为图G的源，的源，若顶点若顶点vt只有入度没有出度，称为只有入度没有出度，称为G的汇，的汇，若顶点若顶点v 既不是源也不是汇，称为既不是源也不是汇，称为v中间顶点。中间顶点。v2v4v1v3vsvt483757377v2v4v1v3vsvt48375737设设u,v网络网络G(V,E)的相邻顶点，边的相邻顶点，边(u,v)上的函数上的函数f(u,v)称为边称

6、为边(u,v)上的实际流量；上的实际流量；若对网络若对网络G(V,E)的任意相邻顶点的任意相邻顶点u,v 均成立：均成立： 0 f(u,v) c(u,v) ， 称该网络为相容网络。称该网络为相容网络。若若v为网络为网络G(V,E)的中间顶点，的中间顶点， Vuvuf),( Vwwvf),(有：有：8v2v4v1v3vsvt48375737网络的总流量为从源网络的总流量为从源vs 流出的总流量：流出的总流量： VwswvffV),()(流入汇流入汇vt 总流量：总流量： VutvuffV),()(9设网络设网络G(V,E,C)，其中，其中 为源为源 ， 为汇，为汇，),(ijcC svtv为边为

7、边 上的容量，上的容量，ijc),(jivv若流若流 满足：满足：ijff （1）容量限制条件：）容量限制条件：对每一条弧对每一条弧 成立成立Evvji ),(ijijcf 0（2）平衡条件：）平衡条件： Vuuvf),( Vuvuf),( ttssvvfVvvvvvfV),(, 0),(称流称流 为可行流，为可行流，V( f )为总流量。为总流量。ijff 10 若存在一个可行流若存在一个可行流f *，使得对所有可行流，使得对所有可行流 f 都有都有V(f *) V(f )成立，则称成立，则称f *为最大流。为最大流。11最大流模型：最大流模型：)(maxfVs.t: VvijVvjijjv

8、vfvvf),(),(,),(0ijjicvvf ),(Vvvji sivvfV ),(tsivvv, 0 tvvfV ),(例例7.1分组交换技术在计算机网络中发挥着重要作用，信分组交换技术在计算机网络中发挥着重要作用，信息从源节点到目的节点不再需要一条固定的路径，而是息从源节点到目的节点不再需要一条固定的路径，而是将其分割为几组，通过不同的路径传输到目的节点，目将其分割为几组，通过不同的路径传输到目的节点，目的节点再重新组合还原文件。现考察如图所示的网络，的节点再重新组合还原文件。现考察如图所示的网络，图中两节点间的数字表示两交换机间可用的带宽，此时图中两节点间的数字表示两交换机间可用的带

9、宽，此时从节点从节点1到节点到节点9的最大带宽为多少？的最大带宽为多少？v2v5v1v3v82.5v9v4v7v67.13.46.15.62.43.63.87.44.95.77.25.34.53.86.77.412设设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

10、.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 v2v5v1v3v82.5v9v4v7v67.13.46.15.62.43.63.87.44.95.77.25.34.53.86.77.413sets: node/v1.v9/;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)=

11、flow;for(arc:bnd(0,f,c);)(maxfV VujiVuijjjff 9 ),(9 , 1 , 01 ),(ifViifV,0CF .ts14data: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;text()=table(f);enddata1

12、5 Objective value: 14.20000 V1 V2 V3 V4 V5 V6 V7 V8 V9 V1 0 2.5 0 5.6 6.1 0 0 0 0 V2 0 0 3.4 0 0 1.5 0 0 0 V3 0 0 0 0 0 0 0 3.4 0 V4 0 0 0 0 3.3 0 2.3 0 0 V5 0 2.4 0 0 0 7 0 0 0 V6 0 0 0 0 0 0 0 4 4.5 V7 0 0 0 0 0 0 0 0 2.3 V8 0 0 0 0 0 0 0 0 7.4 V9 0 0 0 0 0 0 0 0 0v2v5v1v3v82.5v9v4v7v67.13.46.15.6

13、2.43.63.87.44.95.77.25.34.53.86.77.416例例7.2 （最小费用最大流）在如图所示的运输网络中，（最小费用最大流）在如图所示的运输网络中，从从 发送物资到发送物资到 ，图中边上括号里的第一个数字代，图中边上括号里的第一个数字代表路段上该物资的单位运输成本，第表路段上该物资的单位运输成本，第2个数字代表路个数字代表路段的实际通行能力，问如何组织运输可以获得成本最段的实际通行能力，问如何组织运输可以获得成本最低的最大运输量。低的最大运输量。svtv17:ijc节点节点 到到 的单位运输成本，得矩阵的单位运输成本，得矩阵ivjv nnijcC :ijd边边 上的容量

14、，得容量矩阵上的容量，得容量矩阵),(jivv nnijdD 决策变量：边决策变量：边 上的流量上的流量 ，得流量矩阵，得流量矩阵),(jivv nnijff 要求流量最大和成本最小，可建立多目标规划模型。要求流量最大和成本最小，可建立多目标规划模型。流量最大：流量最大：)(maxfV成本最小：成本最小： ninjijijfc11min约束条件：约束条件： VujiVuijjjff sivvfV ),(tsivvv, 0 tvvfV ),(ijijdf 0ijf18模型求解：（分两步完成）模型求解：（分两步完成）第一步：先求解第一目标第一步：先求解第一目标)(maxfV VujiVuijjjf

15、f sivvfV ),(tsivvv, 0 tvvfV ),(ijijdf 019)(maxfV VujiVuijjjff sivvfV ),(tsivvv, 0 tvvfV ),(ijijdf 0 sets: node/s,1,2,3,4,5,6,7,t/; arc(node,node):d,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;for(arc:bnd

16、(0,f,d);20data: d= 0, 60, 30, 50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 45, 30, 0, 0, 0, 0, 0, 0, 0, 0, 30, 25, 0, 0, 0, 0, 20, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 35, 0, 30,30, 0, 0, 0, 0, 0, 0, 0, 40,50, 0, 0, 0, 0, 0, 0, 0, 0, 40, 0, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0;text()=table(f);enddata21

17、 Objective value: 130.0000 S 1 2 3 4 5 6 7 T S 0 60 20 50 0 0 0 0 0 1 0 0 0 0 45 15 0 0 0 2 0 0 0 0 0 30 10 0 0 3 0 0 20 0 0 0 30 0 0 4 0 0 0 0 0 0 0 15 30 5 0 0 0 0 0 0 0 5 40 6 0 0 0 0 0 0 0 0 40 7 0 0 0 0 0 0 0 0 20 T 0 0 0 0 0 0 0 0 0最大流量：最大流量：f=13022将最优值加入约束，求第二目标：将最优值加入约束，求第二目标： ninjijijfc11mi

18、n VujiVuijjjff sivv ,130tsivvv, 0 tvv ,130ijijdf 0 sets: node/s,1,2,3,4,5,6,7,t/; arc(node,node):c,d,f; endsets OBJmin=sum(arc:c*f);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,d);23data: flow=130;d= 0, 60, 30,

19、50, 0, 0, 0, 0, 0, 0, 0, 0, 0, 45, 30, 0, 0, 0, 0, 0, 0, 0, 0, 30, 25, 0, 0, 0, 0, 20, 0, 0, 0, 30, 0, 0, 0, 0, 0, 0, 0, 35, 0, 30,30, 0, 0, 0, 0, 0, 0, 0, 40,50, 0, 0, 0, 0, 0, 0, 0, 0, 40, 0, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0;c=0, 4, 5, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 3, 0, 0, 0,

20、 0, 0, 0, 0, 0, 3, 2, 0, 0, 0, 0, 2, 0, 0, 0, 4, 0, 0,0, 0, 0, 0, 0, 5, 0, 3, 4, 0, 0, 0, 0, 0, 0, 0, 4, 3, 0, 0, 0, 0, 0, 0, 0, 0, 4, 0, 0, 0, 0, 0, 0, 0, 0, 4,0, 0, 0, 0, 0, 0, 0, 0, 0;text()=table(f);enddata24Objective value: 1510.000 S 1 2 3 4 5 6 7 T S 0 60 30 40 0 0 0 0 0 1 0 0 0 0 30 30 0 0 0

21、 2 0 0 0 0 0 30 20 0 0 3 0 0 20 0 0 0 20 0 0 4 0 0 0 0 0 0 0 0 30 5 0 0 0 0 0 0 0 10 50 6 0 0 0 0 0 0 0 0 40 7 0 0 0 0 0 0 0 0 10 T 0 0 0 0 0 0 0 0 025定义定义1 在图在图G(V,E)中，若顶点中，若顶点 与边与边ei相互关联，相互关联，iivv,1 称非空序列称非空序列12110kkkvevevevw ), 2 , 1(ki 为从为从v0到到vk的一条的一条通路通路，边不重复但顶点可重复的通路称为边不重复但顶点可重复的通路称为道路道路，边与顶点

22、均不重复的通路称为边与顶点均不重复的通路称为路径路径。44112544141vevevevevwvv 通路：通路：4521141vevevPvv 道路：道路：4332264521141vevevevevevTvv 路径：路径：三、最短路三、最短路问题问题26路径路径 ，则称则称 为路径为路径P的权的权定义定义2 (1) 任意两点均有路径的图称为连通图任意两点均有路径的图称为连通图(2) 起点与终点重合的路径称为圈起点与终点重合的路径称为圈(3) 连通而无圈的图称为树连通而无圈的图称为树定义定义3 (1) 设设P(u,v) 是赋权图是赋权图G中从顶点中从顶点u到顶点到顶点v )()()(PEee

23、wPw(2)在赋权图在赋权图G中，从顶点中，从顶点u到顶点到顶点v具有最小权的具有最小权的路径路径 ，称为，称为u到到v最短路最短路。27指定顶点到其余顶点的最短路算法：指定顶点到其余顶点的最短路算法： Dijkstra算法算法 在在matlab中使用命令中使用命令graphshortestpath实现。实现。调用格式：调用格式：dist,path=graphshortestpath(DG,A,B) dist： A与与B之间的最短路的长度之间的最短路的长度 path： A与与B之间的最短路的路径之间的最短路的路径 DG：权数邻接矩阵：权数邻接矩阵28例例7.3 某地某地10个点个点v1,v2,

24、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间

25、的最短路。间的最短路。29(程序程序li703)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 3

26、4: 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 30W=sparse(x,y,w);B=W+W;dist,path=graphshortestpath(B,1,10)ids=v1,v2,v3,v4,v5,v6,v7,v8,v9,v10;bg=biograph(W,ids,ShowArrows,off,ShowWeigh

27、ts,on)h=view(bg)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) 31 4.2 5.6 6.5 3.5 6.5 15.2 3.8 5.4 7.6 5.1 5.1 8.8 12.3 4.7 5.2 7.6 6.3 3.9 5.2 6.9 3.5 6.3 6.8 5.9 5.8 v1v2v3v4v5v6v7v8v9v10dist = 21.4000path = 1 4 6 8

28、 1032每对顶点之间的最短路：每对顶点之间的最短路： floyd算法：算法：设图设图G(V,E,W)的权邻接矩阵为：的权邻接矩阵为：其中其中 当当vi与与vj之间没有边相连时，取之间没有边相连时，取 当当vi与与vj之间有边时，取之间有边时，取 wij 为该边的权。为该边的权。对于无向图对于无向图G，邻接矩阵，邻接矩阵D0是对称矩阵。是对称矩阵。 nnijdD )()0(0)0(ijd )0(ijd，ijijwd )0(33(3)递推产生一个矩阵序列递推产生一个矩阵序列D0, D1, Dn(4) 为最短路距离矩阵，为最短路距离矩阵，floyd算法的步骤：算法的步骤：（求有（求有n个节点的图的

29、最短路距离矩阵个节点的图的最短路距离矩阵Dn的步骤）的步骤）(1)初值初值k=0，nnijdD )()(00 0nnnijndD )()()(nijd为为vi到到vj的最短路的距离。的最短路的距离。(2)计算计算,min)1()1()1()( kkjkikkijkijdddd34建立最短路径矩阵建立最短路径矩阵R的步骤：的步骤：（1） ,)()0()0(nnijrR jrij )0( , )2()1()(kijkijrkr(1)(1)(1)kkkijikkjddd (1)(1)(1)kkkijikkjddd (3)递推产生一个矩阵序列递推产生一个矩阵序列R0,R1,Rn(4)矩阵矩阵R=Rn为

30、最短路径矩阵为最短路径矩阵35查找最短路路径的方法：查找最短路路径的方法：若若 则则 是是点点vi与到点与到点vj最短路径的途中点，最短路径的途中点，1)(arnij 1av(1) 向起点向起点vi与追溯：与追溯：，1)(arnij ，2)(1arnia ， 3)(2arnia ( )kniakra 得：得：12,aaaivvvvk(2) 向终点向终点vj与追溯：与追溯：，1)(arnij ，1)(1brnja ,2)(1，brnjb ，jrnjbm )(得：得：jbbbavvvvvm,211(3)点点vi与到点与到点vj最短路路径：最短路路径：jbbbaaaivvvvvvvvmk,21123

31、6建立由建立由floyd算法求最短路长矩阵的算法求最短路长矩阵的matlab函数：函数：function D=zuiduan(B) n=length(B); D=B; for 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); end end endendD=full(D); 37例例7.4某城市要建立一个消防站，为该市所属的九个区服务，某城市要建立一个消防站，为该市所属的九个区服务，如图所示问应设在哪个区，才能使它至最远区的路径最短？如图所示问应设在哪个区，才能使它至最远区的路径最短？记消防站建在记消防

32、站建在vi处的最大服务距离为处的最大服务距离为S(vi)，(i=1,2,n)模型建立：模型建立： )(min)(1inikvSvS S(vi)：vi到其它节点的最短路程的最大值。到其它节点的最短路程的最大值。记记dij为节点为节点vi到节点到节点vj的最短路程的最短路程ijnjidvS 1max)(求求dij 最短路问题！最短路问题！用用floyd算法算法12358447634637736593866838 B 0 4 4 0 3 7 3 8 3 0 4 3 0 6 7 6 7 3 6 0 3 0 5 6 5 0 8 7 6 0 6 6 6 012358447634637736593866赋权

33、邻接矩阵：赋权邻接矩阵：3912358447634637736593866 x=1,2,4 2,3,3 2,5,7 2,6,3 2,8,8 3,4,4 3,5,3 4,5,6 4,8,7 4,9,6 6,7,5 6,8,6 8,9,6 9,9,0 40 建立一个构造邻接矩阵的函数文件：建立一个构造邻接矩阵的函数文件： function B=qlinjie(x) a=x(:,1);b=x(:,2);c=x(:,3); B=sparse(a,b,c); B=full(B+B); B(find(B=0)=inf; for i=1:length(B) B(i,i)=0; end41clc,clear

34、x=1,2,4;2,3,3;2,5,7;2,6,3;2,8,8;3,4,4;3,5,3;4,5,6;4,8,7;4,9,6;6,7,5;6,8,6;8,9,6;9,9,0;B=fun704(x);D=zuiduan(B); %最短距离矩阵最短距离矩阵S=max(D) %最大服务距离最大服务距离k=find(S=min(S) %最佳选址点最佳选址点主程序（主程序（li704）：）：42 求解结果：求解结果： S = 17 13 11 15 14 12 17 13 17 k=3应该在第应该在第3个节点建消防站。个节点建消防站。43例例7.5 某矿区有某矿区有7个矿点（如图所示）各矿点每天的产矿量为

35、个矿点（如图所示）各矿点每天的产矿量为 )(jvq现要从这现要从这7个矿点选一个来建造矿厂问应选在哪个矿点，才能使个矿点选一个来建造矿厂问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运量（千吨公里）最小。各矿点所产的矿运到选矿厂所在地的总运量（千吨公里）最小。 （1）求最短路程矩阵：）求最短路程矩阵： dij为节点为节点vi到节点到节点vj的最短路程的最短路程)(ijdD （2）计算在第）计算在第i 个矿点建矿厂的总运量：个矿点建矿厂的总运量：ijjjidvqvm )()(71 （3）求）求vk使使)(min)(71iikvmvm 44在第在第i 个矿点建矿厂的总运力：个矿点建矿厂

36、的总运力：ijjjidvqvm )()(711771221111dqdqdqm 2772222112dqdqdqm 7777227117dqdqdqm 表示为矩阵乘积：表示为矩阵乘积：TDqM 最短距离矩阵最短距离矩阵D=(dij)45clc,clear x=1,2,3;2,3,2;2,6,4;3,4,6;3,5,2;4,5,1;5,6,4;6,7,1.5;7,7,0; q=3,2,7,1,6,1,4; %各矿点日产量各矿点日产量 B=fun704(x); %权邻接矩阵权邻接矩阵 D=zuiduan(B); %最短距离矩阵最短距离矩阵 M=D*q %各矿点建厂的总运量各矿点建厂的总运量 k=f

37、ind(M=min(M) %最佳选址点最佳选址点主程序（主程序（li705）：）：46求解结果：求解结果： M = 132 78 70 92 70 106 130 k = 3 5应该在第应该在第3矿点或第矿点或第5矿点建厂。矿点建厂。47四、四、旅行推销员问题（旅行推销员问题（TSPTSP问题）问题） 定义定义1设设G=(V,E)是连通无向图是连通无向图 (1) 经过经过G的每边至少一次的的每边至少一次的闭通路闭通路称为巡回称为巡回 (2) 经过经过G的每边正好一次的巡回称为欧拉巡回的每边正好一次的巡回称为欧拉巡回 (3) 存在欧拉巡回的图称为欧拉图存在欧拉巡回的图称为欧拉图 (4) 经过经过

38、G的每边正好一次的道路称为欧拉道路的每边正好一次的道路称为欧拉道路 e3 v1 v2 v3 v4e1e2e4 e5e6 e3 v1 v2 v3 v4 e1e 2e4e5欧拉道路：欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v148 定义定义2 设设G=(V,E)是连通无向图是连通无向图. (1) 经过经过G的每个顶点正好一次的路径，的每个顶点正好一次的路径，称为称为G的一条哈密尔顿路径的一条哈密尔顿路径 (2) 经过经过G的每个顶点正好一次的圈，的每个顶点正好一次的圈，称为称为G的哈密尔顿圈或的哈密尔顿圈或H圈圈 (

39、3) 含含H圈的图称为哈密尔顿图或圈的图称为哈密尔顿图或H图图 49旅行推销员问题（旅行推销员问题（TSPTSP问题）问题）: : 推销员需要访问某地区的所有城镇，最后回到推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小出发点问如何安排旅行路线使总行程最小。 若用顶点表示城镇，边表示连接两城镇的路，若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、或费用），边上的权表示距离（或时间、或费用），推销员问题就成为在加权图中寻找一条经过每个顶推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题点至少一次的最短闭通路问题。定义定义3在加权图

40、在加权图G=(V,E)中，中， (1)权最小的哈密尔顿圈称为最佳权最小的哈密尔顿圈称为最佳H圈圈。 (2)经过每个顶点至少一次的权最小的闭通路称经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路为最佳推销员回路。50 注意：最佳哈密尔顿圈不一是最佳注意：最佳哈密尔顿圈不一是最佳推销员回路，同样最佳推销员回路推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈。也不一定是最佳哈密尔顿圈。1v2v3v1120 定理定理 在加权图在加权图G=(V,E)中，若对任意中，若对任意,Vzyx ,yzxz 都有都有),(),(),(yzwzxwyxw 则图则图G的最佳的最佳H圈也是最佳推销员回路圈也是

41、最佳推销员回路。到目前为止，到目前为止，TSP问题还没有有效解决方法，问题还没有有效解决方法，现有的方法都是寻找近似最优的哈密顿圈，现有的方法都是寻找近似最优的哈密顿圈，常用方法有边替换法、遗传算法、模拟退火法、常用方法有边替换法、遗传算法、模拟退火法、蚁群算法等。蚁群算法等。51引入引入0-1变量：变量：xij=1，由第，由第i城市进入第城市进入第j城市，且城市，且i j0，其它，其它 目标函数：目标函数： niniijijxcz11min对规模不大的对规模不大的TSP问题可将其转化为数学规划问题：问题可将其转化为数学规划问题：, 11 niijx j=1,2,3,n, 11 njijx i

42、=1,2,3,n ,1 , 0 ijx i, j =1,2,3,n52123456到此得到了一个模型，它是一个指派问题的整数规到此得到了一个模型，它是一个指派问题的整数规划模型。但以上两个条件对于划模型。但以上两个条件对于TSPTSP来说并不充分，来说并不充分，仅仅是必要条件。仅仅是必要条件。例如：例如：以上两个条件都满足，但它显然不是以上两个条件都满足，但它显然不是TSPTSP的解，的解，它存在两个子巡回。它存在两个子巡回。则可以避免产生子巡回。则可以避免产生子巡回。若在原模型上添加变量若在原模型上添加变量ui ，并附加下面形式的约束条件：并附加下面形式的约束条件：，1 nnxuuijji.

43、 12 nji, 20 nui53引入引入0-1变量：变量：xij=1，由第，由第i城镇进入第城镇进入第j城镇，且城镇，且i j0，其它，其它 对规模不大的对规模不大的TSP问题可将其转化为数学规划问题：问题可将其转化为数学规划问题：目标函数：目标函数： niniijijxcz11min s.t：, 11 niijx, 11 njijx, 1 nnxuuijji,2nji , 20 nui i=2,3,n, 1 , 0 ijx i,j=1,2,3,n j=1,2,3,n i=1,2,3,n54例例7. 6 (TSP问题问题) 已知已知9个城市间的旅行费用（见表）个城市间的旅行费用（见表）问他应

44、按怎样的次序访问这些城市，能使得总旅费最问他应按怎样的次序访问这些城市，能使得总旅费最少？少？ 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

45、.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 91 2 3 4 5 6 7 8 955 9191miniiijijxcz s.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

46、/: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)|i#gt#1:u(I)=0);for(link:bin(x);56data: c=0, 3.1, 5.2, 4.3, 5.2, 6.5, 8.8, 7.

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

48、6.6, 0, 5.8, 5.9, 7.2, 6.8, 8.8, 9.4, 7.5, 4.9, 5.8, 0;enddata57Objective 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、最小，最小费费用最小，最小费用：用：49.158五、最小生成树五、最小生成树问题问题1v树：树： 连通且不含圈的无向图称为连通且不含圈的无向图称为树树常用常用T表示表示.树中的边称为树中的边称为树枝树枝. 树中度为树中度为1的顶点称为的顶点称为树叶树叶. 2v3v4v5v支撑树：支撑树： 设图设图G(V,E)，若，若T是树，是树，且且称树称树T是图是图G的支撑（生成）树。的支撑（生成）树。 ( )( ), ( )( )E TE G V TV G ，最小生成树：赋权连通图最小生成树：赋权连通图G的所有支撑树中，其各边的所有支撑树中，其各边权之和最小的支撑树，称为连通图权之和最小的支撑树，称为连通

50、图G的最小生成树。的最小生成树。解决最小生成树的常用方法：克鲁斯卡尔算法、普利解决最小生成树的常用方法：克鲁斯卡尔算法、普利姆算法。姆算法。59普利姆（普利姆（Prim）算法：）算法： 设置两个集合设置两个集合P和和Q，其中，其中P、Q分别用于存放最分别用于存放最小生成树的顶点和边，小生成树的顶点和边，P的初值为的初值为P=v1，Q的初值为的初值为Q=。 普利姆算法的基本思想：从所有普利姆算法的基本思想：从所有的边中，选取一条具有最小权值的边的边中，选取一条具有最小权值的边uv，将顶点，将顶点v加加入到集合入到集合P中，将边中，将边uv加入到集合加入到集合Q中，不断重复下中，不断重复下去，直到

51、去，直到P= =V中止。中止。PVvPu ,60普利姆（普利姆（Prim）算法：）算法： 设置两个集合设置两个集合T和和Q，其中，其中T、Q分别用于存放最分别用于存放最小生成树的顶点和边，小生成树的顶点和边，T的初值为的初值为T=v1，Q的初值为的初值为Q=。普利姆算法的基本思想：普利姆算法的基本思想：从所有从所有 的边的边uv中，中，选取一条具有最小权值的边选取一条具有最小权值的边uv，将顶点将顶点v加入到集合加入到集合T中，再将从集合中，再将从集合S中剔除，中剔除，将边将边uv加入到集合加入到集合Q中，中，不断重复下去，直到不断重复下去，直到T= =V中止。中止。PVSvPu ,61123

52、56465854367669764Q=v2v6Q=v2v6,v2v1Q=v2v6,v2v1,v1v3Q=v2v6,v2v1,v1v3,v3v5最生成小树为最生成小树为Tree=v2v6,v2v1,v1v3,v3v5,v6v7,v7v4 最小生成树的权为最小生成树的权为27。例例7.7 求右图的最小生成树求右图的最小生成树Q=v2v6,v2v1,v1v3,v3v5,v6v7Q=v2v6,v2v1,v1v3,v3v5,v6v7,v7v462Prim算法的算法的matlab实现：实现： function A,B,Tch=primg(w,a) %w: 权矩阵，权矩阵，a：起始点编号：起始点编号 n=l

53、ength(w); T=a; S=setdiff(1:n,T); A=;B=; L=; w(w=0)=inf; k1=1; k2=n-1;Prim算法：算法：图图G(V,E,W)(1)T=v1, Q= S=setdiff(V,T),(2)找顶点找顶点u与与v满足：满足：min ( , )|,w u vu T vS T=T,v,S=setdiff(S,v)Q =Q, uv(3)若若T=V结束循环结束循环 否则转向否则转向(2)63 while k1n min=inf; for m1=1:k1 for m2=1:k2 t=w(T(m1),S(m2); if tmin min=t; u=T(m1);

54、 v=S(m2); end end end T=T,v; S=setdiff(S,v); A=A,u;B=B,v; L=L,min; k1=length(T);k2=length(S); end Tch=sum(L); Prim算法：算法：图图G(V,E,W)(1)T=v1, Q= S=setdiff(V,T),(2)找顶点找顶点u与与v满足：满足：min ( , )|,w u vu T vS T=T,v,S=setdiff(S,v)Q =Q, uv(3)若若T=V结束循环结束循环 否则转向否则转向(2)64例例7.8某单位有某单位有10个下属部门，均不在同一地点办公，个下属部门，均不在同一地点办公，为了实现部门之间的资源共享，该单位打算对原有网络为了实现部门之间的资源共享，该单位打算对原有网络进行改造，将所有各部门通过光缆连接