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

《数模(网络图论模型)ppt课件.ppt》由会员分享，可在线阅读，更多相关《数模(网络图论模型)ppt课件.ppt（112页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学建模电子教案数学建模电子教案v重庆邮电大学重庆邮电大学v 数理学院数理学院v 沈世云沈世云第三章第三章 网络图论模型网络图论模型1最短路最短路(最短路径最短路径)问题问题二二. 行行 遍遍 性性 问问 题题v图论（图论（Graph Theory）是运筹学的一个重要分）是运筹学的一个重要分支，它是建立和处理离散类数学模型的一个重要支，它是建立和处理离散类数学模型的一个重要工具。用图论的方法往往能帮助人们解决一些用工具。用图论的方法往往能帮助人们解决一些用其它方法难于解决的问题。其它方法难于解决的问题。v图论的发展可以追溯到图论的发展可以追溯到1736年欧拉所发表的一篇年欧拉所发表的一篇关于解

2、决关于解决 “哥尼斯堡七桥问题哥尼斯堡七桥问题”的著名论文。的著名论文。v到目前为止，图论的模型和方法已被广泛地应用到目前为止，图论的模型和方法已被广泛地应用于系统工程，通讯工程，计算机科学及经济学领于系统工程，通讯工程，计算机科学及经济学领域，传统的物理、化学、生命科学也都越来越广域，传统的物理、化学、生命科学也都越来越广泛地使用了图论模型方法。由于这种数学模型和泛地使用了图论模型方法。由于这种数学模型和方法直观形象，富有启发性和趣味性，因而深受方法直观形象，富有启发性和趣味性，因而深受人们的青睐。人们的青睐。从七桥问题说起从七桥问题说起 -关于图模型关于图模型v哥尼斯堡七桥问题哥尼斯堡七桥

3、问题 v七桥问题是发生在七桥问题是发生在18世纪东普鲁土的哥尼斯堡的一个真实世纪东普鲁土的哥尼斯堡的一个真实故事。故事。v在哥尼斯堡有条普莱格尔河在哥尼斯堡有条普莱格尔河,它有两条支流在城市中心汇它有两条支流在城市中心汇合后流入波罗的海。这条河将城市分割成四块合后流入波罗的海。这条河将城市分割成四块:A、C两个两个小岛和小岛和B、D两块陆地（如图）。为通行方便，在四块陆两块陆地（如图）。为通行方便，在四块陆地之间建了七座桥，每到节、假日或傍晚，都有许多居民地之间建了七座桥，每到节、假日或傍晚，都有许多居民和大学生来此散步。久而久之和大学生来此散步。久而久之,人们发现并热衷于讨论这人们发现并热衷

4、于讨论这样一个问题样一个问题:能否从四块陆地之一出发能否从四块陆地之一出发,走遍每座桥一次且走遍每座桥一次且仅一次然后回到出发地仅一次然后回到出发地?自然有不少人作过实地尝试自然有不少人作过实地尝试,但一但一直未能实现。直未能实现。问题的提出问题的提出 v1735年年,有大学生写信把问题告诉了欧拉有大学生写信把问题告诉了欧拉,请他帮请他帮助解决。欧拉从大家的失败中进行抽象的数学思助解决。欧拉从大家的失败中进行抽象的数学思考考,从数学角度成功地解决了问题。从数学角度成功地解决了问题。 问题分析与模型假设：问题分析与模型假设： 1. 问题的本质是能否从一地无重复地一次走遍七桥,因而与所走过的桥的大

5、小、形状、长短、曲直等均无关，而只要桥存在，因此不妨将其视为一条弧线； 2. 四块陆地可重复经历,至于陆地的大小、形状、质地等也与问题的本质无关，因而可视四块陆地为四个点 A、B、C、D。 对四个陆地对四个陆地 A A、B B、C C、D D，若其间有桥，则用一条弧，若其间有桥，则用一条弧线连接起来，有两座桥，则连两条不重合的弧线，便得到线连接起来，有两座桥，则连两条不重合的弧线，便得到一个图，并称代表陆地的四个点为顶点一个图，并称代表陆地的四个点为顶点 ，代表桥的弧线，代表桥的弧线为为 边边 。这样一来，能否从一地出发走遍七座桥一次且仅。这样一来，能否从一地出发走遍七座桥一次且仅一次再回到出

