管理运筹学第11章 图与网络模型.pptVIP

第十一章　图与网络模型 §1　图与网络的基本概念 §2　最短路问题 §3　最小生成树问题 §4　最大流问题 §5　最小费用最大流问题 §1　图与网络的基本概念 §1　图与网络的基本概念 §1　图与网络的基本概念 §1　图与网络的基本概念 无向图： 由点和边构成的图，记作G=（V，E）。 有向图： 由点和弧构成的图，记作D=（V，A）。 连通图： 对无向图G，若任何两个不同的点之间，至少存在一条链，则G为连通图。 回路： 若路的第一个点和最后一个点相同，则该路为回路。 赋权图： 对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。 网络： 在赋权的有向图D中指定一点，称为发点(记为vs)，指定另一点称为收点(记为vt)，其它点称为中间点，并把D中的每一条弧的赋权数cij称为弧(vi,vj)的容量，这样的赋权有向图D就称为网络。 §2　最短路问题 最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。 一、求解最短路的Dijkstra算法(双标号法） 步骤： 1.给出点V1以标号(0,s) 2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合 3. 如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则 vs到vt的距离为lt，而从 vs到vt的最短路径，则可以从vt 反向追踪到起点vs 而得到。如果vt 未标号，则可以断言不存在从 vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。 4. 对上述弧的集合中的每一条弧，计算 sij=li+cij 。在所有的 sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。 §2　最短路问题 例1 求下图中v1到v6的最短路 解：采用Dijkstra算法，可解得最短路径为v1 v3 v4 v6 各点的标号图如下： §2　最短路问题 求解过程如下: （1）给定起始点 标以（0，s),表示从 到 的距离为0， 为起始点。 （2）这时已标定点集合I={ },未标定点的集合J={ , , ， ， }， 弧集合 ， 则有min(s12,s13,s14)=s13=2, 这样，给弧 的终点 标以（2，1）， 表示从 到 的距离为2. （3）这时 ，则有min(s12,s14,s34)=s12=s34=3.给弧 的终点 标以（3，1），表示从 到 的距离为3；我们给弧 的终点 标以（3，3），表示从 到 的距离为3. （4）这时 ，则有min(s26,s46)=s46=8,这样给点 标以（8，4），表示从 到 的距离是8. （5）这时 ，而弧集合为空，也即 还未标号，说明从 到 没有有向路. （6）得到一族最优结果。从终点 的标号倒推到起点 ，得到此最短路径为 . §2　最短路问题 例2 电信公司准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。 解：这是一个求无向图的最短路的问题。可以把无向图的每一边（vi,vj）都用