课件-图论和网络分析算法及Matlab实现

图论基本模型算法及matlab实现

一、图论的基本概念

二、图论模型与算法三、Matlab实现1.图论简介起源：1736年Eular解决“哥尼斯堡”七桥问题1.图论简介

图G(V,E)

☺顶点集合V

☺边集合

E

☺一条边e

有两个顶点{u，v}，记为e=uv图G1.图论简介

图G(V,E)

☺顶点集合V

☺边集合

E

☺一条边e

有两个顶点{u,v}，记为e=uv无向图G无序顶点对1.图论简介

图G(V,E)

☺顶点集合V

☺边集合

E

☺一条边e

有两个顶点{u，v}，记为e=uv图G1.图论简介

图G(V,E)

☺顶点集合V

☺边集合

E

☺一条边e

有两个顶点{u，v}，记为e=uv简单图G无环边和重边1.图论简介

图G(V,E)

☺顶点集合V

☺边集合

E

☺一条边e

有两个顶点{u，v}，记为e=uv☺u是v的邻居节点☺v的度d(v)：与v关联的边数1.图论简介

图G(V,E)

☺顶点集合V

☺边集合

E

☺一条边e

有两个顶点{u，v}，记为e=uv☺u是v的邻居节点☺v的度d(v)：与v关联的边数☺v的邻域N(v)：所有v的邻居的集合1.图论简介

完全图：任意两点有边相连，用表示

路与圈图中一个点边接续交替且不重复出现的序列称为路；若仅有起点和终点重复，则称为圈。3.路与圈图中一个点边接续交替且不重复出现的序列称为路；若仅有起点和终点重复，则称为圈。路与圈图中一个点边接续交替且不重复出现的序列称为路；若仅有起点和终点重复，则称为圈。匹配：一个边集合M,任意两条边不相邻；覆盖所有顶点的匹配叫完美匹配。关联矩阵与邻接矩阵

关联矩阵与邻接矩阵

有向图与无向图，圈，回路比较：路有向路二.最短路问题

v5v1v3v6v4v2v7255233575711算法：Dijkstra算法（Dijkstra，1959）Dijkstra,E.W.(1959).Anoteontwoproblemsinconnexionwithgraphs.NumerischeMathematik1,269–271.算法思想：Bellman最优化原理若P是网络G中从Vs到Vt的一条最短路，Vl是P中除Vs与Vt外的任何一个中间点，则沿P从Vs到Vl的一条路P1亦必是Vs到Vl的最短路。Dijkstra算法-标号法由图G建立一步可达距离阵D=(dij)n×n给V1(Vs)括号(l1,Vk)=(0,s)给出已标号集合I和未标号集合J的元素对于给定的I和J，确定集合A={aij|Vi∈I，Vj∈J}

计算距离给Vk括号(lk,Vh)lk=lh+WhkI=I+{Vk}J=J–{Vk}A=φ或J＝φ从Vt

逆向搜索双括号，可得最小路P途径各点及最小路距离ENDNYDijkstra算法用标号法解例v5v1v3v6v4v2v7255233575711[0，v1][2，v1][3，v1][4，v2][7，v3][8，v5][13，v6]最短距为13；最短路为v1-v2-v3-v5-v6-v7。最短路问题应用厂址选择厂址布局设备更新网络线路安装工程设计企业管理最短路问题的应用例子

某汽车公司正在制订5年内购买汽车的计划。下面给出一辆新汽车的价格以及一辆汽车的使用维修费用(万元)：

年份 1 2 3 4 5年初价格 11 11 12 12 13

使用年数0～11～22～3 3～44～5年维护费用5 6 8 11 18

试用图论中求最短路的方法确定公司可采用的最优策略。解：设Vi—i年初购进一台新设备aij—i年初购进之新设备使用到第j年初ωij—i年初购进之新设备使用到第j年初之总费用

方法：以年号作顶点绘图，连线表示连续使用期间，以费用作路长。费用矩阵方法：以年号作顶点绘图，连线表示连续使用期间，以

费用作路长。可知最短费用流（相当于最短路）

P：V1V3V6