6、发点就变成了：能否从这个图上任一顶点出一次再回到出发点就变成了：能否从这个图上任一顶点出发，经过每条边一次且仅一次而回到出发顶点。这就是众发，经过每条边一次且仅一次而回到出发顶点。这就是众所周知的这个图能否所周知的这个图能否“一笔画出一笔画出”的问题。的问题。 1 最短路最短路(最短路径最短路径)问题问题1、图、图 论论 的的 基基 本本 概概 念念2、最、最 短短 路路 问问 题题 及及 其其 算算 法法3、最、最 短短 路路 的的 应应 用用图图 论论 的的 基基 本本 概概 念念一、一、 图图 的的 概概 念念1、图的定义、图的定义2、顶点的次数、顶点的次数 3、子图、子图二、二、 图图

7、 的的 矩矩 阵阵 表表 示示1、 关联矩阵关联矩阵2、 邻接矩阵邻接矩阵返回返回定义定义有序三元组G=(V,E, )称为一个图图.图的定义图的定义定义定义定义定义返回返回顶点的次数顶点的次数4)(4vd5)(3)(2)(444vdvdvd定理定理)(2)()(GvdGVv例例 在一次聚会中，认识奇数个人的在一次聚会中，认识奇数个人的 人数一定是偶数人数一定是偶数。返回返回子图子图 GGv1,v4,v5Ge1,e2,e3关联矩阵关联矩阵M=43215432110110011000101110001vvvveeeee注：假设图为简单图邻接矩阵邻接矩阵对无向图，其邻接矩阵)(ijaA，其中：不相邻

8、与若相邻与若jijiijvvvva01注：假设图为简单图A=432143210111101011011010vvvvvvvv对有向图（，） ，其邻接矩阵)(ijaA，其中：EvvEvvajijiij），若（），若（01A=4321432105375083802720vvvvvvvv最最 短短 路路 问问 题题 及及 其其 算算 法法一、一、 基基 本本 概概 念念二、固 定 起 点 的 最 短 路三、每 对 顶 点 之 间 的 最 短 路路基 本 概 念),(),(min),(),(),(),(),(),(000000vuuvdSvSuSvdvuuvdvvdSvdvvdccc2),(),(),

