图论和网络分析算法及Matlab实现(Graph-and-Network-Analysis)

图论与网络分析(GraphTheoryandNetworkAnalysis)一、图论的基本概念二、网络分析算法三、Matlab实现2019/12/10涉及网络优化的数学建模问题1、最短路问题货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。2019/12/102、最小支撑树问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？2019/12/103、指派问题Assignmentproblem一家公司经理安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报不同。如何分配工作方案可以使总回报最大？2019/12/104、中国邮递员问题Chinesepostmanproblem一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？我国管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。2019/12/105、旅行商问题Travelingsalesmanproblem一名推销员准备前往若干城市推销产品。如何为他设计一条最短的旅行路线？（从驻地出发，经过每个城市恰好一次，最后返回驻地）2019/12/106、运输问题Transportationproblem某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂。假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？2019/12/10问题的两个共同特点（1）目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学问题称为最优化或优化问题。（2）它们都可用图形形式直观描述，数学上把这种与图相关的结构称为网络。图和网络相关的最优化问题就是网络最优化。网络优化问题是以网络流为研究的对象，常常被称为网络流或网络流规划等。一、图论的基本概念1.图与子图11(,),,,,nmGVEVvvEee，其中为，图顶点集为边集。11111(,),,GVEVVEE其中子图。e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如G：简单图：无自环、无重边的图。2019/12/10•|V|=n表示图G中节点个数为n，此节点个数n也称为图G的阶•|E|=m表示图G中边的个数为m•任一顶点相关联的边的数目称为该顶点的度•完全图：任意两点有边相连，用表示完全图的边，和每点的度是多少？nK2.关联与相邻121212,[,],()evvevvvve（边与点关系）：若是二点间的边，记称或联与关关联。12121212vvvveeee（边与边、点与点）：点与有公共边，称与相邻；边与有公共点，称与邻接相邻。n1110100110001000110100001101：关联矩阵：*m或者是m*n图在计算机中的表示n0111101011011011邻接矩阵：*n邻接矩阵为对称阵，简单图对角线元素为03.链与圈112211[,],MatlabkkiiiGveveevevvG:由中的某些点与边相间构成的序列，若满足则称此边点序链列为中的一条链。链在中的存储：只储存顶点标号圈：封闭的链。G：图中任二点间至少存连通图在一条链。4.有向图与无向图(,),(,[,]).[,],),kijijijGVEGvvvvvGGvv无向图也可记若点对无序，称为；否则称为。为区别起见，称有向图图有向图弧的边为，记（在图上用箭线表示。），路有向图：弧（，链无向图：边jijivvvv,],[，圈，回路比较：1ijijavv有向图的存储：行为起点，列为终点存在弧赋权图：边有长度v1v2v3v5v4834217W=.41.99.51.32.15.45.38.32.36.29.21;DG=sparse61223445561,26354163435,Wview(biograph(DG,[],'ShowWeights','on'))UGtrilDGDG'view(biograph(UG,[],'ShowWeights','on'))；赋权图在Matlab中的存储：5.树例1已知有5个城市，要在它们之间架设电话线网，要求任2城市都可通话（允许通过其它城市），并且电话线的根数最少。v1v2v3v5v4特点：连通、无圈。树——无圈的连通图，记为T。v1v2v3v5v4树的性质：（1）树的任2点间有且仅有1链；（2）在树中任去掉1边，则不连通；（3）在树中不相邻2点间添1边，恰成1圈；（4）若树T有n个顶点，则T有n-1条边。6.图的支撑树若图G=（V，E）的子图T=（V，E’）是树，则称T为G的支撑树。特点——边少、点不少。性质：G连通，则G必有支撑树。证：破圈、保连通。二、网络分析网络——赋权图，记D=（V，E，C），其中C={c1，…，cn}，ci为边ei上的权（设ci）。网络分析主要内容:最小支撑树最短路最大流。0一.最小支撑树问题问题：求网络D的支撑树，使其权和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例2求如图网络的最小支撑树。v5v1v3v6v4v2v7255233575711Kruskal,J.B.(1956).OntheShortestSpanningSubtreeofaGraphandtheTravelingSalesmanProblem.ProceedingsoftheAmericanMathematicalSociety7,48-50.避圈法是一种选边的过程，其步骤如下：1.从网络D中任选一点vi，找出与vi相关联的权最小的边[vi，vj]，得第二个顶点vj；2.把顶点集V分为互补的两部分V1,1，其中V集；不与已选边相关联的点，，与已选边相关联的点集，11VV其中权最小的；挑选其中考虑所有这样的边,,],,[3.11VvVvvv。即，直至全部顶点属于重复)(34.11VV2019/12/10对G中各边按权大小顺序排列，不妨设为W1≤W2≤…≤Wm填写Wj对应的各边ajS=φ，i=0，j=1{aj}∪S构成回路？|S|=n-1ei+1=ajS={ei+1}∪Si=i+1j=j+1j=j+1T*=S打印T*ENDYYNN用避圈法解例2v5v1v3v6v4v2v7255233575711•最小部分树如图上红线所示；最小权和为14。思考：破圈法是怎样做的呢？——见圈就破，去掉其中权最大的。最小支撑树问题的应用例子已知有A、B、C、D、E、F六个城镇间的道路网络如图，现要在六个城镇间架设通讯网络（均沿道路架设），每段道路上的架设费用如图。求能保证各城镇均能通话且总架设费用最少的架设方案。6EACBFD5109353978284二.最短路问题1.问题：求网络D中一定点v1到其它点的最短路。例3求如图网络中v1至v7的最短路，图中数字为两点间距离。v5v1v3v6v4v2v72552335757112019/12/10•2.方法：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的最短路。证明（反证）：若P1不是从Vs到Vl的最短路，则存在另一条Vs到Vl的路P2使W(P2)W(P1)，若记路P中从Vl到Vt的路为P3。则有W(P2)+W(P3)W(P1)+W(P3)=W(P)，此说明G中存在一条从Vs沿P2到Vl沿P3再到Vt的更短的一条路，这与P使G中从Vs到Vt的一条最短路矛盾。2019/12/10算法思想：设G中从Vs到Vt的最小路P：Vs…Vj…Vk…Vt，则P不仅是从Vs到Vt的最小路，而且从Vs到P中任意中间点的最短路也在P上，为此可采用如下求解步骤：⑴为求得Vs到Vt的最短路，可先求得Vs到中间点的最短路，然后由中间点再逐步过渡到终点Vt。⑵在计算过程中，需要把V中“经判断为最短路P途径之点i”和“尚未判断是否为最短路P途径之点j”区分开来，可设置集合I和J,前者归入I，后者归入J，并令算法初始时，I中仅包含Vs，其他点全在J中，然后随着求解过程的进行，I中的点逐渐增加（相应J中的点逐渐减少），直到终点Vt归入I（相应J=φ），此时迭代结束。I称为已标号集合,J称为未标号集合。2019/12/10⑶为区分中间点Vk是否已归入I中以及逆向求解最短路的方便，可在归入I中的点Vj上方给予双标号（lj,Vk），此中lj表示从Vs到Vj最短路的距离，而Vk则为从Vs到Vj最短路P中Vj的前一途径点。⑷为在计算机上实现上述求解思想，还需引入G中各点间一步可达距离阵D=(dij)n×n，其中|V|=njijiwdijij不能一步到达，能一步到达，2019/12/10由图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途径各点及最小路距离ENDhkhijIiiWlJWl}V|min{jNYDijkstra算法用标号法解例3v5v1v3v6v4v2v7255233575711[0，v1][2，v1][3，v1][4，v2][7，v3][8，v5][13，v6]最短距为13；最短路为v1-v2-v3-v5-v6-v7。2019/12/10dijV1V2V3V4V5V6V7V10253∞∞∞V2203∞∞7∞V3530135∞V43∞105∞∞V5∞∞35017V6∞75∞105V7∞∞∞∞7502019/12/10Vj(lj,Vk)IJhkhijIiiWlJWl}V|min{jV1(0,V1)V1V2~V7min{0+2,0+5,0+3}=2=l1+W12V2(2,V1)V1,V2V3~V74=l2+W23V4(3,V1)V1V2V4V3V5~V73=l1+W14V3(4,V2)V1V2V3V4V5~V77=l3+W35V5(7,V3)V1~V5V6V78=l5+W56V6(8,V5)V1~V6V713=l6+W67V7(22,V6)V1~V7,φ•迭代过程2019/12/10最短路问题应用•厂址选择•厂址布局•设备更新•网络线路安装•工程设计•企业管理最短路问题的应用例子某汽车公司正在制订5年内购买汽车的计划。下面给出一辆新汽车的价格以及一辆汽车的使用维修费用(万元)：年份12345年初价格1111121213使用年数0～11～22～33～44～5年维护费用5681118试用网络分析中求最短路的方法确定公司可采用的最优策略。2019/12/10解：设Vi—i年初购进一台新设备aij—i年初购进之新设备使用到第j年初ωij—i年初购进之新设备使用到第j年初之总费用方法：以年号作顶点绘图，连线表示连续使用期间，以费用作路长。2019/12/10使用总年费用23456注购置费11111111115555566668881111维护费1234518总费用1622304