或者是V1V4V6

|

P|=53万元

结论：公司五年期设备更新方案有两个：A与B，总费用均为53万元。

A方案：第1年初购置设备使用到第3年初,第3年初再购置新设备使用到第5年末（第6年初）

B方案：第1年初购置设备使用到第4年初，第4年初再购置新设备使用到第5年末（第6年初）

Matlab程序实现

Matlab程序实现1写出邻接矩阵输入临接矩阵：W=[0218infinfinfinf

20inf61infinfinf

1inf07infinf9inf

8670512inf

inf1inf503

inf9

infinfinf130

46

infinf92inf4

03infinfinf

inf96

30];function[d,path]=dijkstra(W,s,t)%s起点，t终点[n,m]=size(W);ix=(W==0);W(ix)=inf;ifn~=m,error('SquareWrequired');endvisited(1:n)=0;dist(1:n)=inf;parent(1:n)=0;dist(s)=0;d=inf;fori=1:(n-1),ix=(visited==0);vec(1:n)=inf;vec(ix)=dist(ix);[a,u]=min(vec);visited(u)=1;

forv=1:n,

if(W(u,v)+dist(u)<dist(v)),dist(v)=dist(u)+W(u,v);parent(v)=u;

end;

end;endifparent(t)~=0,path=t;d=dist(t);

whilet~=s,p=parent(t);path=[ppath];t=p;

end;end;树v1v2v3v5v4

特点：连通、无圈。——无圈的连通图，记为T。v1v2v3v5v4树的性质：（1）树的任2点间有且仅有1条路；（2）在树中任去掉1边，则不连通；（3）在树中不相邻2点间添1边，恰成1圈；（4）若树T有n个顶点，则T有n-1条边。图的支撑树

若图G=（V，E）的子图T=（V，E’）是树，则称T为G的支撑树。特点——边少、点不少。性质：G连通，则G必有支撑树。证：破圈、保连通。最小支撑树问题

例2求如图网络的最小支撑树。v5v1v3v6v4v2v7255233575711Kruskal,J.B.(1956).OntheShortestSpanningSubtreeofaGraphandtheTravelingSalesmanProblem.ProceedingsoftheAmericanMathematicalSociety7,48-50.

避圈法是一种选边的过程，其步骤如下：1.从图D中任选一点vi，找出与vi相关联的权最小的边[vi，vj]，得第二个顶点vj；2.把顶点集V分为互补的两部分V1,1，其中对G中各边按权大小顺序排列，不妨设为W1≤W2≤…≤Wm填写Wj对应的各边aj

S=φ，i=0，j=1{aj}∪S构成回路？|S|=n-1ei+1=ajS={ei+1}∪Si=i+1j=j+1j=j+1T*=S打印T*ENDYYNN用避圈法解例题v5v1v3v6v4v2v7255233575711•最小部分树如图上红线所示；最小权和为14。思考：破圈法是怎样做的呢？——见圈就破，去掉其中权最大的。最小支撑树问题的应用例子已知有A、B、C、D、E、F六个城镇间的道路网络如图，现要在六个城镇间架设通讯网络（均沿道路架设），每段道路上的架设费用如图。求能保证各城镇均能通话且总架设费用最少的架设方案。6EACBFD5109353978284三.最大流问题

v4v2vsv1vtv3213145325三.最大流问题1.问题已知网络D=（V，A，C），其中V为顶点集，A为弧集，C={cij}为容量集，cij为弧（vi，vj）上的容量。现D上要通过一个流f={fij}，其中fij为弧（vi，vj）上的流量。问应如何安排流量fij可使D上通过的总流量v最大？v4v2vsv1vtv3213145325可采用线性规划的单纯型法求解（容量约束）（平衡条件）问题：最大流问题的决策变量、目标函数、约束条件各是什么？2.数学模型3.基本概念与定理如：在前面例举的网络流问题中，若已给定一个可行流（如括号中后一个数字所示），请指出相应的弧的类型。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）（2）可增值路（增广路）v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）路路（2）可增值路（增广路）路路v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）算法设计思想

最大流的判别条件

