数模(网络图论模型)课件

数学建模电子教案重庆邮电大学数理学院沈世云数学建模电子教案重庆邮电大学1第三章网络图论模型最短路(最短路径)问题二.行遍性问题第三章网络图论模型最短路(最短路径)问题二.行2图论（GraphTheory）是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要工具。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。图论的发展可以追溯到1736年欧拉所发表的一篇关于解决“哥尼斯堡七桥问题”的著名论文。到目前为止，图论的模型和方法已被广泛地应用于系统工程，通讯工程，计算机科学及经济学领域，传统的物理、化学、生命科学也都越来越广泛地使用了图论模型方法。由于这种数学模型和方法直观形象，富有启发性和趣味性，因而深受人们的青睐。图论（GraphTheory）是运筹学的一个重要分支，它3从七桥问题说起

---关于图模型哥尼斯堡七桥问题七桥问题是发生在18世纪东普鲁土的哥尼斯堡的一个真实故事。在哥尼斯堡有条普莱格尔河,它有两条支流在城市中心汇合后流入波罗的海。这条河将城市分割成四块:A、C两个小岛和B、D两块陆地（如图）。为通行方便，在四块陆地之间建了七座桥，每到节、假日或傍晚，都有许多居民和大学生来此散步。久而久之,人们发现并热衷于讨论这样一个问题:能否从四块陆地之一出发,走遍每座桥一次且仅一次然后回到出发地?自然有不少人作过实地尝试,但一直未能实现。问题的提出从七桥问题说起

---关于图模型哥尼斯堡七桥4

1735年,有大学生写信把问题告诉了欧拉,请他帮助解决。欧拉从大家的失败中进行抽象的数学思考,从数学角度成功地解决了问题。

1735年,有大学生写信把问题告诉了欧拉,请他帮助解决。欧5

问题分析与模型假设：

1.问题的本质是能否从一地无重复地一次走遍七桥,因而与所走过的桥的大小、形状、长短、曲直等均无关，而只要桥存在，因此不妨将其视为一条弧线；

2.四块陆地可重复经历,至于陆地的大小、形状、质地等也与问题的本质无关，因而可视四块陆地为四个点A、B、C、D。

问题分析与模型假设：6对四个陆地A、B、C、D，若其间有桥，则用一条弧线连接起来，有两座桥，则连两条不重合的弧线，便得到一个图，并称代表陆地的四个点为顶点，代表桥的弧线为边。这样一来，能否从一地出发走遍七座桥一次且仅一次再回到出发点就变成了：能否从这个图上任一顶点出发，经过每条边一次且仅一次而回到出发顶点。这就是众所周知的这个图能否“一笔画出”的问题。对四个陆地A、B、C、D，若其间有桥，则用一条7最短路(最短路径)问题1、图论的基本概念2、最短路问题及其算法3、最短路的应用最短路(最短路径)问题1、图论的基本概念2、最8图论的基本概念一、图的概念1、图的定义2、顶点的次数

3、子图二、图的矩阵表示1、关联矩阵2、邻接矩阵返回图论的基本概念一、图的概念1、图的定义29定义有序三元组G=(V,E,)称为一个图.图的定义定义有序三元组G=(V,E,)称为一个图.图的定10定义定义定义定义11数模(网络图论模型)ppt课件12返回返回13顶点的次数顶点的次数14例在一次聚会中，认识奇数个人的人数一定是偶数。返回例在一次聚会中，认识奇数个人的返回15子图子图16关联矩阵注：假设图为简单图关联矩阵注：假设图为简单图17邻接矩阵注：假设图为简单图邻接矩阵注：假设图为简单图18数模(网络图论模型)ppt课件19最短路问题及其算法一、基本概念二、固定起点的最短路三、每对顶点之间的最短路最短路问题及其算法一、基本概念二、固20基本概念基本概念21数模(网络图论模型)ppt课件22数模(网络图论模型)ppt课件23数模(网络图论模型)ppt课件24数模(网络图论模型)ppt课件25数模(网络图论模型)ppt课件26数模(网络图论模型)ppt课件27数模(网络图论模型)ppt课件28数模(网络图论模型)ppt课件29数模(网络图论模型)ppt课件30．．31（2）对任意的，

