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

1、图论与网络分析图论与网络分析 (Graph Theory and Network Analysis)Graph Theory and Network Analysis)一、图论的基本概念一、图论的基本概念 二、网络分析算法二、网络分析算法三、三、MatlabMatlab实现实现2022-11-8涉及网络优化的数学建模问题涉及网络优化的数学建模问题1、最短路问题、最短路问题货柜车货柜车司机司机奉命在最短的时间内将一车货物奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网从甲地运往乙地。从甲地到乙地的公路网纵纵横交错横交错，因此有多种行车路线，这名司机应，因此有多种行车路线，这名司机

2、应选择哪条线路呢？假设货柜车的运行速度是选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条恒定的，那么这一问题相当于需要找到一条从甲地到乙地的从甲地到乙地的最短路最短路。2022-11-82 2、最小支撑树问题最小支撑树问题某一地区有若干个主要城市，现准备修建高速公某一地区有若干个主要城市，现准备修建高速公路把这些路把这些城市连接城市连接起来，使得从其中任何一个城起来，使得从其中任何一个城市都可以经高速公路市都可以经高速公路直接或间接直接或间接到达另一个城市到达另一个城市。假定已经知道了任意两个城市之间修建。假定已经知道了任意两个城市之间修建高速公高速公路成本路成本，

3、那么应如何决定在哪些城市间修建高速，那么应如何决定在哪些城市间修建高速公路，使得公路，使得总成本最小总成本最小？2022-11-83 3、指派问题指派问题Assignment problemAssignment problem 一家公司经理一家公司经理安排安排N N名员工去完成名员工去完成N N项任务，每项任务，每人一项。由于各员工的人一项。由于各员工的特点不同特点不同，不同的员工，不同的员工去完成同一项任务时所获得的去完成同一项任务时所获得的回报不同回报不同。如何。如何分配工作方案可以使总分配工作方案可以使总回报最大回报最大？2022-11-84 4、中国邮递员问题、中国邮递员问题Chine

4、se postman problemChinese postman problem一名一名邮递员邮递员负责投递某个街区的邮件。如何为负责投递某个街区的邮件。如何为他（她）设计一条最短的他（她）设计一条最短的投递路线投递路线（从邮局出（从邮局出发，经过投递区内每条发，经过投递区内每条街道至少一次街道至少一次，最后返，最后返回邮局）？回邮局）？我国管梅谷教授我国管梅谷教授1960年首先提出，年首先提出，国际上称之为中国邮递员问题。国际上称之为中国邮递员问题。2022-11-85 5、旅行商问题、旅行商问题Traveling salesman problemTraveling salesman pr

5、oblem一名一名推销员推销员准备前往若干准备前往若干城市城市推销产推销产品。如何为他设计一条品。如何为他设计一条最短最短的旅行的旅行路线？路线？（从驻地出发，经过每个城（从驻地出发，经过每个城市恰好一次，最后返回驻地）市恰好一次，最后返回驻地）2022-11-86 6、运输问题、运输问题Transportation problemTransportation problem 某种原材料有某种原材料有 M M个产地个产地，现在需要将原材料从产，现在需要将原材料从产地运往地运往 N N个使用这些原材料的工厂。假定个使用这些原材料的工厂。假定 M M个产个产地的产量和地的产量和 N N家工厂家工厂

6、的需要量已知，单位产品从的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排任一产地到任一工厂的运费已知，那么如何安排运输方案可以使总运输方案可以使总运输成本运输成本最低？最低？2022-11-8问题的两个共同特点问题的两个共同特点（1 1）目的都是从若干可能的安排或方案中寻求）目的都是从若干可能的安排或方案中寻求 某种意义下的某种意义下的最优安排最优安排或方案，数学问题称或方案，数学问题称 为最优化或为最优化或优化问题优化问题。（2 2）它们都可用）它们都可用图形图形形式直观描述，数学上把这形式直观描述，数学上把这 种与图相关的结构称为种与图相关的结构称为网络网络。图和网络相关

7、图和网络相关 的最优化问题就是的最优化问题就是网络最优化网络最优化。网络优化问题是以网络流为研究的对象，常网络优化问题是以网络流为研究的对象，常 常被称为网络流或常被称为网络流或网络流规划网络流规划等。等。一、图论的基本概念1.图与子图11(,),nmGV EVvvEee，其中为，图顶点集为边集。11111(,),GV EVV EE其中子图。e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如 G：简单图：无自环、无重边的图。2022-11-8|V|=n表示图G中节点个数为n，此节点个数n也称为图G的阶|E|=m表示图G中边的个数为m 任一顶点相关联的边的数

