[理学]第7章网络分析_3.ppt

第7章 图与网络分析 Floyed 算法 适用范围：求网络上任意两点间的最短路 7.4 最大流问题 交通运输网络：车流，货物流 供水网络：水流 金融系统：现金流 通讯系统：信息流等 “网络流理论”——网络应用的重要组成部分 最大流有关概念 设有向联通图G=（V，E），G的每条边（vi，vj）上有非负数cij称为边的容量，仅有一个入次为0的点vs 称为发点，一个出次为0的点vt称为收点，其余点为中间点，这样的网络G称为容量网络，常记作G={V，E，C} 最大流有关概念 2. 对任一G中的边（vi，vj）有流量fij ，称集合fij为网络G上的一个流。称满足下列条件的流f为可行流： （1）容量限制条件： 对G中每条边（vi，vj）有 0≤ fij ≤ cij 最大流有关概念 （2）平衡条件 对中间点vi： 对收、发点vs ，vt： 最大流有关概念 可行流总是存在的。f={0}—流量为0的可行流 最大流问题就是在容量网络中寻找流量最大的 可行流 3. 四 图的基本概念 最小支撑树 最短路问题 最大流问题 最小费用流 又称：距离矩阵幂乘法，通过定义一个网络权矩阵进行类似于矩阵的计算来求两点间最短路的一种算法 两点间走一步 到达的最短距离 D3 D1 两点间走两步 到达的最短距离 D2 两点间走三步 到达的最短距离 容量 流量 （从vs点发出的物资总量等于vt点输入的量 且等于网络总流量） （中间点vi的物资输出量与输入量相等） 4. 增广链 二 流出未饱弧，令θj=min(cij-fij,θi)，并给vj标号(θ j，vi) 流入非零弧，令θj=min(fji,θi)，并给vj标号(θ j,-vi) 对于vi： 流出未饱弧，令θj=min(cij-fij,θi)，并给vj标号（ θ j，vi） 流入非零弧，令θj=min(fji,θi)，并给vj标号（ θ j,-vi） 流出未饱弧，令θj=min(cij-fij,θi)，并给vj标号（ θ j，vi） 流入非零弧，令θj=min(fji,θi)，并给vj标号（ θ j,-vi） 流出未饱弧，令θj=min(cij-fij,θi)，并给vj标号（ θ j，vi） 流入非零弧，令θj=min(fji,θi)，并给vj标号（ θ j,-vi） 流出未饱弧，令θj=min(cij-fij,θi)，并给vj标号（ θ j，vi） 流入非零弧，令θj=min(fji,θi)，并给vj标号（ θ j,-vi） 调整方案2 0 2 三