（2）对任意的，32数模(网络图论模型)ppt课件33数模(网络图论模型)ppt课件34数模(网络图论模型)ppt课件35算法步骤：算法步骤：36数模(网络图论模型)ppt课件37数模(网络图论模型)ppt课件38u1u2u3u4u5u6u7u8返回u1u2u3u4u5u6u7u8返回39每对顶点之间的最短路1、求距离矩阵的方法2、求路径矩阵的方法3、查找最短路路径的方法（一）算法的基本思想（三）算法步骤每对顶点之间的最短路1、求距离矩阵的方法240算法的基本思想算法的基本思想41算法原理——求距离矩阵的方法返回算法原理——求距离矩阵的方法返回42算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．返回算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径43ij算法原理——

查找最短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：返回ij算法原理——查找最短路路径的方法pkp2p1p3q144算法步骤算法步骤45TOMATLAB(road2(floyd))返回TOMATLAB返回46一、可化为最短路问题的多阶段决策问题二、选址问题1、中心问题2、重心问题返回一、可化为最短路问题的多阶段决策问题二、选址问题147可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题48数模(网络图论模型)ppt课件49数模(网络图论模型)ppt课件50返回返回51

选址问题--中心问题TOMATLAB(road3(floyd))选址问题--中心问题TOMATLAB52S(v1)=10,S(v2)=7,S(v3)=6,S(v4)=8.5,S(v5)=7,S(v6)=7,S(v7)=8.5S(v3)=6,故应将消防站设在v3处。返回S(v1)=10,S(v2)=7,S(v3)=6,S(53

选址问题--重心问题返回选址问题--重心问题返回54三树图与最小生成树一般研究无向图树图：倒置的树，根(root)在上，树叶(leaf)在下多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图三树图与最小生成树一般研究无向图55

1、树的定义及其性质

已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。v1v2v3v4v5v61)、一个连通的无圈的无向图叫做树。树中次为1的点称为树叶，次大于1的点称为分支点。1、树的定义及其性质v1v2v3v4v5v61)、56树

的性质：（1）数必连通，但无回路（圈）。（2）n个顶点的树必有n-1条边。（3）树中任意两个顶点之间，恰有且仅有一条链（初等链）。（4）树

连通，但去掉任一条边，必变为不连通。（5）树无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。v1v2v3v4v5v6树的性质：v1v2v3v4v5v6572)、设图是图G=(V,E)的一支撑子图，如果图是一个树,那么称K是G的一个生成树（支撑树），或简称为图G的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。一个图G有生成树的充要条件是G

