苏大_张芳华_运筹学课件第七章网络规划.ppt

图论导引 最小支撑树问题 最短路问题 网络上的最大流问题 本章教学基本要求 1． 理解图的基本概念； 2． 掌握树和最小支撑树的定义和性质； 3． 熟练掌握求最小支撑树的方法； 4． 熟练掌握D氏算法求最短路问题和最短链问题； 5． 了解Floyd算法求最短路问题的原理和方法； 6． 掌握网络最大流的有关概念； 7． 熟练求解网络最大流问题； 8． 掌握截集概念和学会求解最小截集； 9． 了解最小费用流的算法。 图 论 导 引 哥尼斯堡七桥问题 图 的 示 例 点和线画出各种各样的示意图 图 的 示 例 图的基本概念 图的意义 图的基本概念 用G=（V，E） 表示 其中V表示图G的全部顶点的集合 E表示图G的全部边的集合 多重边 ：两个端点都完全相同的边（e2和e3） 弧立点 ：不与任一条边相关联的点(v5) 简单图 :无环无多重边的图 多重图：无环有多重边的图 若无特别声明，我们研究的图一般都是指简单图。 图的基本概念 点与（有向）边 每一条边和两个节点关联，一条边可以用两个节点的标号表示（i，j） 最小支撑树算法—Kruskal 第一步，将图的所有边按权从小到大的次序排列出来； 第二步，逐边检查，首先把最短的一条边留下来，同时，在检查每一条边时，如它不与已留下的边形成圈，就留下来，否则就去掉； 直至所有被留下来的边形成支撑树时，计算终止。 最小支撑树算法—Prim 首先从图中取出权最小的一边来，把他看成一树，然后把此树逐步扩大，直至支撑整个图为止。每次扩大时，都是先考虑那些与作出的树有边相连的各点，从中找出权最小的边，然后把此边及其端点加到已作出的树中去。 D氏方法的基本思想是从V1出发,逐步地向外探寻最短路。执行过程中与每个点对应,记录下这个点的标号（λij ，?）。 λij表示从V1到该点的最短路的权; ?表示从何处获得的最短权; 其中有λij= λi+wij 按此方法依次从已标号的点出发对没有标号的点考察，并获取标号，直到使终点获得标号。就可以求出从V1到各点的最短路. 如果一个有向图D中存在权为负数的回路(称为负回路) ，这样两点间最短路的长度就没有下界。 设给定有向图D=(V,E)及E上的权函数w(e) 以wj表示从vi到vj的最短路的权, w=(vi,vj)仍简记为wij.又设V的点数为n,易知w1, w2, wn,必须满足如下方程: wj =min{ wi+wij}, (vj∈V j=1,2,……n) 对一切i规定wii=0, 若V中的两点vi和vj之间无弧相连,则令w=(vi,vj)=+∞,这样便可认为,任何两点之间都有弧相连了. 开始令wj(0)= w1j(j=1,2,……n),一般地,设已有各个wj(k-1),则: wj(k)= min{ wi(k-1)+ wij} (j=1,2,……n) 当过程进行到某一步,发现每个j都有wj(k)= wj(k-1)时,则计算停止,此时wj(k)就是从vi到vj的最短路的权. 上述算法最多经过n-1次迭代必定收敛。若在已算出的wj(n-1)中至少有某个j,使得wj(n-1)≠wj(n-2), 说明图中有负回路，无最短路. 求解过程可在表上进行。表的左边是初始数据，右边是各次迭代的计算结果，最右边的一列数字就是从V1到各个VJ的最短路的权。 求Wj(1) Wj(1) = min {Wi(0) + Wij } W1(1) = min {W1(0) + W11、 W2(0) + W21… W5(0) + W51} = min{0+0、2+2、3-2}=0 W2(1) = min {W1(0) + W12、 W2(0) + W22… W5(0) + W52} = min{0+2、2+0、3-4}=-1（3，2） W3(1) = min {W1(0) + W13、 W2(0) + W23… W5(0) + W53} = min{0+3、3+0}=3（1，3） W4(1) = min {W1(0) + W14、 W2(0) + W24… W5(0) + W53} = ∞ W5(1) = min {W1(0) + W15、 W2(0) + W25… W5(0) + W55} = min{2-2}=0（2，5） 求Wj(3) Wj(3) = min {Wi(2) + Wij } W1(3) = min {W1(2) + W11、 W2(2) + W21… W5(2