图论和网络分析算法及Matlab实现(Graph_and_Network_Analysis)讲课教案.ppt

《图论和网络分析算法及Matlab实现(Graph_and_Network_Analysis)讲课教案.ppt》由会员分享，可在线阅读，更多相关《图论和网络分析算法及Matlab实现(Graph_and_Network_Analysis)讲课教案.ppt（74页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、图论图论(t ln)(t ln)与网络分析与网络分析 (Graph Theory and (Graph Theory and Network Analysis)Network Analysis)一、图论的基本概念一、图论的基本概念 二、网络分析算法二、网络分析算法(sun(sun f)f)三、三、MatlabMatlab实现实现第一页，共74页。2022/12/9涉及网络涉及网络(wnglu)(wnglu)优化的数学建模问优化的数学建模问题题1、最短路问题、最短路问题货柜车司机奉命货柜车司机奉命(fng mng)在最短的时间内在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地将一车货物从甲地

2、运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。要找到一条从甲地到乙地的最短路。第二页，共74页。2022/12/92 2、最小支撑、最小支撑(zh chng)(zh chng)树问题树问题某一地区有若干个主要城市，现准备某一地区有若干个主要城市，现准备(zhnbi)修修建高速公路把这些城市连接起来，使得从其中任何建高速公路把这些城市连接起来，使得从其中任何一个城

3、市都可以经高速公路直接或间接到达另一个一个城市都可以经高速公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速城市。假定已经知道了任意两个城市之间修建高速公路成本，那么应如何决定在哪些城市间修建高速公路成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？公路，使得总成本最小？第三页，共74页。2022/12/93 3、指派指派(zhpi)(zhpi)问题问题Assignment problemAssignment problem 一家公司经理安排(npi)N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报不同。如何分配工作

4、方案可以使总回报最大？第四页，共74页。2022/12/94 4、中国、中国(zhn u)(zhn u)邮递员问题邮递员问题Chinese postman problemChinese postman problem一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少(zhsho)一次，最后返回邮局）？我国管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。第五页，共74页。2022/12/95 5、旅行、旅行(lxng)(lxng)商问题商问题Traveling salesman problemTraveling salesman

5、 problem一一名名推推销销员员准准备备前前往往(qinwng)(qinwng)若若干干城城市市推推销销产产品品。如如何何为为他他设设计计一一条条最最短短的的旅旅行行路路线线？（从从驻驻地地出出发发，经经过过每每个城市恰好一次，最后返回驻地）个城市恰好一次，最后返回驻地）第六页，共74页。2022/12/96 6、运输、运输(ynsh)(ynsh)问题问题Transportation problemTransportation problem 某某种种原原材材料料有有 M M个个产产地地，现现在在需需要要将将原原材材料料从从产产地地运运往往 N N个个使使用用这这些些原原材材料料的的工工厂

6、厂。假假定定 M M个个产产地地的的产产量量和和 N N家家工工厂厂的的需需要要量量已已知知，单单位位产产品品从从任任一一产产地地到到任任(do(do rn)rn)一一工工厂厂的的运运费费已已知知，那那么么如如何何安安排排运运输输方方案可以使总运输成本最低？案可以使总运输成本最低？第七页，共74页。2022/12/9问题的两个共同问题的两个共同(gngtng)(gngtng)特点特点（1 1）目的都是从若干可能的安排或方案中寻求）目的都是从若干可能的安排或方案中寻求 某种意义下的最优安排或方案，数学问题称某种意义下的最优安排或方案，数学问题称 为最优化或优化问题。为最优化或优化问题。（2 2）

7、它们都可用图形形式直观描述，数学上把这）它们都可用图形形式直观描述，数学上把这 种与图相关的结构称为网络。图和网络相关种与图相关的结构称为网络。图和网络相关 的最优化问题就是的最优化问题就是(jish)(jish)网络最优化。网络最优化。网络优化问题是以网络流为研究的对象，常网络优化问题是以网络流为研究的对象，常 常被称为网络流或网络流规划等。常被称为网络流或网络流规划等。第八页，共74页。2022/12/9 一、图论(t ln)的基本概念1.图与子图e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如 G：简单(jindn)图：无自环、无重边的图。第九页，

