建模课件图论模型贵

1、数学模型 图论模型 朱和贵朱和贵 1. 图论的基本概念2. 最短路问题及算法 图论模型 3. 最小生成树及算法 4.网络流问题及算法 5. 行遍性问题及算法18 最短路径问题是图论中十分重要的最优最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优设备更新等等。也可以用于解决其它的最优化问题。化问题。2. 最短路问题及算法 19 例例 如下图所示

2、的单行线交通网，每个弧旁边的数字如下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从表示这条单行线的长度。现在有一个人要从V1出发，经出发，经过这个交通网到达过这个交通网到达V6 6， 要寻求总路程最短的要寻求总路程最短的 线路。线路。 v6v5v3v1v4v2365112436 从从v v1 1到到v v6 6的路线是很多的。比如从的路线是很多的。比如从V V1 1出发，经过出发，经过V V2 2 ,V,V4 4到达到达V V6 6或者从或者从V V1 1出发，经过出发，经过V V2 2，V V3 3，V V5 5到达到达V V6 6等等。但不同等等。但不同的路线

3、，经过的总长度是不同的。例如，按照第一个线路，的路线，经过的总长度是不同的。例如，按照第一个线路，总长度是总长度是3+6+3=123+6+3=12单位，按照第二个路线，总长度是单位，按照第二个路线，总长度是3+1+1+6=113+1+1+6=11单位。单位。20 求非负赋权图求非负赋权图G中某一点到其它各点最中某一点到其它各点最短路，一般用短路，一般用Dijkstra( (迪克斯特拉迪克斯特拉) )标号算标号算法；求非负赋权图上任意两点间的最短路，法；求非负赋权图上任意两点间的最短路，一般用一般用Floyd(弗洛伊德弗洛伊德) )算法。这两种算法均算法。这两种算法均适用于有向非负赋权图（适用于

4、有向非负赋权图（Floyd算法算法也适应也适应于负赋权图）。于负赋权图）。 21原则：原则： 如果如果P是是D中从中从vs到到vj的最短路，的最短路，vi是是P中中的一个点，那么，从的一个点，那么，从vs沿沿P到到vi的路是从的路是从vs到到vi的最短路。的最短路。24例例6求求v1到到v6的最短路的最短路（1）首先给）首先给v1以以P标号：标号： 标号以标号以（ ）形式标在结点旁边形式标在结点旁边 0 0：表示从表示从V V1 1到该点的最短距离到该点的最短距离 V1V1：表示从表示从V V1 1到该点的最短路中上一个顶点。到该点的最短路中上一个顶点。v6v5v3v1v4v236511243

5、625（2）S：V1S：V2，V3，V4，V5，V6求出（求出（S S）所有）所有弧，分别计算：弧，分别计算：S12=0+3=3,S13=0+5=5,MinSij=S12给给V2标号（标号（3，V1）v6v5v3v1v4v236511243626（3）S：V1，V2S：V3，V4，V5，V6求出（求出（S S）所有）所有弧，分别计算：弧，分别计算：S13=0+5=5S23=3+1=4S14=S24=3+6=9MinSij=S23给给V3标号（标号（4，V2）v6v5v3v1v4v236511243627（4）S：V1，V2，V3S：V4，V5，V6求出（求出（S S）所有）所有弧，分别计算：弧

6、，分别计算：S14=S24=3+6=9S34=4+4=8S15=S25=S35=4+1=5MinSij=S35给给V5标号（标号（5，V3）v6v5v3v1v4v236511243628v6v5v3v1v4v2365112436（5）S：V1，V2，V3，V5S：V4，V6求出（求出（S S）所有）所有弧，分别计算：弧，分别计算：S14=S24=3+6=9S34=4+4=8S54=5+2=7S56=5+6=11MinSij=S54给给V4标号（标号（7，V5）29（6）S：V1，V2，V3，V4，V5S：V6求出（求出（S S）所有）所有弧，分别计算：弧，分别计算：S46=7+3=10S56=

7、5+6=11MinSij=S46给给V6标号（标号（10，V4）12354v6v5v3v1v4v236511243630(7) (7) 标出最短路标出最短路 最短路径是：最短路径是： V1V2V3V5V4V6 路长路长1010。同时得到起点到其余各点的最短路。同时得到起点到其余各点的最短路。（3 3）（4 4）v6v5v3v1v4v2365112436（5 5）（7 7）31求天然气管道最优路径求天然气管道最优路径 筹建中的天然气管道网设计如图所示：筹建中的天然气管道网设计如图所示： 解为：解为： LJGEDA 表示压缩机站，流动主向用箭表示压缩机站，流动主向用箭头表示，每个管道旁的数字表示管

