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

《图论和网络分析算法及Matlab实现(Graph and Network Analysis).ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论与网络分析(GraphTheoryandNetworkAnalysis)一、图论的基本概念二、网络分析算法三、Matlab实现2021/7/21涉及网络优化的数学建模问题1、最短路问题货柜车司机奉命在最短的时间内将一车货物从甲地运往乙地。从甲地到乙地的公路网纵横交错，因此有多种行车路线，这名司机应选择哪条线路呢？假设货柜车的运行速度是恒定的，那么这一问题相当于需要找到一条从甲地到乙地的最短路。2021/7/212、最小支撑树问题某一地区有若干个主要城市，现准备修建高速公路把这些城市连接起来，使得从其中任何一个城市都可以经高速

2、公路直接或间接到达另一个城市。假定已经知道了任意两个城市之间修建高速公路成本，那么应如何决定在哪些城市间修建高速公路，使得总成本最小？2021/7/213、指派问题Assignmentproblem一家公司经理安排N名员工去完成N项任务，每人一项。由于各员工的特点不同，不同的员工去完成同一项任务时所获得的回报不同。如何分配工作方案可以使总回报最大？2021/7/214、中国邮递员问题Chinesepostmanproblem一名邮递员负责投递某个街区的邮件。如何为他（她）设计一条最短的投递路线（从邮局出发，经过投递区内每条街道至少

3、一次，最后返回邮局）？我国管梅谷教授1960年首先提出，国际上称之为中国邮递员问题。2021/7/215、旅行商问题Travelingsalesmanproblem一名推销员准备前往若干城市推销产品。如何为他设计一条最短的旅行路线？（从驻地出发，经过每个城市恰好一次，最后返回驻地）2021/7/216、运输问题Transportationproblem某种原材料有M个产地，现在需要将原材料从产地运往N个使用这些原材料的工厂。假定M个产地的产量和N家工厂的需要量已知，单位产品从任一产地到任一工厂的运费已知，那么如何安排运输方案可以使

4、总运输成本最低？2021/7/21问题的两个共同特点（1）目的都是从若干可能的安排或方案中寻求某种意义下的最优安排或方案，数学问题称为最优化或优化问题。（2）它们都可用图形形式直观描述，数学上把这种与图相关的结构称为网络。图和网络相关的最优化问题就是网络最优化。网络优化问题是以网络流为研究的对象，常常被称为网络流或网络流规划等。2021/7/21一、图论的基本概念1.图与子图e1e2e3e5e6e4e7v3v2v1v4e2e3e5e6e4v3v2v1v4G1：如G：简单图：无自环、无重边的图。2021/7/21

5、V

6、=n表示图G中

7、节点个数为n，此节点个数n也称为图G的阶

8、E

9、=m表示图G中边的个数为m任一顶点相关联的边的数目称为该顶点的度完全图：任意两点有边相连，用表示完全图的边，和每点的度是多少？2021/7/212.关联与相邻2021/7/212021/7/213.链与圈2021/7/214.有向图与无向图，圈，回路比较：2021/7/21v1v2v3v5v48342172021/7/212021/7/215.树例1已知有5个城市，要在它们之间架设电话线网，要求任2城市都可通话（允许通过其它城市），并且电话线的根数最少。v1v2v3v5v4特点：连通、

10、无圈。树——无圈的连通图，记为T。2021/7/21v1v2v3v5v4树的性质：（1）树的任2点间有且仅有1链；（2）在树中任去掉1边，则不连通；（3）在树中不相邻2点间添1边，恰成1圈；（4）若树T有n个顶点，则T有n-1条边。2021/7/216.图的支撑树若图G=（V，E）的子图T=（V，E’）是树，则称T为G的支撑树。特点——边少、点不少。性质：G连通，则G必有支撑树。证：破圈、保连通。2021/7/21二、网络分析网络——赋权图，记D=（V，E，C），其中C={c1，…，cn}，ci为边ei上的权（设ci）。网络分析主

11、要内容:最小支撑树最短路最大流。2021/7/21一.最小支撑树问题问题：求网络D的支撑树，使其权和最小。方法：避圈法（Kruskal,1956）、破圈法(管梅谷，1975)。例2求如图网络的最小支撑树。v5v1v3v6v4v2v7255233575711Kruskal,J.B.(1956).OntheShortestSpanningSubtreeofaGraphandtheTravelingSalesmanProblem.ProceedingsoftheAmericanMathematicalSociety7,48-50.202

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