图论中的几个典型问题(上)

《图论中的几个典型问题(上)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、图论中的几类典型问题（上）二.行遍性问题：中国邮递员问题，货郎担问题(旅行售货商题Hamilton问题）三.建模竞赛中的实例一.最短路问题重要性质：若v0v1…vm是图G中从v0到vm的最短路,则1≤k≤m,v0v1…vk必为G中从v0到vk的最短路.即：最短路是一条路，且最短路的任一段也是最短路.求非负赋权图G中某一点到其它各点最短路，一般用Dijkstra标号算法；求非负赋权图上任意两点间的最短路，一般用Floyd算法.这两种算法均适用于有向非负赋权图.一.最短路问题固定起点的最短路最短路是一条路径，且最短路的任一段也是最短路．假设在u

2、0-v0的最短路中只取一条，则从u0到其余顶点的最短路将构成一棵以u0为根的树．因此,可采用树生长的过程来求指定顶点到其余顶点的最短路．求赋权图中固定起点的最短路的Dijkstra算法：算法步骤：TOMATLAB(road1)u1u2u3u4u5u6u7u8算法的基本思想返回求赋权图中任意两点的最短路的Floyd算法：算法原理——求距离矩阵的方法返回算法原理——求路径矩阵的方法在建立距离矩阵的同时可建立路径矩阵R．即当vk被插入任何两点间的最短路径时，被记录在R(k)中，依次求时求得，可由来查找任何点对之间最短路的路径．ij算法原理——查找最

3、短路路径的方法pkp2p1p3q1q2qm则由点i到j的最短路的路径为：设A=(aij)n×n为赋权图G=(V,E,F)的权矩阵,dij表示从vi到vj点的距离,rij表示从vi到vj点的最短路中一个点的编号.①赋初值.对所有i,j,dij=aij,rij=j.k=1.转向②.②更新dij,rij.对所有i,j,若dik+dkj＜dij,则令dij=dik+dkj,rij=k,转向③;③终止判断.若k=n终止;否则令k=k+1,转向②.最短路线可由rij得到.算法步骤例2求下图中任意两点间的最短路:解：用Floyd算法,首先写出其(对称的)权

4、矩阵A=(aij)8×8，然后利用计算机编程计算.0123456700281∞∞∞∞1206∞1∞∞∞28607512∞31∞70∞∞9∞4∞15∞03∞85∞∞1∞30466∞∞29∞4037∞∞∞∞8630以下仅从图上进行直观操作.根据若dik+dkj＜dij,则令dij=dik+dkj.将原来的赋权值改变为

5、v2v4

6、=4,

7、v5v6

8、=3.再依次改变为

9、v1v2

10、=5,

11、v0v2

12、=7.接下来根据若dij=dik+dkj,则删除vi到vj的连线.得到从上图中容易得到任意两点间的最短路.例如,v1到v6的路有三条：v1v0v3v2v6(

13、长度为12),v1v4v5v2v6(长度为7),v1v4v7v6(长度为12).TOMATLAB(road2(floyd))最优截断切割问题问题：从长方体中经6次截断切割切出一个已知尺寸、位置预定的长方体(两长方体对应表面平行)，设水平切割单位面积费用是垂直切割单位面积费用r倍.当先后两次切割的平面不平行时，因调整刀具需额外费用e.试设计各面加工次序(称“切割方式”)方法，使加工费用最少.假设1.水平切割单位面积费用为r，垂直切割单位面积费用1；2.先后两次切割平面不平行时，调整刀具需额外费用e；3.第一次切割前，刀具已调整完毕，即第一次垂直

14、切割不加入刀具调整费用；4.每个待加工长方体必须经6次截断切割.模型的建立与求解设待加工长方体的左右面、前后面、上下面间距离分别为a0、b0、c0，六个切割面Mii=1、2、3、4、5、6分别位于左、右、前、后、上、下，这六个面与待加工长方体相应外侧面的边距分别为uii=1、2、3、4、5、6.这样,一种切割方式就是六个切割面一个排列,共P66=720种切割方式.当考虑切割费用时，显然有局部优化准则：两个平行待切割面中，边距较大的待切割面总是先加工.由此准则,在求最少加工费用时只需考虑种切割方式.设u1≥u2，u3≥u4，u5≥u6，故只考虑

15、M1在M2前、M3在M4前、M5在M6前的切割方式.1、e=0的情况构造有向赋权网络图G(V,E).为了表示切割过程的有向性，在网络图上加上坐标轴x，y，z.图9-13G(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)长方体石材从

16、状态Vi一次切割变为VjVi(xi,yi,zi)到Vj(xj,yj,zj)有弧(Vi,Vj)，相应弧上的权W(Vi,Vj)为此切割过程的费用.W(Vi,Vj)=(