[其它]图论0511.ppt

第五章 图与网络分析 重点: 理解图与网络的基本概念：掌握最小树、最短路、最大流问题的解法。 重点掌握DIJKSTRA法、FLOYD法、最大流的标号法、最小载集最大流量定理和最小费用最大流算法。 U(1) = 0 5 ? ? ? ? 0 6 ? -3 ? ? 0 ? 2 4 9 8 0 ? 4 9 ? -2 0 同时，在修正 处修改 U(1) = 0 5 ? ? ? ? 0 6 ? -3 ? ? 0 ? 2 4 9 8 0 ? 4 9 ? -2 0 U(2) = 0 5 11 ? 2 ? 0 6 ? -3 ? ? 0 ? 2 4 9 8 0 6 4 9 15 -2 0 （2）用 U(1) 的第二行、第二列修正其余的 uij， （3）用 U(2) 的第三行、第三列修正其余的 uij， 2 7 6 （4）用 U(3) 的第四行、第四列修正其余的 uij 4 4 4 8 0 -1 3 -5 4 9 0 （5）用 U(4) 的第五行、第五列修正其余的 uij 2 2 5 5 5 5 5 5 从 v1 到 v3 的最短路长度 路径： 从 v5 到 v2 的最短路长度及路径？ 3000 4 6500 2 4500 3 6500 4 3000 2 4500 3 1 1 莎拉购买二手车的数据 8500 2000 12000 最后一年卖出的价值 （美元） 拥有年份的开车和保养的费用（美元） 购买 价格 应用举例：设备更新问题某企业使用一台设备，在每年年初，企业领导部门就要决定是购置新的，还是继续使用旧的。若购置新设备，需要支付一定的购置费用；若继续使用旧设备，则需支付一定的维修费用。现在的问题是如何制定一个几年之内的设备更新计划，使得总的支付费用最少。现以二手车问题为例。 应用：设某台新设备的年效益及年均维修费用、更新净费用如下表，试确定今后五年内的更新策略，使总效益最大。（设?=1） 3.5 3 2.5 5 3 2.5 3 4 2.5 2.2 1.5 0.5 更新费CK(t) 2 1.5 1 0.5 运行费OK(t) 3.75 4 4.5 5 效益IK(t) 3 2 1 0 役龄 项目 ① ② ③ ④ ⑤ ⑥ 5-0.5-1.5 15.75 3 3 3 3 4.5 5-0.5+4.5-1-2.2 5.8 5.8 5.8 8 5-0.5+4.5-1+4-1.5-2.5 8 8 10.5 5-0.5+4.5-1+4-1.5+3.75-3 12.25 15.25 5-0.5+4.5-1+4-1.5+3.75-2+3-2.5 § 4 网络最大流问题 例 连接某产品产地 v1 和销地 v6 的交通网如下： v2 v5 3 4 8 v3 v1 v4 v6 5 10 6 11 17 3 5 这条运输线的最大通过能力 5 2 6 2 3 3 1 1 2 3 运输数量 制定一个运输方案，使从 v1 到 v6 的产品数量最多。 问题：这个运输网络中，从 v1 到 v6 的最大输送量是多少？ 4.1 基本概念与定理 1.网络与流 定义1 给定一个有向图D=(V, A)，在V中指定一点 vs 称为发点，指定另一点 vt 称为收点，其余点称中间点。任意弧(vi, vj) ∈A，有Cij≥0，称为弧的容量。称 D 为一个容量网络。记为 D =（V，A，C）。 流: 定义在弧集A上的一个函数 f = { f (vi , vj ) }，并称 f ( vi , vj ) 为弧 ( vi , vj ) 上的流量 ( 简记 fij ) 。 如 ( a ) 图是一个网络 如 ( b ) 图是网络上的一个流 弧旁数字：容量 弧旁数字：流量 v2 v5 3 4 8 v3 v1 v4 v6 5 10 6 11 17 3 5 （a） v2 v5 3 1 3 v3 v1 v4 v6 1 5 6 3 2 2 2 （b） v5 v2 v3 3.3 2.2 10.5 v1 vs v4 1.0