8、目称为该顶点的度 完全图：任意两点有边相连，用 表示 完全图的边，和每点的度是多少？nK2.关联与相邻121212,()ev vev vvve（边与点关系）：若 是二点间的边，记称或联与关关联。12121212 vvvveeee（边与边、点与点）：点 与 有公共边，称 与 相邻；边 与 有公共点，称 与邻接相邻。n1110100110001000110100001101：关联矩阵：*m或者是m*n图在计算机中的表示n0111101011011011邻接矩阵：*n邻接矩阵为对称阵，简单图对角线元素为03.链与圈1 1 2 211 ,MatlabkkiiiGv ev eevev vG:由 中的某些

9、点与边相间构成的序列，若满足则称此边点序链列为 中的一条链。链在中的存储：只储存顶点标号圈：封闭的链。G：图 中任二点间至少存连通图在一条链。4.有向图与无向图(,),(,).,),kijijijGV EGvv vv vGGv v无向图也可记若点对无序，称 为；否则称 为。为区别起见，称有向图图有向图弧的边为，记（在图上用箭线表示。），路有向图：弧（，链无向图：边,，圈，回路比较：1ijijavv 有向图的存储：行为起点，列为终点存在弧赋权图：边有长度v1v2v3v5v4834217 W=.41.99.51.32.15.45.38.32.36.29.21;DG=sparse6 1 2 2 3

10、4 4 5 5 6 1,2 6 3 5 4 1 6 3 4 3 5,Wview(biograph(DG,ShowWeights,on)UG tril DG DGview(biograph(UG,ShowWeights,on)；赋权图在Matlab中的存储：5.树 例1 已知有5个城市，要在它们之间架设电话线网，要求任2城市都可通话（允许通过其它城市），并且电话线的根数最少。v1v2v3v5v4 特点：连通、无圈。树无圈的连通图，记为T。v1v2v3v5v4树的性质：（1）树的任2点间有且仅有1链；（2）在树中任去掉1边，则不连通；（3）在树中不相邻2点间添1边，恰成1圈；（4）若树T有n个顶点

11、，则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).On the Shortest Span

12、ning Subtree of a Graph and the Traveling Salesman Problem.Proceedings of the American Mathematical Society 7,48-50.避圈法是一种选边的过程，其步骤如下：1.从网络D中任选一点vi，找出与vi相关联的 权最小的边vi，vj，得第二个顶点vj；2.把顶点集V分为互补的两部分V1,1，其中V集；不与已选边相关联的点，与已选边相关联的点集，11VV其中权最小的；挑选其中考虑所有这样的边 ,3.11svsvvvjiji。即，直至全部顶点属于重复)(3 4.11ss2022-11-8对对G中

13、各边按权大小顺序排列，不妨设为中各边按权大小顺序排列，不妨设为W1 W2 Wm填写填写Wj对应的各边对应的各边aj S=，i=0，j=1aj S构成回路？构成回路？|S|=n-1=n-1ei+1=aj S=ei+1 Si=i+1 j=j+1j=j+1T*=S打印打印T*ENDYYNN用避圈法解例2v5v1v3v6v4v2v7255233575711最小部分树如图上红线所示；最小权和为14。思考：破圈法是怎样做的呢？见圈就破，去掉其中权最大的。最小支撑树问题的应用例子 已知有A、B、C、D、E、F六个城镇间的道路网络 如图，现要在六个城镇间架设通讯网络（均沿道路架设），每段道路上的架设费用如图。

14、求能保证各城镇均能通话且总架设费用最少的架设方案。6EACBFD5109353978284二.最短路问题1.问题：求网络D中一定点v1到其它点的最短路。例3 求如图网络中v1至v7的最短路，图中数字为两点间距离。v5v1v3v6v4v2v72552335757112022-11-8 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

15、的一条最短路，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)300 300米米)对坡度对坡度的限制的限制 0.125=0 0.100 2022-11-8模型计算方法模型计算方法 (1)(1)对地图网格加密，形成图。对地图网格加密，形成图。(2)(2)计算网格的距离，用费用作为权值。计算网格的距离，用费用作为权值。(3)(3)求赋权图两点间的最短距离。求赋权图两点间的最短距离。2022

