《图论中的几个典型问题(上)》由会员分享，可在线阅读，更多相关《图论中的几个典型问题(上)（75页珍藏版）》请在金锄头文库上搜索。
1、图论中的几类典型问题（上）,二.行遍性问题：中国邮递员问题，货郎担问题(旅行售货商题Hamilton问题）,三.建模竞赛中的实例,一.最短路问题,重要性质：,若v0 v1 vm 是图G中从v0到vm的最短路, 则1km, v0v1 vk 必为G中从v0到vk的最短路.,即：最短路是一条路，且最短路的任一段也是最短路. 求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.这两种算法均适用于有向非负赋权图.,一.最短路问题,固 定 起 点 的 最 短 路,最短路是一条路径，且最短路的任一段也是最短路,假设在u0-v0的最短
2、路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树,因此, 可采用树生长的过程来求指定顶点到其余顶点的最短路,求赋权图中固定起点的最短路的Dijkstra算法：,算法步骤：,TO MATLAB (road1),u1,u2,u3,u4,u5,u6,u7,u8,算法的基本思想,返回,求赋权图中任意两点的最短路的Floyd算法：,算法原理 求距离矩阵的方法,返回,算法原理 求路径矩阵的方法,在建立距离矩阵的同时可建立路径矩阵R,即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求 时求得 ，可由 来查找任何点对之间最短路的路径,算法原理 查找最短路路径的方法,pk,p2,p
3、1,p3,q1,q2,qm,则由点i到j的最短路的路径为：,设A = (aij )nn为赋权图G = (V, E, F)的权矩阵, dij表示从vi到vj点的距离, rij表示从vi到vj点的最短路中一个点的编号. 赋初值. 对所有i, j, dij = aij, rij = j. k = 1. 转向. 更新dij , rij . 对所有i, j, 若dik + dk jdij , 则令dij = dik + dkj , rij = k, 转向; 终止判断. 若k = n终止; 否则令k = k + 1, 转向. 最短路线可由rij得到.,算法步骤,例2 求下图中任意两点间的最短路:,解：用F
4、loyd算法,首先写出其(对称的)权矩阵A = (aij )88，然后利用计算机编程计算.,0 1 2 3 4 5 6 7 0 0 2 8 1 1 2 0 6 1 2 8 6 0 7 5 1 2 3 1 7 0 9 4 1 5 0 3 8 5 1 3 0 4 6 6 2 9 4 0 3 7 8 6 3 0,以下仅从图上进行直观操作.,根据若dik + dkjdij , 则令dij = dik + dkj .将原来的赋权值改变为|v2v4|=4,|v5v6|=3. 再依次改变为|v1v2|=5,|v0v2|=7. 接下来根据若dij = dik + dkj ,则删除vi到vj的连线.,得到,从上
5、图中容易得到任意两点间的最短路.,例如,v1到v6的路有三条： v1v0v3v2v6(长度为12), v1v4v5v2v6(长度为7), v1v4v7v6(长度为12).,TO MATLAB (road2(floyd),最优截断切割问题,问题：从长方体中经6次截断切割切出一个已知尺寸、位置预定的长方体(两长方体对应表面平行)，设水平切割单位面积费用是垂直切割单位面积费用r倍.当先后两次切割的平面不平行时，因调整刀具需额外费用e.试设计各面加工次序(称“切割方式”)方法，使加工费用最少.,假 设 1. 水平切割单位面积费用为r，垂直切割单位面积费用1； 2.先后两次切割平面不平行时，调整刀具需额
6、外费用e； 3.第一次切割前，刀具已调整完毕，即第一次垂直切割不加入刀具调整费用； 4.每个待加工长方体必须经6次截断切割.,模型的建立与求解,设待加工长方体的左右面、前后面、上下面间距离分别为 a0、b0、c0 ，六个切割面Mi i=1、2、3、4、5、6分别位于左、右、前、后、上、下，这六个面与待加工长方体相应外侧面的边距分别为 ui i=1、2、3、4、5、6. 这样, 一种切割方式就是六个切割面一个排列, 共P66=720种切割方式. 当考虑切割费用时，显然有局部优化准则：两个平行待切割面中，边距较大的待切割面总是先加工.,由此准则,在求最少加工费用时只需考虑,种切割方式.,设u1u2
7、，u3u4，u5u6，故只考虑M1在M2前、M3在M4前、M5在M6前的切割方式.,1、e=0 的情况,构造有向赋权网络图G(V,E).为了表示切割过程的有向性，在网络图上加上坐标轴x，y，z.,图9-13 G(V,E),(1) 图中点Vi(xi,yi,zi)表示被切石材所处状态. 坐标xi、yi、zi分别代表石材在左右、前后、上下方向已被切割的刀数. 如：V24(2,1,2) 表示石材在左右方向上已切两刀，前后方向被切一刀，上下方向被切两刀，即面M1、M2、M3、M5、M6均已被切割. 顶V1(0,0,0) 表示石材最初待加工状态，顶V27(2,2,2)表示石材加工完成状态.,(2) 长方体
8、石材从状态Vi一次切割变为VjVi(xi, yi, zi) 到Vj(xj, yj, zj)有弧(Vi,Vj)，相应弧上的权W(Vi,Vj)为此切割过程的费用.,W(Vi,Vj)=(xj -xi)(bi ci)+(yj -yi)(ai ci)+(zj -zi)(ai bi)r,其中，ai、bi、ci分别代表在状态Vi时，长方体的左右面、上下面、前后面之间的距离.,例如，状态V5(1,1,0)，a5=a0+u1, b5=b0+u3, c5= c0; 状态V6(2,1,0); W(V5,V6)(b0+u3)c0.,(3)根据准则知第一刀应切M1、M3、M5中某个面，分别对应弧( V1,V2)，(V1
9、,V4)，(V1,V10). 从V1到V27任意一条有向路代表一种切割方式. 共对应90种切割方式. V1到V27的最短路对应所求的最优切割方式,实例：待加工长方体和成品长方体的长、宽、高分别为10、145、19 和3、2、4，两者左侧面、正面、底面之间的距离分别为6、7、9，则边距如下表：,V1V10V13V22V23V26V27，其权为374,r=1时，求得最短路为:,对应最优切割为M5M3M6M1M4M2， 费用为374元.,2、 e0的情况,先后两次切面不平行时，需加调刀费e. 图9-13中某些边在所有切割序列中顺序不同，故所加权不同. 怎么办?,先切一对平行面，再切另外一对平行面，总
10、费用比e=0时的费用增加e.,先切一个，再切一对平行面，最后割剩余的一个，总费用比e=0时的费用增加2e.,切割面是两两相互垂直，总费用比e=0时的费用增加3e.,所考虑90种切割中，上述三种情况下切面的排列及在图G中对应有向路必经点如下表：,四个垂直面的切割顺序只有三种可能情况：,z=0,1,2,由上表知: 三种情况中 情形(1)有公共点集(2,1,z)|z=0,1,2， 情形(2)有公共点集(1,2,z)|z=0,1,2.,情形(1)的有向路不通过情形(2)的公共点集， 情形(2)的有向路也不通过情形(1)的公共点集. 故这两部分是独立的、互补的.,在图G中分别去掉点集(1,2,z)|z=
11、0,1,2和(2,1,z)|z=0,1,2及与之相关联的入弧，形成1和2两个新图. 则1和2具有互补性. 所求最短路必存在于1和2某一个中.,调整3次刀具，总费用增加3e，先安排此情况的权增加值，每次转刀，给其待切弧上的权增加e. 如图9-14所示. 再判断是否满足调整二次、一次刀具时的情况，发现所加的权满足另外两类切割序列.,综述，将图G分为图1和2，把指定边上的权增加e，分别求1和2中从V1到V27的最短路，最短路的权分别为:d1, d2. 则整体最少费用：d = min(d1,d2) ，最优切割序列即为其对应的最短路径.,例：r=15,e=2时，最短路为H2的路V1V4V5V14V17V
12、26V27，权为4435，对应最优切割序列为M3M1M6M4M5M2，最优费用为4435.,图9-14 H1,图9-15 H2,欧拉回路和中国邮递员问题,中国邮递员问题(Chinese Postman Problem, CPP)由我国管梅谷教授于1962年首先提出并发表的 问题是从邮局出发，走遍邮区的所有街道至少一次再回到邮局，走什么路由才能使总的路程最短？ 如果街区图是一个偶图，根据定理 3，一定有欧拉回路，CPP 问题也就迎刃而解了 若街区图不是偶图，则必然有一些街道要被重复走过才能回到原出发点 显然要在奇次点间加重复边 如何使所加的边长度最少 归结为求奇次点间的最小 匹配( minimu
13、m weighted match) 由Edmons 给出 多项式算法(1965),一.中国邮递员问题-定义,中国邮递员问题-算法,Fleury算法-基本思想：从任一点出发，每当访问 一条边时，先要进行检查如果可供访问的边不只 一条，则应选一条不是未访问的边集的导出子图的 割边(桥:G的某条边,不在G的任一圈或者去掉该边图 就不连通)作为访问边，直到没有边可选择为止.,若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次,解决这类问题的一般方法是，在一些点对之间 引入重复边（重复边与它平行的边具有相同的权）， 使原图成为欧拉图，但希望所有添加的重复边的 权的总和为最小,（）求出G1的最小权理
14、想匹配M，得到奇次顶点的最佳配对,解中国邮递员问题的步骤,0、将图中的所有悬挂点依次摘去 1、求所有奇次点间的最短距离和最短路径 2、根据奇次点间的最短距离求最小完全匹配 3、根据最小完全匹配和最短路径添加重复边 4、将悬挂点逐一恢复，并加重复边 5、根据得到的偶图，给出欧拉回路的若干种走法,解中国邮递员问题的步骤,二. 哈密顿环球旅行问题(货郎担问题,旅行售货商问题,Hmilton问题): 十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？,含一切顶的轨叫Hamilton轨。,闭的Hamilton轨为Hamilton圈。,哈密尔顿
15、回路及旅行售货商问题,( Hamiltonian circuit) 连通图G(V,E)中的回路称为哈密尔顿回路，若该回路包括图中所有的点。显然哈密尔顿回路有且只有 n 条边，若|V|=n 连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是由爱尔兰数学家哈密尔顿1859年提出的，但至今仍未解决. 欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访问的问题 搜索哈密尔顿回路的难度是 NP-complete,任两点间都有边的图为完全图, 完全图中有(n-1)!/2条不同的哈密尔顿回路, 有(n-1)/2个边不相交的哈密尔顿回路. 哈密尔顿路径：包含图中所有点的路径.,旅行售货商(TSP)：设
16、v1, v2, .,vn 为 n 个城市，城市之间的路程已知，售货商从 v1出发，走遍所有城市一次且仅一次回到v1，并使总旅程最短.,不允许点重复的售货商问题就是最小哈密尔顿回路问题 一般售货商问题(GTSP)：允许点重复的TSP 当网路边权满足三角不等式时，一般售货商问题等价于最小哈密尔顿回路问题 网路边权不满足三角不等式时，用两点间最短路的距离代替原来边权，就可满足三角不等式，在此基础上求最小哈密尔顿回路,G是有向图，把G各边方向去掉所得无向图叫G的底图；若G的底图是连通图，则称G是弱连通有向图；在有向图G中，u,vV(G), 且G 中存在有向轨P(u,v)，则称u可到达v，,每对顶都连边的有向图为竞赛图。,