任意一个可行流(例如零值流)开始，若能找到一条s-t增广路P，则沿P修改流的值，得到一个更大的流f；若不存在s-t增广路，则由定理5.2，f就是最大流，算法终止。关键：在给定可行流

f时，如何找s-t增广路或判断s-t增广路不存在?

Ford-Fulkerson标号法

例5用标号法求下面网络的最大流。v4v2vsv1vtv3（2，2）（1，1）（3，3）（1，1）（4，3）（5，1）（3，0）（2，1）（5，3）2020当前流即为最大流，流值为5

割集与割容量

例4对于下图，若V1={vs，v1}，请指出相应的割集与割容量。解：（4）流量与割容量的关系最大流最小割定理：v4v2vsv1vtv3（2，2）（1，0）（3，3）（1，0）（4，3）（5，2）（3，0）（2，2）（5，3）最大流问题的应用例子汽车由A城通往B城的可能的路线如下图所示。环境保护部门拟建立足够数量的汽车尾气检查站，以便使每辆汽车至少必须经过一个检查站。建立检查站的费用根据各路段的条件而有所不同(如图上数字所示)。若求这个问题的最小费用解，可使用

模型。

a.最短路模型；b.最大流模型；c.最小支撑树模型AacbdefgB824452643367378最小费用流问题

延伸问题最小费用流中国邮递员问题、欧拉回路（边）旅行商问题、汉密尔顿圈（点）可平面化问题指派问题统筹网络计划匹配问题无圈网络：拓扑排序+动态规划圈的检测正费用网络：Dijkstra算法（1959）一般网络，单一起点（或终点）Bellman-Ford算法(1956)：

O(mn)一般网络，所有点对Floyd-Warshall算法(1962)：

O(n3)负圈检测最短路算法：标号设定/修正算法破圈法-----复杂度高避圈法----贪婪算法(GreedyAlgorithm)Kruskal算法（1956）Prim算法（1957）：即“边割法”Dijkstra算法（1959）Sollin算法（1961）最小（生成）树算法增广路算法Ford-Fulkerson标号算法(1956)最大容量增广路算法容量变尺度算法最短增广路算法：O(n2m)预流推进算法最高标号预流推进算法：O(n2m1/2)最大流算法实际计算效率高消圈算法最小费用路算法原始-对偶算法Ford和Forkerson(1957,1962)瑕疵算法(Out-Of-KilterAlgorithm)松弛(Relaxation)算法网络单纯形算法最小费用流算法实际计算效率高二部图匹配增广路算法：O(mn)简单网络上的最大流算法：O(mn1/2)一般图匹配“花”算法:O(n3)二部赋权匹配（指派问题）最小费用流算法（如匈牙利算法）:O(n3)一般赋权匹配原始-对偶算法:O(n3)匹配算法Matlab图论工具箱命令名功能graphallshortestpaths求图中所有顶点对之间的最短距离graphconncomp找无向图的连通分支，或有向图的强弱连通分支graphisdag测试有向图是否含有圈，不含圈返回1，否则返回0graphisomorphism确定两个图是否同构，同构返回1，否则返回0graphisspantree确定一个图是否是生成树，是返回1，否则返回0graphmaxflow计算有向图的最大流graphminspantree在图中找最小生成树graphpred2path把前驱顶点序列变成路径的顶点序列graphshortestpath求图中指定的一对顶点间的最短距离和最短路径graphtopootder执行有向无圈图的拓扑排序graphtraverse求从一顶点出发，所能遍历图中的顶点[i,j,v]=find(G);S=sparse(i,j,v,n,n);图论工具包中的命令要求输入的邻接矩阵为稀疏矩阵，我们用下面的命令来实现：

图的最短路径graphallshortestpaths函数的命令格式[dist]=graphallshortestpaths(G)[dist]=graphallshortestpaths(G,...’Directed’,DirectedValue,...)[dist]=graphallshortestpaths(G,...’Weights’,WeightsValue,...)

