运筹学基础及应用第6章-图与网络分析.ppt

树与图的最小树 树：无圈的连通图即为树 性质1：任何树中必存在次为1的点。 性质2：n 个顶点的树必有n-1 条边。 性质3：树中任意两个顶点之间，恰有且仅有一条链。 性质4：树连通，但去掉任一条边，必变为不连通。 性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。 v1 v2 v3 v4 v5 v6 树与图的最小树 图的最小部分树(支撑树) 如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝，一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。 v1 v2 v3 v4 v5 v1 v2 v3 v4 v5 G1 G2 求树的方法：破圈法和避圈法 最短路问题 问题描述： 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路 . 有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。 最短路问题 求最短路有两种算法: 狄克斯屈拉(Dijkstra)标号算法 逐次逼近算法 最短路问题 狄克斯屈拉(Dijkstra)标号算法的基本思路： 若序列{ vs,v1…..vn-1,vn }是从vs到vt间的最短路，则序列{ vs,v1…..vn-1 } 必为从vs 到vn-1的最短路。 假定v1→v2 →v3 →v4是v1 →v4的最短路，则v1 →v2 →v3一定是v1 →v3的最短路，v2 →v3 →v4也一定是v2 →v4的最短路。 v1 v2 v3 v4 v5 最短路问题 求网络图的最短路，设图的起点是vs,终点是vt ,以vi为起点vj为终点的弧记为 (i, j) 距离为dij P标号(点标号)：b(j) —起点vs到点vj的最短路长； T标号(边标号)： k(i,j)=b(i)+dij， 步骤： 1. 令起点的标号；b(s)＝0。 2. 找出所有vi已标号vj未标号的弧集合 B={(i, j)} 如果这样的弧不存在或vt已标号则计算结束； 3. 计算集合B中弧k(i，j)=b(i)+dij的标号 4. 选一个点标号 在终点vl处标号b(l), 返回到第2步。 最短路问题 例6.5 求下图v1到v7的最短路长及最短路线 ① ② ③ ④ ⑤ ⑥ ⑦ 8 5 2 5 2 3 5 3 4 2 10 5 7 0 8 5 2 2 5 4 4 11 14 7 5 10 7 11 P标号 T标号 9 最短路问题 v1到v7的最短路长及最短路线如图所示： ① ② ③ ④ ⑤ ⑥ ⑦ 8 6 2 5 2 3 5 3 4 2 10 5 7 v7已标号，计算结束。从v1到v7的最短路长是 11, 最短路线： v1→ v4 → v6 → v7 0 2 4 11 最短路问题 从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj 。 注：无向图最短路的求法只将上述步骤2将弧改成边即可。 最短路问题 例6.6 求下图v1到各点的最短距离及最短路线。 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 4 5 2 6 1 7 8 3 9 3 2 6 12 16 18 0 4 5 2 2 3 10 3 9 6 12 6 4 11 6 6 18 8 12 24 8 24 18 最短路问题 v1到各点的最短距离及最短路线如图所示： ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 4 5 2 6 1 7 8 3 9 3 2 6 12 16 18 0 2 6 18 所有点都已标号，点上的标号就是v1到该点的最短距离，最短路线就是红色的链。 最大流问题 如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。 基本概念： 1. 容量网络：对网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为vs)和一个收点(也称汇点，记为vt)，网络中其他点称为中间点。 vs ① ② ③ ④ vt 4 8 4 4 1 2 2 6 7 9 最大流问题 2. 网络的最大流 是指网络中从发点到收点之间允许通过的最大流量。 3. 流与可行流 流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的载量记为fij。若fij=0，称为零流。 满足以下条件的一组流称为可行流。 容量限制条件。容量网络上所有的弧满足：0≤fij≤cij 中间点平衡条