8、段长度，现需要头表示，每个管道旁的数字表示管段长度，现需要求该网络从起点求该网络从起点A A到终点到终点L L的最短通道，并确定沿最的最短通道，并确定沿最优路径相应的压缩机站所处的节点。优路径相应的压缩机站所处的节点。 LCBA、A AC CF FI IK KL LJ JE EB BD DH HG G3 33 35 52 21 12 23 34 44 44 43 33 34 46 64 43 31 15 55 52 2 例例: :每对顶点间的最短路算法每对顶点间的最短路算法 寻求赋权图中各对顶点之间最短路，显然可以调用 Dijkstra 算法。具体方法是：每次以不同的顶点作为起点，用 Dijk

9、stra 算法求出从该起点到其余顶点的最短路径，反复执行次这样的操作，就可得到每对顶点之间的最短路。但这样做需要大量重复计算，效率不高。R. W. Floyd（弗洛伊德）另辟蹊径，提出了比这更好的算法，操作方式与 Dijkstra 算法截然不同。 Floyd 算法的基本思想是：从图的带权邻接矩阵 A = a(i, j)nn 开始，在 A 中用插入顶点的方法依次构造出 n 个矩阵 D(1)、D(2)、D(n)，使最后得到的矩阵 D(n) 成为图的距离矩阵图的距离矩阵，即矩阵矩阵D(n)的的i 行行j 列元素便是列元素便是i 号顶点到号顶点到j 号顶号顶点的距离点的距离。构造 D(i) 的同时，也

10、引入一个路由路由矩阵矩阵P(i) 来记录两点间的最短路径。 构造矩阵 D(k)，k = 1, 2, , n，采用如下的递推公式： D(0) = dij(0)nn = A：是带权邻接矩阵，dij(0) 表示从 vi 到 vj 的、中间不插入任何点的路径，即边 vivj 的权值； D(1) = dij(1)nn，其中 dij(1) = mindij(0)，di1(0) d1j(0)：dij(1) 表示从 vi 到 vj 的、中间最多只允许 v1 作为插入点的路径中最短路的长度； D(2) = dij(2)nn，其中 dij(2) = mindij(1)，di2(1) d2j(1)：dij(2) 表

11、示从 vi 到 vj 的、中间最多只允许 v1 和 v2 作为插入点的路径中最短路的长度； D(n) = dij(n)nn，其中 dij(n) = mindij(n1)， di, n1(n1) dn1, j(n1)：dij(n) 表示从 vi 到 vj 的、中间最多只允许 v1, v2, , vn1 作为插入点的路径中最短路的长度，即 vi 和 vj 之间的距离。（II）求路径矩阵的方法.在建立距离矩阵的同时可建立路径矩阵R ivjv（III）查找最短路路径的方法.然后用同样的方法再分头查找若：1av2av3avkav1bv2bvmbv例 求下图中加权图的任意两点间的距离与路径. ,05314