例：创建并显示一个含有6个结点11条边的有向图w=[4199513215453832362921];%权值向量dg=sparse([61223445561],[26354163435],w);%构造的稀疏矩阵表示图h=view(biograph(dg,[],'ShowWeights','on'))%显示图的结构dist=graphallshortestpaths(dg)%显示图中每对结点之间的最短路径dist=

0

136

53

57

21

95

111

0

51

66

32

104

60

94

0

15

81

53

45

79

67

0

66

38

81

115

32

36

0

74

89

41

29

44

73

0求给定两点间最短路径---graphshortestpath函数：[dist,path,pred]=graphshortestpath(S,ss,se,’Directed’,1,’Method’,’Bellman-Ford’)S：图的稀疏矩阵ss,se：

分别代表起点和终点‘Directed’：1表示有向图，0或false表示无向图‘Method’：使用算法，默认值为Dijkstra算法输出dist：距离；path：路径

Matlab程序：clc,clearA(1,2)=2;A(1,3)=5;A(1,4)=3;A(2,3)=2;A(2,6)=7;A(3,4)=1;A(3,5)=3;A(3,6)=5;A(4,5)=5;A(5,6)=1;A(5,7)=7;A(6,7)=5;A=A’%matlab工具包要求数据为下三角矩阵[i,j,v]=find(A);S=sparse(i,j,v,7,7);[dist,path,pred]=graphshortestpath(S,1,7,’Directed’,0)数学建模竞赛涉及题目1994修路路线设计问题

1998灾情巡查路线设计

2005DVD在线租赁问题

2007乘公交看奥运问题

2011围追堵截岗亭设置问题1994全国大学生数学建模竞赛

要在一山区修建公路,首先测得一些地点的高程,数据见表1(平面区域0≤x≤5600,0≤y≤4800,表中数据为坐标点的高程,单位:米).数据显示:

在y=3200处有一东西走向的山峰;从坐标(2400,2400)到(4800,0)有一西北---东南走向的山谷;在(2000,2800)附近有一山口湖,其最高水位略高于1350米,雨季在山谷中形成一溪流.经调查知,雨量最大时溪流水面宽度w与(溪流最深处)的x坐标的关系可近似表示为w(x)=((x-24003/4)/2)+5(2400≤x≤4000).公路从山脚(0,800)处开始,经居民点(4000,2000)至矿区(2000,4000).已知路段工程成本及对路段坡度α(上升高程与水平距离之比)的限制如表2.

题目要求试给出一种线路设计方案,包括原理、方法及比较精确的线路位置(含桥梁、隧道),并估算该方案的总成本.

如果居民点改为3600≤x≤4000,2000≤y≤2400的居民区,公路只须经过居民区即可,那么你的方案需要有什么改变？表1

表2

工程种类┃一般路段┃桥梁┃隧道_________┃_______工程成本(元/米)┃300┃2000┃1500(长度≤300米);3000(长度>300米)对坡度α的限制┃α<0.125┃α=0┃α<0.100模型计算方法(1)

对地图网格加密，形成图。(2)

计算网格的距离，用费用作为权值。(3)求赋权图两点间的最短距离。

例：逃生路线问题n*n网格节点上有m个房间，逃到边上节点就算逃生成功如何规划逃生路线，使这些路线互不相交？网络优化问题的例子

可以变成最大流问题逃生成功没有逃生路线m个房间是供应节点（源，供应量为１）只有边上节点可以是吸收节点（汇，吸收量为１）多源多汇，容易变成单源单汇每条边容量为１每个节点容量为１（通过增加节点和边，变成边容量）逃生路线问题变成最大流问题逃生成功没有逃生路线例：空间实验问题某航天公司计划进行一次空间载人飞行，宇航员将在飞行中进行一系列科学实验。目前该公司收到了多个不同的科学实验申请，完成每个实验要求携带相应的一种或多种仪器设备（不同的实验所需要的仪器设备中有些可能是相同的，而另外有些可能是不同的）。已知完成每个实验后公司所得到的相应报酬（不同实验的报酬可能不同），并已知飞行器携带每种仪器设备的相应费用（不同仪器设备的费用可能不同）。公司希望你帮助选定此次飞行究竟从事哪