图与网络分析(1-4).ppt

1、1,图与网络分析Graph Lsr+drp，则对p点标号，并将Lsp的值标注在p点旁的小方框内； 重复第3步，一直到t点得到标号为止。,43,Dijkstra算法举例,例3 求下图中从v1到v7的最短路,图 6-10,44,解题-1,（1）从点v1出发，对v1标号，将L11=0标注在v1旁的小方框内。令 ，其余点属于 。,V,45,(2)同v1相邻的未标号点有v2、v3。L1r=mind12,d13=min5,2=2=L13,即对点v3标号，将L13的值标注在v3旁的小方框内。将v1,v3加粗，并令,解题-2,，,46,(3)同标号点v1、v3相邻的点有v2、v4、v6，故有 对v2点标号，将

2、L12的值标注在v2点旁的小方框内，将v1,v2加粗，并令，,解题-3,，,(c),47,解题-4,(4)同标号点v1、v2、v3相邻的点有v5、v4、v6，有 故对点v6标号，将L16的值标注在v6点旁的小方框内，将v3, v6加粗，并令，,48,解题-5,(5)同标号点v1、v2、v3、v6相邻的点有v4、v5、v7，有 故对点v4和v5同时标号，将L14=L15=7的值分别标注在v4和v5点旁的小方框内，将v2,v4及v6,v5加粗，并令，,，,49,解题-6,同各标号点相邻的未标号点只有v7，因有 故在点v7旁小方框内标注L17=10，加粗v6,v7 。图(f)中的粗线表明从点v1到网

3、络中其它各点的最短路，各点旁方框中的数字是从v1点到各点的最短距离。,10,50,矩阵算法,Dijkstra算法提供了从网络图中某一点到其它点的最短距离。 但实际问题中往往要求网络任意两点之间的最短距离，如果仍采用Dijkstra算法对各点分别计算，就显得很麻烦。 求网络各点间最短距离矩阵计算法。,51,矩阵算法举例,在图6-10中用矩阵计算法求各点之间的最短距离,图 6-10,52,解题-1,定义dij为图中两相邻点的距离，令,=,53,解题-2,上面矩阵表明从i点到j点的直接最短距离。但从i到j的最短路不一定是ij，可能是ilj，ilkj，或ilkj。 先考虑i与j之间有一个中间点的情况，

4、如图6-10中v1v2的最短距离应为mind11+d12,d12+d22,d13+d32,d14+d42,d15+d52,d16+d62,d17+d72，也即mind1r+dr2。,54,解题-3,为此可以构造一个新的矩阵D(1)，令D(1)中每个元素 则矩阵D(1)给出了网络中任意两点之间直接到达和包括经一个中间点时的最短距离,55,解题-4,再构造矩阵D(2)。令 则D(2)给出网络中任意两点之间直接到达，及包括经过一至三个中间点时的最短距离。,56,解题-5,再构造矩阵D(3)。令 则D(3)给出网络中任意两点之间直接到达，及包括经过一至四个中间点时的最短距离。 计算可得：D(2)= D

5、(3) D(3)各个元素值即为各点间最短距离,57,一般地有 矩阵D(k)给出网络中任意两点之间直接到达，经过一个、两个到（2k-1）个中间点到达时比较得到的最短距离。 设网络图有p个点，则一般计算到不超过D(k)，k的值按式 计算 即 如果计算中出现D(m+1)=D(m)时，计算即可结束，矩阵中D(m)的各个元素值即为各点间最短距离。 本例中， 所以最多计算到D(3)，,58,例5,假定图6-10中v1、v2、v3、v4、v5、v6、v7为七个村子，决定要联合办一所小学。 已知各村的小学生人数分别为v1 -30， v2 -40， v3 -25， v4 -20， v5 -50， v6 -60，

6、 v7 -60， 则小学应建在哪一个村子，使小学生上学走的总路程为最短？,59,解题,将上例中计算得到的D（3）的第一行乘v1村的小学生人数，则乘积数字为假定小学建于各个村时， v1村小学生上学单程所走路程。 将D（3）第二行数字乘v2村小学生人数，得小学建于各个村子时， v2村小学生上学所走路程。 依此类推可计算得到下表。,60,决策方案：小学应建在v6村,小学建于vi村时，7个村子的学生累计的一次单程上学路程。,61,应用举例设备更新问题,某企业使用一台设备，在每年年初，企业领导部门需要决定 是购置新的还是继续使用旧的； 若购置新设备需支付一定的购置费用，若继续使用旧的，须支付一定的维修费

7、用。 问题是：如何制定一个五年之内的设备更新计划，使得总的支出费用最少。,62,63,用点vi表示“第i年年初购进一台设备”；用弧（vi，vj）表示在第i年年初购进的设备一直使用到第j年年初。则问题成为最短路径问题。,16,16,17,17,18,22,30,41,59,22,30,41,23,31,23,64,中国邮路问题,第四节,65,问题提出,一个邮递员从邮局出发，走遍他负责投递的每一条街道，然后再返回邮局，问应选择什么样的路线，使走的路程为最短。 因这个问题最早由中国数学工作者提出（1962年管梅谷提出），故称中国邮路问题。,66,哥尼斯堡七桥问题,一个散步者能否走过七座桥，且每次只走

8、过一次，最后回到出发点。,普雷格尔河,67,欧拉“一笔画问题”,68,欧拉图,欧拉回路： 连通图G中，若存在一条回路，经过每边一次且仅一次，称这条回路为欧拉回路。 欧拉图：具有欧拉回路的图。 可以证明，连通图G是欧拉图的充分必要条件是图中的点全为偶点。 某图如能一笔画出，此图必为欧拉链或欧拉圈 能否一笔画：连通图中只有小于等于2个的奇点。 基于欧拉图和欧拉回路的概念，结合例子讨论邮递员的最短投递路线问题。,69,例6,设某邮递员负责投递的街道如图6-12所示，要求找出该邮递员的最短投递路线。 如果投递路线图中没有奇点，可以走到没有重复路线的最短路径。 奇点几个？,70,解题-1,若图6-12是

9、欧拉图，则图中的欧拉回路就是邮递员的最短投递路线。 否则将图转化成欧拉图， 转化方法：将图中奇点两两相连，变成偶点，则包括连线在内的图构成欧拉图，而连线的长度就是邮递员要在街道上重复走的路。,71,解题-2,邮递员重复走的路最短，就是要使奇点两两之间的连线最短，为此奇点间的连线应符合下列条件： (a)每条边上最多重复一次； (b)在图G的每个回路上，有重复的边的长度不超过回路总长的一半。,72,图 6-13,解题-3,图6-12不是欧拉图，图上有8个奇点(用号标示)，说明邮递员必须要在某些区段重复走，才能走遍所有负责投递的街道。 将奇点两两连结(用虚线表示，图6-13)，则所有奇点都成了偶点。 因此包括虚线在内的线路邮递员可走遍而做到不重复。如图所示为其一。,73,解题-4,为使邮递员重复走的路程也即虚线的长度为最短，可根据上述条件(a)和(b)进行调整。 (a)每条边上最多重复一次； (b)在图G的每个回路上，有重复的边的长度不超过回路总长的一半。,图 6-13,74,解题-4,在回路v4,v5,v11,v10,v4中，虚线长度超过回路长度一半，故改将v4与v5连结，v11与v12连结。 又在回路v2,v3,v9,v6,v2中，同样虚线长超过回路长度一半，故可将虚线标到回路的另