9、(min),(:,2001110732110101 vvdvuuvdSvSuSvdvvvSvvSSvccc再求，设加入把3),(),(),(),(),(min),(,303220022207432210212 vvdvvvvdvuuvdSvSuSvdvvvSvvvSSvccc求，设加入把ciiiSvvuuvdSuSvvvdvl1010),(),(min),()(;)(,0)(100vlvvVvvl时，当）设（ 000, 0,vaivSiciSv).,()(),(),(min)(vuulvlEvuSuvli（2）对任意的）对任意的， ).(min3vlSvci）计算（，使中取出）在（vSci4.

10、),(min)(1vavlSvvlici .511iiiaSS）（算法步骤：算法步骤：（）赋初值：令 Su0, l u()0=0 vSVS,令l v( )=W u v(, )0,z v( )=u0 uu0（3） 设v*是使l v( )取最小值的S中的顶点，则令 S=Sv*， uv*（4） 若S ，转 2，否则，停止. 用上述算法求出的l v( )就是u0到v的最短路的权，从v的父亲标记)(vz追溯到u0, 就得到u0到v的最短路的路线.（2）更新l v( )、z v( )： vSVS,若l v( )l uW u v( )( , ) 则令l v( )=l uW u v( )( , ),z v(

11、)= u)(iul迭代次数1u2u3u 4u5u6u 7u 8u2345678 0 2 8 10 8 3 10 8 6 10 12 7 1012 9 12 12最后标记:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5u)(iul1u2u3u 4u5u6u 7u 8u最后标记:)(vl)(vz 0 2 1 7 3 6 9 12 1u 1u 1u 6u 2u 5u 4u 5uu1u2u3u4u5u6u7u8返回返回每 对 顶 点 之 间 的 最 短 路1、求距离矩阵的方法、求距离矩阵的方法2、求路径矩阵的方法、求路径矩阵的方法3、查找最短路路径的方

12、法、查找最短路路径的方法（一）算法的基本思想（一）算法的基本思想（三）算法步骤（三）算法步骤算法的基本思想算法原理算法原理 求距离矩阵的方法求距离矩阵的方法把带权邻接矩阵 W 作为距离矩阵的初值，即 D(0)=)()0(ijd=W（）D(1)= )() 1 (ijd，其中)0(1)0() 1 (,miniijijddd)0(1jd)1(ijd是从 vi到 vj的只允许以 v1作为中间点的路径中最短路的长度（2）D(2)= )()2(ijd，其中) 1 (2) 1 ()2(,miniijijddd)1 (2 jd )2(ijd是从 vi到 vj的只允许以 v1 、 v2作为中间点的路径中最短路的

13、长度（）D()=)()(ijd，其中)1()1()(,miniijijddd)1( jd)(ijd是从 vi到 vj的只允许以 v1、v2、v作为中间点的路径中最短路的长度即是从 vi到 vj中间可插入任何顶点的路径中最短路的长，因此D()即是距离矩阵返回返回算法原理算法原理 求路径矩阵的方法求路径矩阵的方法R=)(ijr, rij的含义是从 vi到 vj的最短路要经过点号为 rij的点)()0()0(ijrR, jrij)0(每求得一个 D(k)时，按下列方式产生相应的新的 R(k)否则若)1()1()1()1()(kkjkikkijkijkijdddrkr在建立距离矩阵的同时可建立路径矩阵

14、R 即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径)(D)(R)(R返回返回ij算法原理算法原理 查找最短路路径的方法查找最短路路径的方法若1)(prij，则点 p1是点 i 到点 j 的最短路的中间点.然后用同样的方法再分头查找若：（） 向点 i 追朔得：2)(1prip,3)(2prip,kipprk)(（） 向点 j 追朔得：1)(1qrjp,2)(1qrjq,jrjqm)(pkp2p1p3q1q2qm则由点i到j的最短路的路径为：jqqqpppimk,21, 12返回返回算法步骤算法步骤Floyd 算法：算法：求任意两点

15、间的最短路D(i,j)：i 到 j 的距离R(i,j)：i 到 j 之间的插入点输入: 带权邻接矩阵 w(i,j)（） 赋初值：对所有 i,j, d(i,j)w(i,j), r(i,j)j, k1(2) 更新 d(i,j), r(i,j)对所有 i,j，若 d(i,k)+d(k,j)d(i,j)，则 d(i,j)d(i,k)+d(k,j), r(i,j)k(3) 若 k=，停止否则 kk+1，转（） 例例 求下图中加权图的任意两点间的距离与路径 TO MATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD

16、951d，故从 v5到 v1的最短路为51r由 v4向 v5追朔：3, 35354rr;由 v4向 v1追朔：141r所以从 v5到 v1的最短路径为：1435.返回返回最最 短短 路路 的的 应应 用用一、一、 可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题二、二、 选选 址址 问问 题题1、 中心问题中心问题2、 重心问题重心问题返回返回可化为最短路问题的多阶段决策问题可化为最短路问题的多阶段决策问题 例例 1 设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的.若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用.

17、现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少. 已知该种设备在每年年初的价格为：第一年第二年第三年第四年第五年1111121213 使用不同时间设备所需维修费为：使用年限0112233445维修费5681118构造加权有向图 G1(V,E)（1）顶点集 VXib , i=1,2,3,4,5Xirk( ), i=2,3,4,5,6; k=1,2,i-1,每个顶点代表年初的一种决策，其中顶点Xib代表第 i 年初购置新设备的决策，顶点Xirk( )代表第 i 年初修理用过 k 年的旧设备的决策（2）弧集 E=(,),(,),(),XXXXibibirkib11i=1,2,3,4;

18、 k=1,2,i-1 (,),( )XXibir11, i=1,2,3,4,5(,)(),()XXirkirk11,i=1,2,3,4,5;k=1,2,i-1若第 i 年初作了决策Xi后，第 i+1 年初可以作决策Xi1，则顶点Xi与Xi1之间有弧(Xi,Xi1)，其权 W(Xi,Xi1)代表第 i 年初到第 i+1 年初之间的费 用.例如，弧(,)( )XXbr341代表第 3 年初买新设 备，第四 年初决定用第三 年买的用 过一年的 旧设备， 其权则为 第三年初 的购置费 与三、四年间 的维修费 之和，为 12517（3）问题转化为顶点Xb1到Xrk6( )的最短路问题.五年的最优购置费为

19、 kbrkd XX1 2 3 4 516, , , ,( )min (,)其中 d(Xb1,Xrk6( )为顶点Xb1到Xrk6( )的最短路的权.求 得 最 短 路 的 权 为 53， 而 两 条 最 短 路 分 别 为 XXXXXXbrrbrr1213245162( )()( )();XXXXXXbrbrrr1213415263( )( )()()因 此 ， 计 划 为 第 一 、 三 年 初 购 置 新 设 备 ， 或 第 一 、 四 年 初 购 置 新 设 备 ，五 年 费 用 均 最 省 ， 为 53.也可构造加权有向图 G2(V,E).（1）顶点集 V=V V V V V V123

20、456,，Vi表第 i 年初购置新设备的决策，V6表第五年底.（2）弧集 E=(,)V Vij，i=1,2,3,4,5; ij6,弧(,)V Vij表第 i 年初购进一台设备一直使用到第 j 年初的决策，其权 W(,)V Vij表由这一决策在第 i 年初到第 j 年初的总费用，如W(,)V V14=11+5+6+8=30.（3）问题转化为求V1到V6的最短路问题，求得两条最短路为VVV146，VVV136，权为 53，与图 G1(V,E)的解相同返回返回（2） 计算在各点iv设立服务设施的最大服务距离)(ivS max)(1ijjidvS , 2 , 1i 选址问题选址问题-中心问题中心问题例

21、例 2某城市要建立一个消防站，为该市所属的七个区服务，如图所示问应设在那个区，才能使它至最远区的路径最短（1）用 Floyd 算法求出距离矩阵 D=)(ijd（3）求出顶点kv，使)(min)(1iikvSvS则kv就是要求的建立消防站的地点此点称为图的中心点中心点 TO MATLAB(road3(floyd)05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .42502545 .24720375 .5710530DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7,

22、 S(v7)=8.5S(v3)=6,故应将消防站设在v3处。 返回返回 选址问题选址问题-重心问题重心问题例例 3某矿区有七个矿点，如图所示已知各矿点每天的产矿量)(jvq（标在图的各顶点上） 现要从这七个矿点选一个来建造矿厂 问应选在哪个矿点，才能使各矿点所产的矿运到选矿厂所在地的总运力（千吨公里）最小（1）求距离阵 D=)(ijd（2） 计算各顶点作为选矿厂的总运力)(ivm ijjjidvqvm)()(1 , 2 , 1i（3） 求kv使)(min)(1iikvmvm，则kv就是选矿厂应设之矿点此点称为图 G 的重心重心或中位点中位点返回返回三 树图与最小生成树v一般研究无向图一般研究无

23、向图v树图：倒置的树，根树图：倒置的树，根(root)在上，树叶在上，树叶(leaf)在下在下v多级辐射制的电信网络、管理的指标体系、家多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图谱、分类学、组织结构等都是典型的树图C1C2C3C4根根叶叶 1 1、树的定义及其性质树的定义及其性质 已知有六个城市，它们之间已知有六个城市，它们之间 要架设电话线，要求任意要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。两个城市均可以互相通话，并且电话线的总长度最短。 v1v2v3v4v5v6 1) 1)、一个连通的无圈的无向图叫做树。、一个连通的无圈的无向图

24、叫做树。 树中次为树中次为1 1的点称为树叶，次大于的点称为树叶，次大于1 1的点称为分支点。的点称为分支点。 树树 的性质：的性质： （1 1）数必连通，但无回路（圈）。数必连通，但无回路（圈）。 （2 2）n 个顶点的树必有个顶点的树必有n-1 条边条边。 （3 3）树树 中任意两个顶点之间，恰有且仅有一条链（初中任意两个顶点之间，恰有且仅有一条链（初等链）。等链）。 （4 4）树）树 连通，但去掉任一条边，连通，但去掉任一条边， 必变为不连通。必变为不连通。 （5 5） 树树 无回路（圈），但不相邻的两个点之间加一条无回路（圈），但不相邻的两个点之间加一条边，恰得到一个回路（圈）。边，恰

25、得到一个回路（圈）。v1v2v3v4v5v6 2) 2)、 设图设图 是图是图G=(V , E )的一支撑子图，的一支撑子图，如果图如果图 是一个树是一个树, ,那么称那么称K 是是G 的一个生成的一个生成树（支撑树），或简称为图树（支撑树），或简称为图G 的树。图的树。图G中属于生成树的中属于生成树的边称为树枝，不在生成树中的边称为弦。边称为树枝，不在生成树中的边称为弦。),(1EVK 一个图一个图G 有生成树的充要条件是有生成树的充要条件是G 是连通图。是连通图。 v1v2v3v4v5v1v2v3v4v5),(1EVK 用破圈法求出下图的一个生成树。用破圈法求出下图的一个生成树。 v1v2

26、v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8（一）（一）破圈法破圈法（二）（二）避圈法避圈法 在图中任取一条边在图中任取一条边e1，找一条与，找一条与e1不构成圈的边不构成圈的边e2，再找一条与再找一条与e1，e2不构成圈的边不构成圈的边e3。一般设已有。一般设已有e1，e2，ek，找一条与，找一条与e1，e2，ek中任何一些边中任何一些边不构成圈的边不构成圈的边ek+1，重复这个过程，直到不能进行为，重复这个过程，直到不能进行为止。止。v1v2v3v4v5v6v1v3v1v3v2v1v3v2v5v6v1v

27、3v2v5v6v4v1v3v2v5v树树 T 是连通图是连通图 G 的生成树的生成树(spanning tree)，若，若 T 是是 G的子图且包含图的子图且包含图 G 的所有的节点；包含图的所有的节点；包含图 G 中部分指定中部分指定节点的树称为节点的树称为 steiner treev每个节点有唯一标号的图称为标记图，每个节点有唯一标号的图称为标记图，标记图的生成树称为标记树标记图的生成树称为标记树(labeled tree)Caylay 定理：定理：n ( 2)个节点，有个节点，有nn 2个个不同的不同的标记树标记树2. 图的生成树 2 . 图的生成树v如何找到一棵生成树如何找到一棵生成树

28、深探法深探法(depth first search)：任选一点标记为：任选一点标记为 0 点开点开始搜索，选一条未标记的边走到下一点，该点标记为始搜索，选一条未标记的边走到下一点，该点标记为 1，将走过的边标记；假设已标记到，将走过的边标记；假设已标记到 i 点，总是从最点，总是从最新标记的点向下搜索，若从新标记的点向下搜索，若从 i 点无法向下标记，即与点无法向下标记，即与 i 点相关联的边都已标记或相邻节点都已标记，则退点相关联的边都已标记或相邻节点都已标记，则退回到回到 i 1 点继续搜索，直到所有点都被标记点继续搜索，直到所有点都被标记广探法广探法(breadth first sear

29、ch)：是一种有层级结构的：是一种有层级结构的搜索，一般得到的是树形图搜索，一般得到的是树形图ACDBACDBACDBADCB 3. 最小生成树v有有n 个乡村，各村间道路的长度是已知的，个乡村，各村间道路的长度是已知的，如何敷设光缆线路使如何敷设光缆线路使 n 个乡村连通且总长个乡村连通且总长度最短度最短v显然，这要求在已知边长度的网路图中找显然，这要求在已知边长度的网路图中找最小生成树最小生成树 最小生成树的算法最小生成树的算法：vKruskal 算法：算法：将图中所有边按权值从小将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集到大排列，依次选所剩最小的边加入边集 T，只要不和前

30、面加入的边构成回路，直，只要不和前面加入的边构成回路，直到到 T 中有中有 n 1 条边，则条边，则 T 是最小生成树是最小生成树 3. 最小生成树最小生成树vKruskal 算法基于下述定理算法基于下述定理定理 3 指定图中任一点指定图中任一点vi，如果，如果 vj 是距是距 vi 最近的相邻节点，则关联边最近的相邻节点，则关联边 eij 必在某个最必在某个最小生成树中。小生成树中。推论推论 将网路中的节点划分为两个不相交的将网路中的节点划分为两个不相交的集合集合V1和和V2，V2=V V1，则，则V1和和V2间权值间权值最小的边必定在某个最小生成树中。最小的边必定在某个最小生成树中。 3.

31、 最小生成树v最小生成树不一定唯一最小生成树不一定唯一v定理定理 3 推论是一个构造性定理，它指示了推论是一个构造性定理，它指示了找最小生成树的有效算法找最小生成树的有效算法vPrim 算法：不需要对边权排序，即可以直算法：不需要对边权排序，即可以直接在网路图上操作，也可以在边权矩阵上接在网路图上操作，也可以在边权矩阵上操作，后者适合计算机运算操作，后者适合计算机运算 3. 最小生成树v边权矩阵上的边权矩阵上的 Prim 算法算法：1、根据网路写出边权矩阵，两点间若没有边，则用、根据网路写出边权矩阵，两点间若没有边，则用 表示；表示；2、从、从 v1 开始标记，在第一行打开始标记，在第一行打

32、，划去第一列；，划去第一列；3、从所有打、从所有打 的行中找出尚未划掉的最小元素，对的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应该元素画圈，划掉该元素所在列，与该列数对应的行打的行打 ；4、若所有列都划掉，则已找到最小生成树、若所有列都划掉，则已找到最小生成树(所有画所有画圈元素所对应的边圈元素所对应的边)；否则，返回第；否则，返回第 3 步。步。v该算法中，打该算法中，打 行对应的节点在行对应的节点在 V1中，未划去的中，未划去的列在列在 V2中中 3. 最小生成树 97125 .19179810787111275 . 9165 .195 . 910171011

33、1610vPrim算法是多项式算法vPrim算法可以求最大生成树v网路的边权可以有多种解释，如效率v次数受限的最小生成树尚无有效算法v最小 Steiner 树尚无有效算法v1v4v6v3v5v2101081177169.51712919.5 v1v4v6v3v5v2108779.5行行 遍遍 性性 问问 题题行行 遍遍 性性 问问 题题一、中一、中 国国 邮邮 递递 员员 问问 题题二、推二、推 销销 员员 问问 题题三、建模案例：最佳灾情巡视路线三、建模案例：最佳灾情巡视路线（一）（一） 欧欧 拉拉 图图（二）（二） 中中 国国 邮邮 递递 员员 问问 题题（一）（一） 哈哈 密密 尔尔 顿

34、顿 图图（二）（二） 推推 销销 员员 问问 题题 定定义义 设图 G =（V，E） ，ME，若 M 的边互不相邻，则称 M 是 G 的一个匹匹配配.若顶点 v与 M 的一条边关联，则称 v是 M饱和的饱和的 设 M 是 G 的一个匹配，若 G 的每个顶点都是 M饱和的，则称 M 是 G 的理理想想匹匹配配.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割边G的边e是割边的充要条件是e不含在G的圈中 割边的定义割边的定义：设G连通，e E(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边e3v1v2v3v4e1e2e4e5e6欧欧 拉拉 图图e3v1v2v3v4

35、e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1定理定理对于非空连通图 G，下列命题等价：（）G 是欧拉图（）G 无奇次顶点（）G 的边集能划分为圈推推论论设 G 是非平凡连通图，则 G 有欧拉道路的充要条件是 G 最多只有两个奇次顶点e3v1v2v3v4e1e2e4e5e3v1v2v3v4e1e2e4e5e6欧拉图非欧拉图返回返回中国邮递员问题中国邮递员问题- -定义定义 若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投

36、递区构成一个赋权连通无向图中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为最最佳佳巡巡回回中国邮递员问题中国邮递员问题- -算法算法 1、G是欧拉图是欧拉图 Fleury算法算法-基本思想：从任一点出发，每当访问基本思想：从任一点出发，每当访问一条边时，先要进行检查如果可供访问的边不只一条边时，先要进行检查如果可供访问的边不只一条，则应选一条不是未访问的边集的导出子图的一条，则应选一条不是未访问的边集的导出子图的割边割边作为访问边，直到没有边可选择为止作为访问边，直到没有边可选择为止.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e102、G

37、不是欧拉图不是欧拉图 若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次 解决这类问题的一般方法是，在一些点对之间引入重复边（重复边与它平行的边具有相同的权），使原图成为欧拉图，但希望所有添加的重复边的权的总和为最小情形情形G正好有两个奇次顶点正好有两个奇次顶点（）用 Dijkstra 算法求出奇次顶点 u 与 v 之间的最短路径 P（）令 G*=GP，则 G*为欧拉图（）用 Fleury 算法求出 G*的欧拉巡回，这就是 G 的最佳巡回V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9Edmonds 最小对集算法：最小对集算法：基 本 思 想 ：算法步骤：算法步骤：（）求

38、出（）求出G1的的最小权理想匹配最小权理想匹配M，得到奇次顶点，得到奇次顶点的最佳配对的最佳配对例例求右图所示投递区的一条最佳邮递路线用 Floyd 算法求出它们之间的最短路径和距离：3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv2以 v4、v7、v8、v9为顶点，它们之间的距离为边权构造完备图 G13求出 G1的最小权完美匹配 M=(v4,v7),(v8,v9)4在 G 中沿 v4到 v7的最短路径添

39、加重复边，沿 v8到 v9的最短路径 v8v9添加重复边，得欧拉图 G2G2中一条欧拉巡回就是 G 的一条最佳巡回其权值为返回返回哈哈 密密 尔尔 顿顿 图图定定义义设 G=(V,E)是连通无向图（） 经过 G 的每个顶点正好一次的路径，称为 G 的一条 哈哈密密尔尔顿顿路路径径（） 经过 G 的每个顶点正好一次的圈，称为 G 的哈哈密密尔尔 顿顿圈圈或 H 圈（）含 H 圈的图称为哈哈密密尔尔顿顿图图或 H 图返回返回推销员问题推销员问题- -定义定义 流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题推销员问题 若用顶点表示城镇，边表示连接两城

40、镇的路，边上的权表示距离（或时间、费用），于是推销员问题就成为在加权图中寻找一条经过每个顶点至少一次的最短闭通路问题定义定义在加权图G=(V,E)中，（）权最小的哈密尔顿圈称为最佳最佳H圈圈（）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回路最佳推销员回路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长22最佳推销员回路，长4定定理理在加权图G=(V,E)中，若对任意x,y,zV，zx,zy,都有 w(x,y)w(x,z)+w(z,y)，则图 G 的最佳 H 圈也是最佳推销员回路最佳推销员回路问题可转化为最佳 H 圈问题方法是由给定的

41、图 G=(V,E)构造一个以 V 为顶点集的完备图 G=(V,E)，E的每条边(x,y)的权等于顶点 x 与 y 在图中最短路的权即：x,yE w(x,y)=mindG(x,y)定理定理加权图 G 的最佳推销员回路的权与 G的最佳 H 圈的权相同1. 已知邮递员要投递的街道如图所已知邮递员要投递的街道如图所示，试求最优邮路示，试求最优邮路解解 先找出奇节点：先找出奇节点：A1，A2，A3，A4，B1，B2，B3，B4奇节点进行配对，不妨把奇节点进行配对，不妨把A1与与B1，A2与与B2，A3与与B3，A4与与B4配对配对，求其最短路显然它不是最优解，求其最短路显然它不是最优解下面我们根据定理下

42、面我们根据定理3来进行调解来进行调解推销员问题近似算法：推销员问题近似算法：二边逐次修正法二边逐次修正法：（）任取初始 H 圈: C0=v1,v2,vi, ,vj,vn,v1（）对所有的 i ,j，1i+1jn,若w(vi, vj)+w(vi+1,vj+1)w(vi,vi+1)+w(vj,vj+1)则在 C0中删去边(vi,vi+1)和(vj,vj+1)而加入边(vi, vj)和(vi+1,vj+1)，形成新的 H 圈 C，即C= v1,v2,vi,vj , vj-1, ,vi+1,vj+1, ,vn,v1）对 C 重复步骤（） ，直到条件不满足为止，最后得到的C即为所求图论模型案例图论模型案

43、例:最佳灾情巡视路线最佳灾情巡视路线一、问一、问 题题 今年夏天某县遭受水灾今年夏天某县遭受水灾.为考察灾情、组织自救，县为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡（镇） 、村领导决定，带领有关部门负责人到全县各乡（镇） 、村巡视巡视.巡视路线指从县政府所在地出发， 走遍各乡 （镇） 、巡视路线指从县政府所在地出发， 走遍各乡 （镇） 、村，又回到县政府所在地的路线村，又回到县政府所在地的路线. 若分三组（路）巡视，试设计总路程最短且各组尽可若分三组（路）巡视，试设计总路程最短且各组尽可能均衡的路线能均衡的路线. 1 假定巡视人员在各乡（镇）停留时间假定巡视人员在各乡（镇）

44、停留时间 T=2 小时，在各小时，在各村停留时间村停留时间 t=1 小时， 汽车行驶速度小时， 汽车行驶速度 V=35 公里公里/小时小时.要在要在24 小时内完成巡视， 至少应分几组； 给出这种分组下小时内完成巡视， 至少应分几组； 给出这种分组下最佳最佳的巡视路线的巡视路线. 乡镇、村的公路网示意图见下图乡镇、村的公路网示意图见下图二、二、 假假 设设 1 汽车在路上的速度总是一定， 不会出现抛锚等现象； 汽车在路上的速度总是一定， 不会出现抛锚等现象； 2巡视当中，在每个乡镇、村的停留时间一定，不会巡视当中，在每个乡镇、村的停留时间一定，不会出现特殊情况而延误时间；出现特殊情况而延误时间

45、； 3每个小组的汽车行驶速度完全一样；每个小组的汽车行驶速度完全一样； 4分组后，各小组只能走自己区内的路，不能走其他分组后，各小组只能走自己区内的路，不能走其他小组的路，除公共路外小组的路，除公共路外. 三、模三、模 型型 的的 建建 立立 与与 求求 解解 将公路网图中，每个乡（镇）或村看作图中的一个节点，各将公路网图中，每个乡（镇）或村看作图中的一个节点，各乡（镇） 、村之间的公路看作图中对应乡（镇） 、村之间的公路看作图中对应节点间的边，各条公节点间的边，各条公路的长度（或行驶时间）看作对应边上的权，所给公路网就路的长度（或行驶时间）看作对应边上的权，所给公路网就转化为加权网络图， 问

46、题就转化为在给定的加权网络图中寻转化为加权网络图， 问题就转化为在给定的加权网络图中寻找从给定点找从给定点 O 出发，行遍所有顶点至少一次再回到出发，行遍所有顶点至少一次再回到 O 点，点，使得总权（路程或时间）最小，此即最佳推销员回路问题使得总权（路程或时间）最小，此即最佳推销员回路问题. 在加权图在加权图 G 中求最佳推销员回路问题是中求最佳推销员回路问题是 NP完全完全问题，我们采用一种近似算法求出该问题的一个近似问题，我们采用一种近似算法求出该问题的一个近似最优解，来代替最优解，算法如下：最优解，来代替最优解，算法如下： 算法一算法一 求加权图求加权图 G G（V V，E E）的最佳推

47、销员回路的近似算法：）的最佳推销员回路的近似算法： 1 用图论软件包求出用图论软件包求出 G 中任意两个顶点间的最短路， 构造中任意两个顶点间的最短路， 构造出完备图出完备图),(EVG，Eyx,， yxMindyxG,； 2 输入图输入图G的一个初始的一个初始 H 圈；圈； 3 用对角线完全算法产生一个初始用对角线完全算法产生一个初始 H 圈；圈； 4 随机搜索出随机搜索出G中若干个中若干个 H 圈，例如圈，例如 2000 个；个； 5 对第对第 2、3、4 步所得的每个步所得的每个 H 圈，用二边逐次修正法进圈，用二边逐次修正法进行优化行优化，得到近似最佳，得到近似最佳 H 圈；圈； 6

48、在第在第 5 步求出的所有步求出的所有 H 圈中， 找出权最小的一个， 此即圈中， 找出权最小的一个， 此即要找的最佳要找的最佳 H 圈的近似解圈的近似解. 由于二边逐次修正法的结果与初始圈有关，故本算法第由于二边逐次修正法的结果与初始圈有关，故本算法第 2、3、4 步分别用三种方法产生初始圈，以保证能得到较优的计步分别用三种方法产生初始圈，以保证能得到较优的计算结果算结果. 问题一 若分为三组巡视，设计总路程最短且各组尽可能均衡的巡视路线.此此问问题题是是多多个个推推销销员员的的最最佳佳推推销销员员回回路路问问题题.即即在在加加权权图图 G 中中求求顶顶点点集集 V 的的划划分分nVVV,.

49、,21，将将 G 分分成成 n个个生生成成子子图图 nVGVGVG,.,21，使使得得 （1）顶顶点点iVO i=1，2，3n （2）GVVnii1 （3）iijijiCMaxCCMax,， 其其中中iC为为iV的的导导出出子子图图 iVG中中的的最最佳佳推推销销员员回回路路，iC为为iC的的权权，i，j=1，2，3n （4）MinCnii1 定义定义 称称iijijiCMaxCCMax,0为该分组的实为该分组的实际均衡度际均衡度.为最大容许均衡度为最大容许均衡度. 显然显然100，0越小，说明分组的均衡性越好越小，说明分组的均衡性越好.取取定一个定一个后，后，0与与满足条件（满足条件（3）的

50、分组是一个均衡分）的分组是一个均衡分组组.条件（条件（4）表示总巡视路线最短）表示总巡视路线最短. 此问题包含两方面：第一、对顶点分组；第二、在每组中此问题包含两方面：第一、对顶点分组；第二、在每组中求最佳推销员回路，即为单个推销员的最佳推销员问题求最佳推销员回路，即为单个推销员的最佳推销员问题. 由于单个推销员的最佳推销员回路问题不存在多由于单个推销员的最佳推销员回路问题不存在多项式时间项式时间内的精确算法，故多个推销员的问题也不存在多项式时间内内的精确算法，故多个推销员的问题也不存在多项式时间内的精确算法的精确算法.而图中节点数较多，为而图中节点数较多，为 53 个，我们只能去寻求个，我们