是连通图。v1v2v3v4v5v1v2v3v4v52)、设图是图G=(V,E58用破圈法求出下图的一个生成树。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8用破圈法求出下图的一个生成树。v1v2v3v4v5e1e259（一）破圈法（一）破圈法60（二）避圈法

在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与{e1，e2}不构成圈的边e3。一般设已有{e1，e2，…，ek}，找一条与{e1，e2，…，ek}中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。（二）避圈法在图中任取一条边e1，找一条与e161v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v3v2v5v6v4v1v3v2v5v1v2v3v4v5v6v1v3v1v3v2v1v3v2v562树T是连通图G的生成树(spanningtree)，若T是G的子图且包含图G的所有的节点；包含图G中部分指定节点的树称为steinertree每个节点有唯一标号的图称为标记图，标记图的生成树称为标记树(labeledtree)Caylay定理：n(2)个节点，有nn2个不同的标记树2.图的生成树2.图的生成树632.图的生成树如何找到一棵生成树深探法(depthfirstsearch)：任选一点标记为0点开始搜索，选一条未标记的边走到下一点，该点标记为1，将走过的边标记；假设已标记到i点，总是从最新标记的点向下搜索，若从i点无法向下标记，即与i点相关联的边都已标记或相邻节点都已标记，则退回到

i

1点继续搜索，直到所有点都被标记广探法(breadthfirstsearch)：是一种有层级结构的搜索，一般得到的是树形图2.图的生成树如何找到一棵生成树643.最小生成树有n个乡村，各村间道路的长度是已知的，如何敷设光缆线路使n个乡村连通且总长度最短显然，这要求在已知边长度的网路图中找最小生成树

最小生成树的算法：Kruskal算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集T，只要不和前面加入的边构成回路，直到T中有n1条边，则T是最小生成树3.最小生成树有n个乡村，各村间道路的长度65

3.最小生成树Kruskal

算法基于下述定理定理3指定图中任一点vi，如果vj是距vi最近的相邻节点，则关联边eij必在某个最小生成树中。推论

将网路中的节点划分为两个不相交的集合V1和V2，V2=VV1，则V1和V2间权值最小的边必定在某个最小生成树中。3.最小生成树66数模(网络图论模型)ppt课件67数模(网络图论模型)ppt课件68数模(网络图论模型)ppt课件69

3.最小生成树最小生成树不一定唯一定理3推论是一个构造性定理，它指示了找最小生成树的有效算法Prim算法：不需要对边权排序，即可以直接在网路图上操作，也可以在边权矩阵上操作，后者适合计算机运算

3.最小生成树最小生成树不一定唯一70数模(网络图论模型)ppt课件71

3.最小生成树边权矩阵上的Prim算法：1、根据网路写出边权矩阵，两点间若没有边，则用表示；2、从v1开始标记，在第一行打，划去第一列；3、从所有打的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打；4、若所有列都划掉，则已找到最小生成树(所有画圈元素所对应的边)；否则，返回第3步。该算法中，打行对应的节点在V1中，未划去的列在V2中3.最小生成树边权矩阵上的Prim算法：723.最小生成树Prim算法是多项式算法Prim算法可以求最大生成树网路的边权可以有多种解释，如效率次数受限的最小生成树—尚无有效算法最小Steiner树—尚无有效算法3.最小生成树Prim算法是多项式算法73行遍性问题

行遍性问题

74行遍性问题一、中国邮递员问题二、推销员问题三、建模案例：最佳灾情巡视路线（一）欧拉图（二）中国邮递员问题（一）哈密尔顿图（二）推销员问题行遍性问题一、中国邮递员问题二、推销75数模(网络图论模型)ppt课件76V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割边G的边e是割边的充要条件是e不含在G的圈中．

割边的定义：设G连通，eE(G),若从G中删除边e后，图G-{e}不连通，则称边e为图G的割边．V7e3v1v2v3v4e1e2e4e5V5V6e6e7e877e3v1v2v3v4e1e2e4e5e6欧拉图e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1e3v1v2v3v4e1e2e4e5e6欧拉图e3v1v78e3v1v2v3v4e1e2e4e5e3v1v2v3v4e1e2e4e5e6欧拉图非欧拉图返回e3v1v2v3v4e1e2e4e5e3v1v2v3v4e179中国邮递员问题-定义中国邮递员问题-定义80中国邮递员问题-算法

Fleury算法-基本思想：从任一点出发，每当访问一条边时，先要进行检查．如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的割边作为访问边，直到没有边可选择为止.中国邮递员问题-算法Fleury算法-基本思想：从81V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10V7e3v1v2v3v4e1e2e4e5V5V6e6e7e882

若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次．

解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小．若G不是欧拉图，则G的任何一个巡回经过某些边必83V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9V7e3v1v2v3v4e1e2e4e5V5V6e6e7e884数模(网络图论模型)ppt课件85（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．（３）求出G1的最小权理想匹配M，得到奇次顶点86返回返回87哈密尔顿图返回哈密尔顿图返回88推销员问题-定义流动推销员需要访问某地区的所有城镇，最后回到出发点．问如何安排旅行路线使总行程最小．这就是推销员问题．若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题．推销员问题-定义流动推销员需要访问某地区的所有城89定义在加权图G=(V,E)中，（１）权最小的哈密尔顿圈称为最佳H圈．（