12、2503330212044401210 )0(D,654321654321654321654321654321654321 )0(R,053142503330212044401210 )0(D,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点v1，得：得：,053132503330212043401210)1(D,654311654321654321654321154321654321 )1(R矩阵中带“=”的项为经迭代比较以后有变化的元素.,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点v2，得：得：,05313250333021

13、2043401210)1(D矩阵中带“=”的项为经迭代比较以后有变化的元素.,05313250333021204534012510)2(D,654311654321654321654322154321654221 )2(R,min) 1() 1() 1()(kkjkikkijkijdddd,053132503330267120453640127510)3(D,654311654321654333654322153321653221 )3(R插入点插入点v3，得：得：,05313250333021204534012510)2(D,min) 1() 1() 1()(kkjkikkijkijdddd

14、,053132503330267120453640127510)3(D插入点插入点v4，得：得：,05313250359103302671520453964012107510)4(D,654311654444654333644322143321643221 )4(R,)4()5(DD插入点插入点v5，得：得：,)4()5(RR,min) 1() 1() 1()(kkjkikkijkijdddd插入点插入点v6，得：得：,05313250359103302671520453964012107510)5(D,053132503587330265152043386401275310)6(D.6543

15、11654466654336644326163321666621 )6(R,053132503587330265152043386401275310)6(D.654311654466654336644326163321666621 )6(R8)6(52d故从v5到v2的最短路为8 6)6(52R由v6向v5追溯: . 6)6(56R由v6向v2追溯: , 1)6(62R. 2)6(12R所以从到的最短路径为： .2165vvvv Kruskal(克鲁斯卡尔克鲁斯卡尔)算法的基本思想算法的基本思想 设 T 和 C(T) 分别为图 G 的最小生成树的边集及其权值，初始状态均为空，算法结束时 T包含

16、最小生成树的所有边，C(T) 表示最小生成树的权值。令 VS是一个不相交的节点的集合，初始状态时 VS = v1, v2, , vn。算法的主要步骤是每次从边集 E 中选出一条未处理的有最小权值的边 (u, v) 进行分析，如果 u 和 v 同属于 VS 的一个元素集，则将边 (u, v) 删除，如果 u 和 v 分属于 VS 的两个元素集，则将边 (u, v) 加入到 T 中，并将这两个元素集合并为一个元素集并将这两个元素集合并为一个元素集，然后再从 E 中另选权值最小的边进行处理，直至找到一棵最小生成树为止。例n n个城市个城市, ,各城市之间的距离如下各城市之间的距离如下，从一个城市出发

17、走遍各个城市, ,如何选择最优的如何选择最优的旅行路线.用 Kruskal 算法求上图给出的赋权图的最小生成树。 解：将图的边按照权值从小到大进行排列：边(a, b) (c, e) (a, e) (b, c) (d, g) (a, c)权45791215边(d, f)(f, g)(c, d) (a, g) (e, g) (d, e)权162025283032步骤选出边ew(e)操作VSTC(T)1(a, b)4加到T中a, b, c, d, e, f, g(a, b)42(c, e)5加到T中a, b, c, e, d, f, g(a, b), (c, e)93(a, e)7加到T中a, b,

18、 c, e, d, f, g(a, b), (c, e), (a, e)164(b, c)9删除a, b, c, e, d, f, g(a, b), (c, e), (a, e)165(d, g)12加到T中a, b, c, e, d, g, f(a, b), (c, e), (a, e), (d, g)286(a, c)15删除a, b, c, e, d, g, f(a, b), (c, e), (a, e), (d, g)287(d, f)16加到T中a, b, c, e, d, g, f(a, b), (c, e), (a, e), (d, g), (d, f)448(f, g)20删除

19、a, b, c, e, d, g, f(a, b), (c, e), (a, e), (d, g), (d, f), (c, d)449(c, d)25加到T中a, b, c, e, d, g, f(a, b), (c, e), (a, e), (d, g), (d, f), (c, d)692求最小生成树的 Prim 算法Prim(普里姆普里姆)算法的直观描述算法的直观描述 假设 T是赋权图 G 的最小生成树。任选一个顶点将其涂红，其余顶点为白点；在一个端在一个端点为红色，另一个端点为白色的边中点为红色，另一个端点为白色的边中，找一条权最小的边涂红，把该边的白端点也涂成红色；如此，每次将一条

20、边和一个顶点涂成红色，直直到所有顶点都成红色为止到所有顶点都成红色为止。最终的红色边便构成最小生成树 T的边集合。 例如，上一小节给出的赋权图，按照上面的描述，容易求出其最小生成树。 在实际应用中，还会遇到求一个赋权图的最大生在实际应用中，还会遇到求一个赋权图的最大生成树的问题。比如，某图的边权代表的是利润或成树的问题。比如，某图的边权代表的是利润或效益，则最终的问题很可能就是求其最大生成树。效益，则最终的问题很可能就是求其最大生成树。事实上，从上面两个算法可以看出，只要边权的事实上，从上面两个算法可以看出，只要边权的选择改为从大到小，求最小生成树的算就可以用选择改为从大到小，求最小生成树的算

21、就可以用来求最大生成树了来求最大生成树了58 例：有一项工程，要埋设电缆将中央控制室与例：有一项工程，要埋设电缆将中央控制室与12个控制点连通。图中的各线段标出了允许挖电缆沟个控制点连通。图中的各线段标出了允许挖电缆沟的地点和距离（单位：百米）。若电缆线每米的地点和距离（单位：百米）。若电缆线每米20元，元，挖电缆沟（深挖电缆沟（深1米，宽米，宽0.6米）土方每立方米米）土方每立方米5元，请元，请作该项工程预算，回答最少需要多少元？作该项工程预算，回答最少需要多少元？ 行行 遍遍 性性 问问 题题一、中一、中 国国 邮邮 递递 员员 问问 题题二、推二、推 销销 员员 问问 题题三、建模案例：

22、最佳灾情巡视路线三、建模案例：最佳灾情巡视路线（一）（一） 欧欧 拉拉 图图（二）（二） 中中 国国 邮邮 递递 员员 问问 题题（一）（一） 哈哈 密密 尔尔 顿顿 图图（二）（二） 推推 销销 员员 问问 题题 定定义义 设图 G =（V，E） ，ME，若 M 的边互不相邻，则称 M 是 G 的一个匹匹配配.若顶点 v与 M 的一条边关联，则称 v是 M饱和的饱和的 设 M 是 G 的一个匹配，若 G 的每个顶点都是 M饱和的，则称 M 是 G 的理理想想匹匹配配.V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9割边G的边e是割边的充要条件是e不含在G的圈中 割边的定义割边

23、的定义：设G连通，e E(G),若从G中删除边e后，图G-e不连通，则称边e为图G的割边e3v1v2v3v4e1e2e4e5e6欧欧 拉拉 图图e3v1v2v3v4e1e2e4e5巡回：v1e1v2e2v3e5v1e4v4e3v3e5v1欧拉道路：v1e1v2e2v3e5v1e4v4e3v3欧拉巡回：v1e1v2e2v3e5v1e4v4e3v3e6v1中国邮递员问题中国邮递员问题- -定义定义 若将投递区的街道用边表示，街道的长度用边权表示，邮局街道交叉口用点表示，则一个投递区构成一个赋权连通无向图中国邮递员问题转化为：在一个非负加权连通图中，寻求一个权最小的巡回这样的巡回称为最最佳佳巡巡回回

24、中国邮递员问题中国邮递员问题- -算法算法 1、G是欧拉图是欧拉图 此时 G 的任何一个欧拉巡回便是最佳巡回问题归结为在欧拉图中确定一个欧拉巡回Fleury 算算法法：求欧拉图的欧拉巡回V7e3v1v2v3v4e1e2e4e5V5V6e6e7e8e9e10Fleury 算算法法 算算法法步步骤骤 ：（）任选 一个顶点 v0，令道路 w0=v0（）假定 道路 wi=v0e1v1e2eivi已经选好，则从 Ee1,e2, ,ei中选一条边 ei+1，使： a）ei+1与 vi相关联b）除非不能 选择，否 则一定要 使 ei+1不是 Gi=GE-e1,e2, ,ei的割边（）第（ ）步不 能进行时

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

26、小对集算法：基 本 思 想 ： 先将奇次顶点配对，要求最佳配对，即点对之间距离总和最小再沿点对之间的最短路径添加重复边得欧拉图 G*，G*的欧拉巡回便是原图的最佳巡回算法步骤：算法步骤：（）用 Floyd 算法求出的所有奇次顶点之间的最短路径和距离（）以 G 的所有奇次顶点为顶点集（个数为偶数） ，作一完备图，边上的权为两端点在原图 G 中的最短距离，将此完备加权图记为 G1（）在 G 中沿配对顶点之间的最短路径添加重复边得欧拉图 G*（）用 Fleury 算法求出 G*的欧拉巡回，这就是 G 的最佳巡回（）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对例例求右图所示投递区的一条最佳邮递路

27、线1图中有 v4、v7、v8、v9四个奇次顶点用 Floyd 算法求出它们之间的最短路径和距离：3),(,6),(,9),(,6)(,3),(,5),(,9898979787879,49848484747234989787948474vvdvvPvvdvvPvvdvvPvvdvvvPvvdvvPvvdvvvvPvvvvvvvvvvvv2以 v4、v7、v8、v9为顶点，它们之间的距离为边权构造完备图 G13求出 G1的最小权完美匹配 M=(v4,v7),(v8,v9)4在 G 中沿 v4到 v7的最短路径添加重复边，沿 v8到 v9的最短路径 v8v9添加重复边，得欧拉图 G2G2中一条欧拉巡

28、回就是 G 的一条最佳巡回其权值为返回返回哈哈 密密 尔尔 顿顿 图图定定义义设 G=(V,E)是连通无向图（） 经过 G 的每个顶点正好一次的路径，称为 G 的一条 哈哈密密尔尔顿顿路路径径（） 经过 G 的每个顶点正好一次的圈，称为 G 的哈哈密密尔尔 顿顿圈圈或 H 圈（）含 H 圈的图称为哈哈密密尔尔顿顿图图或 H 图返回返回推销员问题推销员问题- -定义定义 流动推销员需要访问某地区的所有城镇，最后回到出发点问如何安排旅行路线使总行程最小这就是推销员问题推销员问题 若用顶点表示城镇，边表示连接两城镇的路，边上的权表示距离（或时间、费用），距离（或时间、费用），于是推销员问题就成为在加

29、权图中寻找一条经过每个顶点至少一次的最短闭通路问题定义定义在加权图G=(V,E)中，（）权最小的哈密尔顿圈称为最佳最佳H圈圈（）经过每个顶点至少一次的权最小的闭通路称为最佳推销员回最佳推销员回路路 一般说来，最佳哈密尔顿圈不一定是最佳推销员回路，同样最佳推销员回路也不一定是最佳哈密尔顿圈H回路，长22最佳推销员回路，长4最佳推销员回路问题可转化为最佳 H 圈问题方法是由给定的图 G=(V,E)构造一个以 V 为顶点集的完备图 G=(V,E)，E的每条边(x,y)的权等于顶点 x 与 y 在图中最短路的权即：x,yE w(x,y)=mindG(x,y)定理定理加权图 G 的最佳推销员回路的权与 G的最佳 H 圈的权相同（）任取初始 H 圈: C0=v1,v2,vi, ,vj,vn,v1（）对所