《图论和网络分析算法及Matlab实现(GraphandNetworkAnalysis)》由会员分享，可在线阅读，更多相关《图论和网络分析算法及Matlab实现(GraphandNetworkAnalysis)（74页珍藏版）》请在金锄头文库上搜索。
1、图论与网络分析 (Graph Theory and Network Analysis),一、图论的基本概念 二、网络分析算法三、Matlab实现,2017/10/26,涉及网络优化的数学建模问题,1、最短路问题货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。,2017/10/26,2、最小支撑树问题,某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速公路直接或间接到达另一个城市。假定已
2、经知道了任意两个城市之间修建高速公路成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？,2017/10/26,3、 指派问题Assignment problem,一家公司经理安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报不同。如何分配工作方案可以使总回报最大？,2017/10/26,4、中国邮递员问题Chinese postman problem,一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少一次，最后返回邮局）？我国管梅谷教授1960年首先提出，国际上称之为中国邮递
3、员问题。,2017/10/26,5 、旅行商问题Traveling salesman problem,一名推销员准备前往若干城市推销产品。如何为他设计一条最短的旅行路线？ （从驻地出发，经过每个城市恰好一次，最后返回驻地）,2017/10/26,6、运输问题Transportation problem,某种原材料有 M个产地，现在需要将原材料从产地运往 N个使用这些原材料的工厂。假定 M个产地的产量和 N家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输成本最低？,2017/10/26,问题的两个共同特点,（1）目的都是从若干可能的安排或方案中寻求 某
4、种意义下的最优安排或方案，数学问题称 为最优化或优化问题。（2）它们都可用图形形式直观描述，数学上把这 种与图相关的结构称为网络。图和网络相关 的最优化问题就是网络最优化。 网络优化问题是以网络流为研究的对象，常 常被称为网络流或网络流规划等。,一、图论的基本概念,1 . 图与子图,G1：,如 G：,简单图：无自环、无重边的图。,2017/10/26,|V|=n表示图G中节点个数为n，此节点个数n也称为图G的阶|E|=m表示图G中边的个数为m任一顶点相关联的边的数目称为该顶点的度完全图：任意两点有边相连，用 表示 完全图的边，和每点的度是多少？,2 . 关联与相邻,3 . 链与圈,4. 有向图
5、与无向图,比较：,5. 树,例1 已知有5个城市，要在它们之间架设电话线网，要求任2城市都可通话（允许通过其它城市），并且电话线的根数最少。,特点：连通、无圈。,树无圈的连通图，记为T。,树的性质：（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上的权（
6、设ci ）。网络分析主要内容: 最小支撑树 最短路 最大流。,一. 最小支撑树问题,问题：求网络D的支撑树，使其权和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。,例 2 求如图网络的最小支撑树。,Kruskal, J.B. (1956). On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem. Proceedings of the American Mathematical Society 7, 48-50.,避圈法是一种选边的过程，其步骤如下：,1. 从网络
7、D中任选一点vi，找出与vi相关联的 权最小的边vi，vj，得第二个顶点vj；,2. 把顶点集V分为互补的两部分V1, 1 ，其中,2017/10/26,对G中各边按权大小顺序排列，不妨设为W1 W2 Wm,填写Wj对应的各边aj,S= ，i = 0，j=1,aj S构成回路？,|S| = n-1,ei+1=aj S=ei+1 Si=i +1 j=j+1,j=j+1,T*=S打印T*,END,Y,Y,N,N,用避圈法解例2,最小部分树如图上红线所示；最小权和为14。,思考：破圈法是怎样做的呢？,见圈就破，去掉其中权最大的。,最小支撑树问题的应用例子,已知有A、B、C、D、E、F六个城镇间的道路
8、网络 如图，现要在六个城镇间架设通讯网络（均沿道路架设），每段道路上的架设费用如图。求能保证各城镇均能通话且总架设费用最少的架设方案。,6,二. 最短路问题,2017/10/26,2. 方法：Dijkstra算法（Dijkstra，1959） Dijkstra, E.W. (1959). A note on two problems in connexion with graphs. Numerische Mathematik 1, 269271. 原理： Bellman最优化原理 若P是网络G中从Vs到Vt的一条最短路，Vl是P中除Vs与Vt外的任何一个中间点，则沿P从Vs到Vl的一条路P1
9、亦必是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的一条最短路矛盾。,2017/10/26,算法思想： 设G中从Vs到Vt的最小路 P：VsVjVkVt，则P不仅是从Vs到Vt的最小路，而且从Vs到P中任意中间点的最短路也在P上，为此可采用如下求解步骤： 为求得Vs到Vt的最短路，可先求得Vs到中间点的最短路，然后由中间点再逐步过
10、渡到终点Vt。 在计算过程中，需要把V中“经判断为最短路P途径之点i”和“尚未判断是否为最短路P途径之点j”区分开来，可设置集合I和J,前者归入I，后者归入J，并令算法初始时，I中仅包含Vs，其他点全在J中，然后随着求解过程的进行，I中的点逐渐增加（相应J中的点逐渐减少），直到终点Vt归入I（相应J=），此时迭代结束。I称为已标号集合,J称为未标号集合。,2017/10/26, 为区分中间点Vk是否已归入I中以及逆向求解最短路的方便，可在归入I中的点Vj上方给予双标号（lj, Vk），此中lj表示从Vs到Vj最短路的距离，而Vk则为从Vs到Vj最短路P中Vj的前一途径点。 为在计算机上实现上述
11、求解思想，还需引入G中各点间一步可达距离阵D=(dij)nn，其中|V|=n,2017/10/26,由图G建立一步可达距离阵D=(dij)nn,给V1(Vs)括号(l1,Vk)=(0,s)给出已标号集合I和未标号集合J的元素,对于给定的I和J，确定集合A=aij |ViI，Vj J,计算距离,给Vk括号(lk ,Vh) lk=lh + Whk,I=I + Vk J=J Vk,A= 或 J,从Vt 逆向搜索双括号，可得最小路P途径各点及最小路距离,END,N,Y,Dijkstra算法,用标号法解例3,0，v1,2，v1,3，v1,4，v2,7，v3,8，v5,13，v6,最短距为13；,最短路为
12、v1-v2-v3-v5-v6-v7。,2017/10/26,2017/10/26,迭代过程,2017/10/26,最短路问题应用,厂址选择厂址布局设备更新网络线路安装工程设计企业管理,最短路问题的应用例子,某汽车公司正在制订5年内购买汽车的计划。下面给出一辆新汽车的价格以及一辆汽车的使用维修费用(万元)： 年份 1 2 3 4 5 年初价格 11 11 12 12 13 使用年数 01 12 23 34 45 年维护费用 5 6 8 11 18试用网络分析中求最短路的方法确定公司可采用的最优策略。,2017/10/26,解：设Vi i年初购进一台新设备aij i年初购进之新设备使用到第j年初i
13、ji年初购进之新设备使用到第j年初之总费用,方法：以年号作顶点绘图，连线表示连续使用期 间，以费用作路长。,2017/10/26,2017/10/26,2017/10/26,费用矩阵,方法：以年号作顶点绘图，连线表示连续使用期间，以 费用作路长。,2017/10/26,2017/10/26,可知最短费用流（相当于最短路） P： V1 V3 V6 或者是V1 V4 V6 | P| = 53万元结论：公司五年期设备更新方案有两个：A与B，总费用均为53万元。 A 方案：第1年初购置设备使用到第3年初,第3年初再购置新设备使用到第 5年末（第6年初） B 方案：第1年初购置设备使用到第4年初，第4年
14、初再购置新设备使用到第5年末（第6年初）,三. 最大流问题,1. 问题 已知网络D=（V，A，C），其中V为顶点集，A为弧集，C=cij为容量集， cij 为弧（vi，vj ）上的容量。现D上要通过一个流f=fij，其中fij 为弧（vi，vj ）上的流量。问应如何安排流量fij可使D上通过的总流量v最大？,可采用线性规划的单纯型法求解,（容量约束）（平衡条件）,问题：最大流问题的决策变量、目标函数、约束条件各是什么？,2. 数学模型,3. 基本概念与定理,如：在前面例举的网络流问题中，若已给定一个可行流（如括号中后一个数字所示），请指出相应的弧的类型。,（2）可增值链（增广链）,（3） 截集与截量,截量：截集上的容量和，记为 。,例4 对于下图，若V1=vs，v1，请指出相应的截集与截量。,例4 对于下图，若V1=vs，v1，请指出相应的截集与截量。,解：,（4） 流量与截量的关系,截集上的流量和,相应于截集的反向弧上流量和,最大流最小割定理：,4. 解法,（5） 最大流的判别条件,步骤：,2017/10/26,1算法思想,双标号算法,2017/10/26,N,Y,Y,N,2、调整步骤,例5 用标号法求下面网络的最大流。,
