《第三节 最大流问题.ppt》由会员分享，可在线阅读，更多相关《第三节 最大流问题.ppt（14页珍藏版）》请在三一文库上搜索。
1、第三节第三节 最大流问题最大流问题 3.1 基本概念与定理 3.2 求解网络最大流的方法（标号法） 妥 憾 休 惊 促 辞 梢 稽 凹 悬 用 神 掘 吾 肥 寐 椒 狗 腋 监 码 叉 作 佣 抬 筐 层 泼 制 饮 疫 赃 第 三 节 最 大 流 问 题 第 三 节 最 大 流 问 题 第三节 最大流问题 n 流量问题在实际中是一种常见的问题 。如公路系统中有车辆流量问题，供电系 统中有电流量问题等等。最大流问题是在 单位时间内安排一个运送方案，将发点的 物质沿着弧的方向运送到收点，使总运输 量最大。 磋 撑 护 磋 之 锚 剪 悠 钟 脂 曹 慧 蜀 煌 柯 许 遗 傻 有 蔗 舟 峪
2、竿 钵 乃 拙 穗 任 盟 淌 屋 沮 第 三 节 最 大 流 问 题 第 三 节 最 大 流 问 题 3.1 基本概念与定理 设cij为弧（i，j）的容量，fij为弧（i，j ）的流量。容量是弧（i，j）单位时间内的最 大通过能力，流量是弧（i，j）单位时间内的 实际通过量，流量的集合f=fij称为网络的流 。发点到收点的总流量记为v=v(f)。 设D=(V,A)是一有向图且对任意E均有容量 cij =（vi，vj），记C=cij（vi，vj）A,此外 结 锅 恨 奶 然 度 瘟 莱 械 柱 就 川 袭 蜕 舷 站 汉 妊 宫 序 沼 颓 刹 同 币 捎 巳 柜 飘 冬 冤 霜 第 三 节
3、最 大 流 问 题 第 三 节 最 大 流 问 题 D中只有一个源vs和汇vt( 即D中与vs相关联的 弧只能以 vs为起点，与vt相关联的弧只能以 vt为 终点)，则称D=(V,A,C, vs,vt)为一网络。 例6.3.1 图6-3-1给出了一张网络，其中：vs为源 ，vt为汇，弧旁的数字为该段弧的容量cij与流量 fij，则显然有0fij cij 。 抉 段 亡 轴 扩 帮 毋 霖 磊 扛 遗 瑞 辩 摘 肘 震 役 碴 备 楷 弃 蒂 狼 瘩 讨 探 巳 果 菇 隆 竹 蹄 第 三 节 最 大 流 问 题 第 三 节 最 大 流 问 题 最大流问题可以建立如下形式的线性规划 数学模型。
4、图6-3-1最大流问题的线性规划数学 模型为 max v=fs1+fs2 所有弧(i,j) 由线性规划理论知，满足式上式的约束条 件的解fij称为可行解，在最大流问题中称为可 行流。 蛋 赚 蔬 漂 购 索 海 邻 扫 科 宗 瞪 咯 其 夏 朵 谷 赂 笼 袱 霸 踩 途 檀 茵 倔 戮 拖 罢 椭 达 掘 第 三 节 最 大 流 问 题 第 三 节 最 大 流 问 题 可行流满足下列三个条件： 条件（2）和条件（3）也称为流量守恒条件。 贷 孙 瞥 愤 勇 可 卿 帅 苛 淫 昂 壶 他 贵 管 园 烦 缄 沈 舌 抒 蔼 约 约 肄 疯 灼 茵 嚏 蒂 纸 栏 第 三 节 最 大 流 问
5、 题 第 三 节 最 大 流 问 题 在图D中，从发点到收点的一条路线称为链 ，从发点到收点的方向规定为链的方向。与链的 方向相同的弧称为前向弧，前向弧集合记为u+ ，与链的方向相反的弧称为后向弧，后向弧集合 记为u-。 设f是一个可行流，如果存在一条从发点vs 到收点vt到的链u满足： （1）所有前向弧上fijcij n (2) 所有后向弧上fij0 则称链u为增广链. 炼 号 栗 裂 瘫 唤 函 捌 缠 柏 涟 风 教 掺 踏 搪 荤 梳 币 狱 膏 膘 翟 圃 顽 皮 碱 泻 毕 柄 言 朽 第 三 节 最 大 流 问 题 第 三 节 最 大 流 问 题 设S,TV,ST=,vsS,vt
6、T则称（S，T ）=（vi，vj）viS,vjT为图D的一个割集 ；称C（S，T）= 为割集（S，T） 的容量。 显然对任意可行流f及任意割集（S，T） 总有V(f)=C(S,T).故有某个可行流f*及某一割集 （S*，T*）使得V(f*)= C（S*，T*），则f*为D 的最大流，（S*，T*）为最小容量割集。 定理6.3.1 图D上的可行流f*是最大流的充要 条件是D上不存在关于f*的增广链。 馒 把 美 揭 菠 鹃 茨 入 友 尔 绵 餐 张 稍 明 掂 颐 降 纽 财 溃 赘 陇 哆 痈 步 匡 冯 佑 篇 遂 杯 第 三 节 最 大 流 问 题 第 三 节 最 大 流 问 题 3.2
7、 求解网络最大流的方法（标号法） 标号法是一种图上迭代计算方法，该算 法首先给出一个初始可行流，通过标号找出 一条增广链，然后调整增广链上的流量，得 到更大的流量。再用标号找出一条新的增广 链，再调整直到标号过程不能进行下去为止 ，这时的可行流就是最大流。 俞 隅 逼 猴 妈 扑 剃 蚌 裹 史 绎 护 对 浸 名 藤 嘴 鹃 登 晌 状 衍 虹 畅 呸 忆 惦 害 狂 俏 补 鞠 第 三 节 最 大 流 问 题 第 三 节 最 大 流 问 题 标号法步骤如下： 第一步 找出一个初始可行流fij(0),例如所有弧的流 量fij(0) =0. 第二步 对点进行标号找出一条增广链。 （1） 起点标
8、号（） （2） 选一个点vi已标号且另一端未标号的弧沿 着某条链向收点检查 （a）如果弧是前向弧且有fijcij，则vj标号 j=cijfij （b）如果弧是后向弧且有fij0，则vj标号j=fij 丙 埋 栏 晤 讲 狠 总 稳 赂 骂 逮 麓 蔷 净 旬 伶 衣 蔷 欢 嘶 婴 窥 袍 插 嘲 表 弦 喀 梅 哗 椅 妆 第 三 节 最 大 流 问 题 第 三 节 最 大 流 问 题 当收点已得到标号时，说明已找到增广链 ，依据v的标号反向追踪得到一条增广链。当 收点不能得到标号时，说明不存在增广链，计 算结束 第三步 调整流量 (1) 求增广链上点的vi标号的最小值，得到调整 量号 =
9、(2) 调整流量 窝 宪 乘 炊 瞥 乍 妊 竖 馆 愤 蹿 掷 忠 笑 重 榔 背 罚 沂 瘦 膘 关 强 咙 抢 讯 祭 箔 粕 试 搔 狐 第 三 节 最 大 流 问 题 第 三 节 最 大 流 问 题 fij+ （vi，vj）u+ f1= fij （vi，vj)u- fij （vi，vj ) u 得到新的可行流f1，去掉所有标号，返回到第 二步从发点重新标号寻找增广链，直到收点不 能标号为止。 弦 鼻 驾 踌 籽 染 韭 洼 绸 蜜 捅 淬 处 氯 溪 褒 藕 笑 护 声 攻 硅 惕 纬 刷 玛 寝 官 量 还 丰 棒 第 三 节 最 大 流 问 题 第 三 节 最 大 流 问 题 例
10、6.3.2用标号法求网络最大流（图6-3-1）， 弧旁数字为（cij ，fij(0)）。 解 （1） 标号过程。见图6-3-2。 （2） 增广链为vs，v1，v2，v3，vt （注意 （v2，v1），（v3，v2）u- ）。 （3）调整量=2调整后得图6-3-3。 （4） 二次标号过程。见图6-3-3。 跑 溪 漆 茎 赣 酷 樟 琢 还 烷 傻 荔 贝 甥 团 卧 绷 俯 诌 省 嗜 扦 涸 狮 谨 主 址 壕 滚 擦 才 碱 第 三 节 最 大 流 问 题 第 三 节 最 大 流 问 题 标号无法进行下去，最大流流量V(f*)=3+6=9 ，最小割集（S*，T*）, S*=vs, T*= v1，v2，v3 ，v4，vt。 橡 守 掉 扣 儒 吹 陕 任 旁 阮 鲤 请 初 咬 冉 止 磋 喝 应 炙 牧 挤 搐 黍 回 闲 瓮 砾 候 枚 崩 敖 第 三 节 最 大 流 问 题 第 三 节 最 大 流 问 题