图与网络.pptVIP

求解最短路的Dijkstra算法(双标号法） 步骤： 1.给出点V1以标号(0,s) 2.找出已标号的点的集合I，没标号的点的集合J以及弧的集合 3. 如果上述弧的集合是空集，则计算结束。如果vt已标号（lt,kt），则 vs到vt的距离为lt，而从 vs到vt的最短路径，则可以从kt 反向追踪到起点vs 而得到。如果vt 未标号，则可以断言不存在从 vs到vt的有向路。如果上述的弧的集合不是空集，则转下一步。 4. 对上述弧的集合中的每一条弧，计算 sij=li+cij 。在所有的 sij中，找到其值为最小的弧。不妨设此弧为（Vc,Vd），则给此弧的终点以双标号（scd,c）,返回步骤2。 最小生成树 求最大流的基本算法 （1）找出一条从发点到收点的路，在这条路上的每一条弧顺流方向的容量都大于零。如果不存在这样的路，则已经求得最大流。 （2）找出这条路上各条弧的最小的顺流的容量pf，通过这条路增加网络的流量pf。 （3）在这条路上，减少每一条弧的顺流容量pf ，同时增加这些弧的逆流容量pf，返回步骤（1）。 注意:在1中选的路不同,过程会不同,但结果应是一样的.为简化过程,在1中我们应选弧数最少的路. 作业P253 2, 3 运 筹 帷 幄 之 中 决 胜 千 里 之 外 运 筹 学 课 件 图与网络 Network Analysis 图论中图是由点和边构成，可以反映一些对象之间的关系。 例如：在一个人群中，对相互认识这个关系我们可以用图来表示，图11-1就是一个表示这种关系的图。 (v1) 赵 (v2)钱 (v3)孙 (v4)李 (v5) 周 (v6)吴 (v7)陈 e2 e1 e3 e4 e5 图11-1 基本概念 (v1) 赵 (v2)钱 孙(v3) 李(v4) 周(v5) 吴(v6) 陈(v7) e2 e1 e3 e4 e5 图11-2 a1 a2 a3 a4 a14 a7 a8 a9 a6 a5 a10 a12 a11 a13 a15 (v1) 赵 (v2)钱 (v3)孙 (v4)李 (v5) 周 (v6)吴 (v7)陈 图11-3 如果我们把上面例子中的“相互认识”关系改为“认识” 的关系，那么只用两点之间的联线就很难刻画他们之间的关系了，这是我们引入一个带箭头的联线，称为弧。 无向图： 由点和边构成的图，记作G=（V，E）。 有向图： 由点和弧构成的图，记作D=（V，A）。 连通图： 对无向图G，若任何两个不同的点之间，至少存在一条链，则G 为连通图。 回路： 若路的第一个点和最后一个点相同，则该路为回路。 赋权图： 对一个无向图G的每一条边(vi,vj)，相应地有一个数wij，则称图G为赋权图，wij称为边(vi,vj)上的权。 最短路问题：对一个赋权的有向图D中的指定的两个点Vs和Vt找到一条从 Vs 到 Vt 的路，使得这条路上所有弧的权数的总和最小，这条路被称之为从Vs到Vt的最短路。这条路上所有弧的权数的总和被称为从Vs到Vt的距离。 最短路问题 v1 v2 v3 v5 v6 v4 例1 3 5 7 2 5 2 1 5 3 1 例2 v1 v2 v3 v7 v5 v6 v4 15 5 3 10 4 6 2 4 6 17 例3 设备更新问题。某公司使用一台设备，在每年年初，公司就要决定是购买新的设备还是继续使用旧设备。如果购置新设备，就要支付一定的购置费，当然新设备的维修费用就低。如果继续使用旧设备，可以省去购置费，但维修费用就高了。请设计一个五年之内的更新设备的计划，使得五年内购置费用和维修费用总的支付费用最小。 13 12 12 11 11 年初价格 5 4 3 2 1 年份 18 11 8 6 5 每年维修费用 4-5 3-4 2-3 1-2 0-1 使用年数 将问题转化为最短路问题，如下图： 用vi表示“第i年年初购进一台新设备”,弧（vi,vj）表示第i年年初购进的 设备一直使用到第j年年初。 把所有弧的权数计算如下表： v1 v2 v3 v4 v5 v6 6 18 5 23 17 4 31 23 17 3 41 30 22 16 2 59 41 30 22 16 1 6 5 4 3 2 1 树是图论中的重要概念，所谓树就是一个无圈的连通图。 图中，(a)就是一个树，而(b)因为图中有圈所以就不是树， (c)因为不连通所以也不是树。 图11-11 v1 v2 v3 v4 v5 v6 v7 v8 v9 v1 v2 v3 v5 v8 v7 v6 v4 v1 v2 v3 v4 v5 v7 v6 v8 v9 (