8、共74页。2022/12/9|V|=n表示图G中节点个数为n，此节点个数n也称为图G的阶|E|=m表示图G中边的个数为m任一顶点相关联的边的数目称为该顶点的度完全图：任意(rny)两点有边相连，用 表示 完全图的边，和每点的度是多少？第十页，共74页。2022/12/92.关联(gunlin)与相邻第十一页，共74页。2022/12/9第十二页，共74页。2022/12/93.链与圈第十三页，共74页。2022/12/94.有向图与无向图，圈，回路比较(bjio)：第十四页，共74页。2022/12/9v1v2v3v5v4834217第十五页，共74页。2022/12/9第十六页，共74页。2

9、022/12/95.树 例1 已知有5个城市，要在它们(t men)之间架设电话线网，要求任2城市都可通话（允许通过其它城市），并且电话线的根数最少。v1v2v3v5v4 特点(tdin)：连通、无圈。树无圈的连通(lintng)图，记为T。第十七页，共74页。2022/12/9v1v2v3v5v4树的性质：（1）树的任2点间有且仅有1链；（2）在树中任去掉(q dio)1边，则不连通；（3）在树中不相邻2点间添1边，恰成1圈；（4）若树T有n个顶点，则T有n-1条边。第十八页，共74页。2022/12/96.图的支撑(zh chng)树 若图G=（V，E）的子图T=（V，E）是树，则称T为G

10、的支撑(zh chng)树。特点(tdin)边少、点不少。性质：G连通，则G必有支撑树。证：破圈、保连通。第十九页，共74页。2022/12/9二、网络分析网络(wnglu)赋权图，记D=（V，E，C），其中C=c1，cn，ci为边ei上的权（设ci ）。网络(wnglu)分析主要内容:最小支撑树 最短路 最大流。第二十页，共74页。2022/12/9一.最小支撑(zh chng)树问题问题(wnt)：求网络D的支撑树，使其权和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例 2 求如图网络(wnglu)的最小支撑树。v5v1v3v6v4v2v7255233575

11、711Kruskal,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.第二十一页，共74页。2022/12/9避圈法是一种选边的过程，其步骤(bzhu)如下：1.从网络(wnglu)D中任选一点vi，找出与vi相关联的 权最小的边vi，vj，得第二个顶点vj；2.把顶点集V分为互补的两部分V1,1，其中第二十二页，共74页。2022/12/9对对G中各

12、边按权大小中各边按权大小(dxio)顺序排列，不妨设为顺序排列，不妨设为W1 W2 Wm填写填写(tinxi)Wj对应的各边对应的各边aj S=，i=0，j=1ajS构成构成(guchng)回路？回路？|S|=n-1=n-1ei+1=aj S=ei+1 Si=i+1 j=j+1j=j+1T*=S打印打印T*ENDYYNN第二十三页，共74页。2022/12/9用避圈法解例2v5v1v3v6v4v2v7255233575711最小部分(b fen)树如图上红线所示；最小权和为14。思考(sko)：破圈法是怎样做的呢？见圈就破，去掉(q dio)其中权最大的。第二十四页，共74页。2022/12/

13、9最小支撑树问题的应用(yngyng)例子 已知有A、B、C、D、E、F六个城镇间的道路网络 如图，现要在六个城镇间架设(jish)通讯网络（均沿道路架设），每段道路上的架设(jish)费用如图。求能保证各城镇均能通话且总架设(jish)费用最少的架设(jish)方案。6EACBFD5109353978284第二十五页，共74页。2022/12/9二.最短路(dunl)问题1.问题：求网络D中一定点v1到其它点的最短路。例3 求如图网络中v1至v7的最短路，图中数字为两点间距离。v5v1v3v6v4v2v7255233575711第二十六页，共74页。2022/12/92.方法：Dijkstr

14、a算法（Dijkstra，1959）Dijkstra,E.W.(1959).A note on two problems in connexion with graphs.Numerische Mathematik 1,269271.原理：Bellman最优化原理 若P是网络G中从Vs到Vt的一条(y tio)最短路，Vl是P中除Vs与Vt外的任何一个中间点，则沿P从Vs到Vl的一条(y tio)路P1亦必是Vs到Vl的最短路。证明（反证）：若P1不是从Vs到Vl的最短路，则存在另一条(y tio)Vs到Vl的路P2使W(P2)W(P1)，若记路P中从Vl到Vt的路为P3。则有W(P2)+W(

15、P3)300米)对坡度的限制 0.125=0 0.100 第六十二页，共74页。2022/12/9模型模型(mxng)(mxng)计算方法计算方法 (1)(1)对地图网格加密，形成图。对地图网格加密，形成图。(2)(2)计算计算(j sun)(j sun)网格的距离，用费网格的距离，用费用作为权值。用作为权值。(3)(3)求赋权图两点间的最短距离。求赋权图两点间的最短距离。第六十三页，共74页。2022/12/9参考答案参考答案第六十四页，共74页。2022/12/919981998年全国大学生数学年全国大学生数学(shxu)(shxu)建模竞赛建模竞赛 灾情巡视路线，下图为某县的乡（镇）、村