16、-11-8参考答案参考答案2022-11-8 灾情巡视路线，下图为某县的乡（镇）、灾情巡视路线，下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段村公路网示意图，公路边的数字为该路段的公里数。今年夏天该县遭受水灾。为考的公里数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，走遍。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的各乡（镇）、村，又回到县政府所在地的路线。路线。2022-11-81.若分三组（路）巡

17、视，试设计总路程最短且各组尽可若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的巡视路线。能均衡的巡视路线。2.假定巡视人员在各乡（镇）停留时间假定巡视人员在各乡（镇）停留时间T=2T=2小时，在各小时，在各村停留时间村停留时间t=1t=1小时，汽车行驶速度小时，汽车行驶速度V=35V=35公里公里/小时。小时。要在要在2424小时内完成巡视，至少应分几组；给出这种分小时内完成巡视，至少应分几组；给出这种分组下你认为最佳的巡视路线。组下你认为最佳的巡视路线。3.若巡视组数已定若巡视组数已定(如三组如三组)，要求尽快完成巡视，讨论，要求尽快完成巡视，讨论T，t和和V改变对最佳巡视路线的影响。

18、改变对最佳巡视路线的影响。4.上述关于上述关于T,t和和V的假定下，如果巡视人员足够多，的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。成巡视的要求下，你认为最佳的巡视路线。2022-11-8乡村分布图乡村分布图2022-11-8点的行遍性问题点的行遍性问题1 1、图论、图论-哈密尔顿问题（是否存在经过所有点一次的圈）哈密尔顿问题（是否存在经过所有点一次的圈）2 2、组合优化、组合优化-旅行商问题（赋权图经过所有顶点至少一次）旅行商问题（赋权图经过所有顶点至少一次）非完全图的多旅行商

19、问题非完全图的多旅行商问题v 两点间的最短路长度作为两点间的权，构造完全图。两点间的最短路长度作为两点间的权，构造完全图。v 两边权之和不小于第三边的权两边权之和不小于第三边的权=v 完全图的最优哈密尔顿圈完全图的最优哈密尔顿圈=原图的最优旅行商问题。原图的最优旅行商问题。v 完全图完全图-增广完全图增广完全图=求最优哈密尔顿圈求最优哈密尔顿圈v 近似算法或分组后直接搜索近似算法或分组后直接搜索v 注意注意（1 1）两点间的最短路长度可用两点间的最短路长度可用DijkstraDijkstra算法算法（2 2）多旅行商问题多旅行商问题=最优哈密尔顿圈最优哈密尔顿圈2022-11-8线性规划模型线

20、性规划模型2022-11-8问题解答：问题解答：1 1、分三组（路）巡视，试设计总路程最短且分三组（路）巡视，试设计总路程最短且 各组尽可能均衡的巡视路线。各组尽可能均衡的巡视路线。目标函数：目标函数：min(C1+C2+C3)min(C1+C2+C3)限制条件：限制条件：min(C3-C1)min(C3-C1)或或 者者 ：min(C1)min(C1)2、假定巡视人员在各乡（镇）停留时间假定巡视人员在各乡（镇）停留时间T=2T=2小时小时，在各村停留时间，在各村停留时间t=1t=1小时，汽车行驶速度小时，汽车行驶速度V=35V=35公里公里/小时。要在小时。要在2424小时内完成巡视，至少应

