网路的最大流和最小截.ppt
《网路的最大流和最小截.ppt》由会员分享,可在线阅读,更多相关《网路的最大流和最小截.ppt(11页珍藏版)》请在三一文库上搜索。
1、1,6.4 网路的最大流和最小截,6.4.1 网路的最大流的概念 网路流一般在有向图上讨论 定义网路上支路的容量为其最大通过能力,记为 cij ,支路上的实际流量记为 fij 图中规定一个发点s,一个收点t 节点没有容量限制,流在节点不会存储 容量限制条件:0 fij cij 平衡条件:,满足上述条件的网路流称为可行流,总存在最大可行流 当支路上 fij = cij ,称为饱和弧 最大流问题也是一个线性规划问题,2,6.4.2 截集与截集容量,定义:把网路分割为两个成分的弧的最小集合,其中一 个成分包含 s 点,另一个包含 t 点 。 一般包含 s 点的成分中的节点集合用V表示,包含 t 点的
2、成分中的节点集合用V表示 截集容量是指截集中正向弧的容量之和,福特-富克森定理:网路的最大流等于最小截集容量,3,6.4.3 确定网路最大流的标号法,从任一个初始可行流出发,如 0 流 基本算法:找一条从 s 到 t 点的增广链(augmenting path) 若在当前可行流下找不到增广链,则已得到最大流 增广链中与 s 到 t 方向一致的弧称为前向弧,反之后向弧,增广过程:前向弧 fij=fij +q , 后向弧 fij=fij q 增广后仍是可行流,4,最大流最小截的标号法步骤,第一步:标号过程,找一条增广链 1、给源点 s 标号s+,q(s)=,表示从 s 点有无限流出潜力 2、找出与
3、已标号节点 i 相邻的所有未标号节点 j,若 (1) (i, j)是前向弧且饱和,则节点 j 不标号; (2) (i, j)是前向弧且未饱和,则节点 j 标号为i+,q(j),表示从节点 i 正向流出,可增广 q(j)=minq(i), cijfij ; (3) (j, i)是后向弧,若 fji=0,则节点 j 不标号; (4) (j, i)是后向弧,若 fji0,则节点 j 标号为i,q(j),表示从节点 j 流向 i,可增广 q(j)=minq(i), fji ; 3、重复步骤 2,可能出现两种情况: (1) 节点 t 尚未标号,但无法继续标记,说明网路中已不存在增广链,当前流 v(f)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 网路 最大 最小
链接地址:https://www.31doc.com/p-2093933.html