16、公路网灾情巡视路线，下图为某县的乡（镇）、村公路网示意图，公路边的数字为该路段示意图，公路边的数字为该路段(l dun)(l dun)的公里的公里数。今年夏天该县遭受水灾。为考察灾情、组织自数。今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡救，县领导决定，带领有关部门负责人到全县各乡（镇）、村巡视。巡视路线指从县政府所在地出发，（镇）、村巡视。巡视路线指从县政府所在地出发，走遍各乡（镇）、村，又回到县政府所在地的路线。走遍各乡（镇）、村，又回到县政府所在地的路线。第六十五页，共74页。2022/12/91.若分三组（路）巡视，试设计总路程最短且各组尽可能均

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

18、关于T,t和和V的假定下，如果巡视人员足够多，完成的假定下，如果巡视人员足够多，完成巡视的最短时间是多少；给出在这种最短时间完成巡视的巡视的最短时间是多少；给出在这种最短时间完成巡视的要求下，你认为最佳的巡视路线。要求下，你认为最佳的巡视路线。第六十六页，共74页。2022/12/9乡村乡村(xingcn)分布图分布图第六十七页，共74页。2022/12/9点的行遍性问题点的行遍性问题(wnt)1 1、图论、图论-哈密尔顿问题（是否存在经过所有点一次的圈）哈密尔顿问题（是否存在经过所有点一次的圈）2 2、组合优化、组合优化-旅行商问题（赋权图经过所有顶点至少一次）旅行商问题（赋权图经过所有顶点

19、至少一次）非完全图的多旅行商问题非完全图的多旅行商问题两点间的最短路长度作为两点间的权，构造完全图。两点间的最短路长度作为两点间的权，构造完全图。两边权之和不小于第三边的权两边权之和不小于第三边的权=完全图的最优哈密尔顿圈完全图的最优哈密尔顿圈=原图的最优旅行商问题。原图的最优旅行商问题。完全图完全图-增广完全图增广完全图=求最优哈密尔顿圈求最优哈密尔顿圈近似算法或分组后直接近似算法或分组后直接(zhji)(zhji)搜索搜索注意注意（1 1）两点间的最短路长度可用两点间的最短路长度可用DijkstraDijkstra算法算法（2 2）多旅行商问题多旅行商问题=最优哈密尔顿圈最优哈密尔顿圈第六

20、十八页，共74页。2022/12/9线性规划线性规划(xin xn u hu)模模型型第六十九页，共74页。2022/12/9问题解答：问题解答：1、分三组（路）巡视，试设计总路程最短且、分三组（路）巡视，试设计总路程最短且 各组各组尽可能均衡尽可能均衡(jnhng)的巡视路线。的巡视路线。目标函数：目标函数：min(C1+C2+C3)限制条件：限制条件：min(C3-C1)或或 者者：min(C1)2、假定巡视人员在各乡（镇）停留时间、假定巡视人员在各乡（镇）停留时间T=2小时，在小时，在各村停留时间各村停留时间t=1小时，汽车行驶速度小时，汽车行驶速度V=35公里公里/小时。小时。要在要在

21、24小时内完成巡视，至少应分几组；给出这种分组小时内完成巡视，至少应分几组；给出这种分组下最佳的巡视路线。下最佳的巡视路线。第七十页，共74页。2022/12/9 目标函数：目标函数：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的假定下，如果巡视的假定下，如果巡视(xnsh)(xnsh)人员足够多，人员