21、分小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线几组；给出这种分组下最佳的巡视路线。2022-11-8 目标函数：目标函数：min(H1+H2+H3)min(H1+H2+H3)花费时间：花费时间：Hi=2mi+ni+Ci/VHi=2mi+ni+Ci/V 限制条件：限制条件：min(max(Hi)min(max(Hi)总时间总时间6969小时小时=至少至少4 4组，组，4 4组的路线可以找到。组的路线可以找到。3 3、在上述关于在上述关于T,tT,t和和V V的假定下，如果巡视人员足够多，完成的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的要求巡视

22、的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。下，你认为最佳的巡视路线。单独巡视的最短时间单独巡视的最短时间=最远距离最远距离 （1）每组时间不超过最远距离时间）每组时间不超过最远距离时间 （2）巡视组足够少，）巡视组足够少，2222组组4 4、若巡视组数已定若巡视组数已定(如三组如三组)，要求尽快完成巡视，讨论，要求尽快完成巡视，讨论T T，t t和和 V V改变对最佳巡视路线的影响。改变对最佳巡视路线的影响。讨论花费时间函数：讨论花费时间函数：Hi=2mi+ni+Ci/VHi=2mi+ni+Ci/V注意：多旅行商问题注意：多旅行商问题=单旅行商问题（单旅行商问

23、题（LING2LING2）2022-11-8DVD在在线租赁线租赁随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许随着信息时代的到来，网络成为人们生活中越来越不可或缺的元素之一。许多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化多网站利用其强大的资源和知名度，面向其会员群提供日益专业化和便捷化的服务。例如，音像制品的在线租赁就是一种可行的服务。这项服务充分发的服务。例如，音像制品的在线租赁就是一种可行的服务。这项服务充分发挥了网络的诸多优势，包括传播范围广泛、直达核心消费群、强烈的互动性、挥了网络的诸多优势，包括传播范围广泛、直达核心消费群、强烈的互动性、感

24、官性强、成本相对低廉等，为顾客提供更为周到的服务。感官性强、成本相对低廉等，为顾客提供更为周到的服务。考虑如下的在线考虑如下的在线DVD租赁问题。顾客缴纳一定数量的月费成为会员，订购租赁问题。顾客缴纳一定数量的月费成为会员，订购DVD租赁服务。会员对哪些租赁服务。会员对哪些DVD有兴趣，只要在线提交订单，网站就会通过有兴趣，只要在线提交订单，网站就会通过快递的方式尽可能满足要求。会员提交的订单包括多张快递的方式尽可能满足要求。会员提交的订单包括多张DVD，这些这些DVD是基是基于其偏爱程度排序的。网站会根据手头现有的于其偏爱程度排序的。网站会根据手头现有的DVD数量和会员的订单进行分数量和会员

25、的订单进行分发。每个会员每个月租赁次数不得超过发。每个会员每个月租赁次数不得超过2次，每次获得次，每次获得3张张DVD。会员看完会员看完3张张DVD之后，只需要将之后，只需要将DVD放进网站提供的信封里寄回（邮费由网站承担），放进网站提供的信封里寄回（邮费由网站承担），就可以继续下次租赁。请考虑以下问题：就可以继续下次租赁。请考虑以下问题：2022-11-81)1)网站正准备购买一些新的网站正准备购买一些新的DVD，通过问卷调查通过问卷调查1000个会员，得到了愿意观个会员，得到了愿意观看这些看这些DVD的人数（表的人数（表1给出了其中给出了其中5种种DVD的数据）。此外，历史数据显示，的数据

26、）。此外，历史数据显示，60%的会员每月租赁的会员每月租赁DVD两次，而另外的两次，而另外的40%只租一次。假设网站现有只租一次。假设网站现有10万个万个会员，对表会员，对表1中的每种中的每种DVD来说，应该至少准备多少张，才能保证希望看到该来说，应该至少准备多少张，才能保证希望看到该DVD的会员中至少的会员中至少50%在一个月内能够看到该在一个月内能够看到该DVD？如果要求保证在三个月内如果要求保证在三个月内至少至少95%的会员能够看到该的会员能够看到该DVD呢？呢？2）表表2中列出了网站手上中列出了网站手上100种种DVD的现有张数和当前需要处理的的现有张数和当前需要处理的1000位会员位

27、会员的在线订单（表的在线订单（表2的数据格式示例如下表的数据格式示例如下表2，具体数据请下），如何对这些，具体数据请下），如何对这些DVD进行分配，才能使会员获得最大的满意度？请具体列出前进行分配，才能使会员获得最大的满意度？请具体列出前30位会员（即位会员（即C0001C0030）分别获得哪些分别获得哪些DVD。3）继续考虑表继续考虑表2，并假设表，并假设表2中中DVD的现有数量全部为的现有数量全部为0。如果你是网站经营。如果你是网站经营管理人员，你如何决定每种管理人员，你如何决定每种DVD的购买量，以及如何对这些的购买量，以及如何对这些DVD进行分配，才进行分配，才能使一个月内能使一个月内95%的会员得到他想看的的会员得到他想看的DVD，并且满意度最大？并且满意度最大？如果你是网站经营管理人员，你觉得在如果你是网站经营管理人员，你觉得在DVD的需求预测、购买和分配中还有哪的需求预测、购买和分配中还有哪些重要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型。些重要问题值得研究？请明确提出你的问题，并尝试建立相应的数学模型。2022-11-8