图论中的几个典型问题上.ppt

图论中的几类典型问题（上）;重要性质：;固定起点的最短路;求赋权图中固定起点的最短路的Dijkstra算法：;算法步骤：;TOMATLAB

(road1);;算法的基本思想;算法原理——求距离矩阵的方法;算法原理——求路径矩阵的方法;;设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算法,首先写出其(对称的)权矩阵A=(aij)8×8，然后利用计算机编程计算.;以下仅从图上进行直观操作.;从上图中容易得到任意两点间的最短路.;;最优截断切割问题;模型的建立与求解;设u1≥u2，u3≥u4，u5≥u6，故只考虑M1在M2前、M3在M4前、M5在M6前的切割方式.;(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)表示石材加工完成状态.;(3)根据准则知第一刀应切M1、M3、M5中某个面，分别对应弧(V1,V2)，(V1,V4)，(V1,V10).从V1到V27任意一条有向路代表一种切割方式.共对应90种切割方式.V1到V27的最短路对应所求的最优切割方式;2、e?0的情况;;由上表知:三种情况中

情形(1)有公共点集{(2,1,z)|z=0,1,2}，

情形(2)有公共点集{(1,2,z)|z=0,1,2}.;综述，将图G分为图Ｈ1和Ｈ2，把指定边上的权增加e，分别求Ｈ1和Ｈ2中从V1到V27的最短路，最短路的权分别为:d1,d2.则整体最少费用：d=min(d1,d2)，最优切割序列即为其对应的最短路径.;欧拉回路和中国邮递员问题;一.中国邮递员问题-定义;中国邮递员问题-算法;V7;若G不是欧拉图，则G的任何一个巡回经过某些边必定多于一次．;V7;（３）求出G1的最小权理想匹配M，得到奇次顶点的最佳配对．;解中国邮递员问题的步骤;解中国邮递员问题的步骤;二.哈密顿环球旅行问题(货郎担问题,旅行售货商问题,Hmilton问题):

十二面体的20个顶点代表世界上20个城市，能否从某个城市出发在十二面体上依次经过每个城市恰好一次最后回到出发点？;哈密尔顿回路及旅行售货商问题;任两点间都有边的图为完全图,完全图中有(n-1)!/2条不同的哈密尔顿回路,有(n-1)/2个边不相交的哈密尔顿回路.

哈密尔顿路径：包含图中所有点的路径.;G是有向图，把G各边方向去掉所得无向图叫G的底图；若G的底图是连通图，则称G是弱连通有向图；在有向图G中，u,v?V(G),且G中存在有向轨P(u,v)，则称u可到达v，;;售货商问题-定义;定义在加权图G=(V,E)中，

（１）权最小的哈密尔顿圈称为最佳H圈．

（２）经过每个顶点至少一次的权最小的闭通路称为最佳售货商回路．;旅行售货商问题近似算法：二边逐次修正法：;例对以下完备图，用二边逐次修正法求较优H圈．

;灾情巡视路线

(CUMCM1998B题);今年夏天该县遭受水灾。为考察灾情、组织自救，县领导决定，带领有关部门负责人到全县各乡(镇)、村巡视。巡视路线从县政府所在地出发，走遍各乡(镇)、村，又回到县政府所在地。;;3.在上述关于T、t、和V的假设下，如果巡视人员足够多，完成巡视的最短时间是多少？给出这种最短时间完成巡视的要求下，你认为最佳的巡视路线。;三.模型的建立与分析;(2).经过每个顶点至少一次且权和最小的通路称为最佳经销商回路。;算法1：(求图G的最佳经销商回路);将G分成n个生成子图G[V1],G[V2],…,G[Vn]。使得：;求V的一个划分：求O到其余各点的最短路，这些路构成一棵树，如图(1):