22、足够多，完成巡视完成巡视(xnsh)(xnsh)的最短时间是多少；给出在这种最短时间完成巡的最短时间是多少；给出在这种最短时间完成巡视视(xnsh)(xnsh)的要求下，你认为最佳的巡视的要求下，你认为最佳的巡视(xnsh)(xnsh)路线。路线。单独巡视单独巡视(xnsh)(xnsh)的最短时间的最短时间=最远距离最远距离 （1 1）每组时间不超过最远距离时间）每组时间不超过最远距离时间 （2 2）巡视）巡视(xnsh)(xnsh)组足够少，组足够少，2222组组4 4、若巡视若巡视(xnsh)(xnsh)组数已定组数已定(如三组如三组)，要求尽快完成巡视，要求尽快完成巡视(xnsh)(xn

23、sh)，讨论，讨论T T，t t和和 V V改变对最佳巡视改变对最佳巡视(xnsh)(xnsh)路线的影响。路线的影响。讨论花费时间函数：讨论花费时间函数：Hi=2mi+ni+Ci/VHi=2mi+ni+Ci/V注意：多旅行商问题注意：多旅行商问题=单旅行商问题（单旅行商问题（LINGOLINGO）第七十一页，共74页。2022/12/920052005年全国大学生数学建模竞赛年全国大学生数学建模竞赛(jngsi)DVD(jngsi)DVD在线租赁在线租赁随随着着信信息息时时代代的的到到来来，网网络络成成为为人人们们生生活活中中越越来来越越不不可可或或缺缺的的元元素素之之一一。许许多多网网站站

24、利利用用其其强强大大的的资资源源和和知知名名度度，面面向向其其会会员员群群提提供供日日益益专专业业化化和和便便捷捷化化的的服服务务。例例如如，音音像像制制品品的的在在线线租租赁赁就就是是一一种种可可行行的的服服务务。这这项项服服务务充充分分发发挥挥了了网网络络的的诸诸多多优优势势，包包括括传传播播范范围围广广泛泛、直直达达核核心心消消费费群群、强强烈烈(qin(qin li)li)的的互互动动性性、感感官官性性强强、成成本本相相对对低低廉等，为顾客提供更为周到的服务。廉等，为顾客提供更为周到的服务。考考虑虑如如下下的的在在线线DVDDVD租租赁赁问问题题。顾顾客客缴缴纳纳一一定定数数量量的的月

25、月费费成成为为会会员员，订订购购DVDDVD租租赁赁服服务务。会会员员对对哪哪些些DVDDVD有有兴兴趣趣，只只要要在在线线提提交交订订单单，网网站站就就会会通通过过快快递递的的方方式式尽尽可可能能满满足足要要求求。会会员员提提交交的的订订单单包包括括多多张张DVDDVD，这这些些DVDDVD是是基基于于其其偏偏爱爱程程度度排排序序的的。网网站站会会根根据据手手头头现现有有的的DVDDVD数数量量和和会会员员的的订订单单进进行行分分发发。每每个个会会员员每每个个月月租租赁赁次次数数不不得得超超过过2 2次次，每每次次获获得得3 3张张DVDDVD。会会员员看看完完3 3张张DVDDVD之之后后

26、，只只需需要要将将DVDDVD放放进进网网站站提提供供的的信信封封里里寄寄回回（邮邮费费由由网网站承担），就可以继续下次租赁。请考虑以下问题：站承担），就可以继续下次租赁。请考虑以下问题：第七十二页，共74页。2022/12/91)1)网网站站正正准准备备购购买买一一些些新新的的DVDDVD，通通过过问问卷卷调调查查10001000个个会会员员，得得到到了了愿愿意意观观看看这这些些DVDDVD的的人人数数（表表1 1给给出出了了其其中中5 5种种DVDDVD的的数数据据）。此此外外，历历史史数数据据显显示示，60%60%的的会会员员每每月月租租赁赁DVDDVD两两次次，而而另另外外的的40%4

27、0%只只租租一一次次。假假设设(jish)(jish)网网站站现现有有1010万万个个会会员员，对对表表1 1中中的的每每种种DVDDVD来来说说，应应该该至至少少准准备备多多少少张张，才才能能保保证证希希望望看看到到该该DVDDVD的的会会员员中中至至少少50%50%在在一一个个月月内内能能够够看看到到该该DVDDVD？如如果果要要求求保保证证在在三三个个月月内内至至少少95%95%的会员能够看到该的会员能够看到该DVDDVD呢？呢？2 2）表表2 2中中列列出出了了网网站站手手上上100100种种DVDDVD的的现现有有张张数数和和当当前前需需要要处处理理的的10001000位位会会员员的

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