图与网络解析.ppt

天津理工大学经济与管理学院 天津理工大学经济与管理学院　李春发 图与网络分析 引 言 第一节 图与网络的基本概念 第二节 树 第三节 最短路径问题 第四节 网络最大流问题 第五节 最小费用最大流问题 引 言 第一节 图与网络的基本概念 第二节 树 第三节 最短路问题 7.4 网络最大流问题 第五节 最小费用最大流问题 推论 可行流f是最大流的充要条件是不存在从vs到vt的(关于f的)增广链. 证明: (略) 寻找最大流的方法是: 从一个可行流开始, 寻求关于这个可行流的增广链, 若存在,则可以经过调整, 得到一个新的可行流, 其流量比原来的可行流要大,重复这个过程, 直到不存在关于该流的增广链时就得到了最大流. 如果在一个网络中, 有多个发点或收点, 则可以将其变为只有一个发点和收点的网络.这只需增加一个新的总发点和一个新的总收点.从总发点到各个发点分别连接一条容量为+无穷大的弧, 从各个收点到总收点分别连接一条容量为+无穷大的弧. 这样就可将问题变为单发点和单收点的网络流问题. 所以, 以后只讨论一个发点和一个收点的网络流问题. 三、求最大流的标号算法 这里介绍计算网络最大流的简便方法: 标号法, 它是Ford —Fulkerson1956年提出,其原理是利用寻找增广链来不断改善可行流. 下面介绍的标号法, 就是一种通过有哪些信誉好的足球投注网站增广链,不断改进可行流, 直至求得最大流的方法. 在标号法中, 网络中的点可分为三类: 标了号且检查过的点; 标了号但未检查的点; 未标号点. 前两种都称为标号点, 对于标号点vj, 它的标号包含两部分内容, 第一部分指出vj的紧前点, 第二部分表示从vs到vj的可能调整量, 记为l(vj)= . 标号法从一个可行流f出发(若网络中没有给定f, 则可以设f是0流), 反复经过标号过程与调整过程来寻找最大流. 设{fij}为可行流, 标号方法分两步: 第1步是标号过程, 通过标号来寻求增广链;第2步是调整过程,沿增广链调整f以增加流量. (一) 标号过程 算法 3o 重复2o直到收点vt被标号或不再有顶点可标号为止. 若vt得到标号, 说明存在一条增广链, 转(二)调整过程. 若vt未获得标号,标号过程已无法进行时,说明f是最大流. (二) 调整过程 (2) 去掉所有标号, 回到第一步, 对行流 重新标号. 例 用标号法求下图的最大流.弧旁的数字是(cij,fij). v4 (1,1) (2,2) (3,0) (2,1) vs v1 v3 vt (4,3) v2 (1,1) (5,3) (3,3) (5,1) 解: (一) 标号过程 (0,+∞) (+vs,4) (3, 3) (1, 1) (1, 1) (4, 3) (2, 2) (3, 0) (5, 3) (2, 1) (5, 1) vs v2 v1 v3 v4 vt (1) 首先给vs标号(0, +∞) (2) 检查vs. 在(vs,v2)上, fs2=cs2=3, 是饱和弧,不满足标号条件. 在(vs,v1)上, fs1=1＜cs1=5, 满足标号条件, 则令 q1=min(cs1-fs1, qs)=min(5-1,+∞)=4 给v1以标号(+vs, 4). (0,+∞) (+vs,4) (3, 3) (1, 1) (1, 1) (4, 3) (2, 2) (3, 0) (5, 3) (2, 1) (5, 1) vs v2 v1 v3 v4 vt (-v1, 1) (3) 检查v1. 在弧上(v1,v3)上, f13=c13, 是饱和弧, 不满足标号条件. 在弧(v2,v1)上, f21=10, 满足标号条件.则令 q2=min(f21,q1)=min(1,4)=1 给v2以标号(-v1,1). 在弧(v3, v2)上, f32=10, 令q3＝min(1, 1)=1, 则给v3以标号(-v2,1). 　 (4) 检查v2. (相邻的未标号的点v4, v3.) 在弧(v2, v4)上, f24=3c24=4, 令 q4＝min(4-3, 1)=1, 则给v4以标号(+v2,1). (0,+∞) (+vs,4) (3, 3) (1, 1) (1, 1) (4, 3) (2, 2) (3, 0) (5, 3) (2, 1) (5, 1) vs v2 v1 v3 v4 vt (-v1, 1) (+v2, 1) (-v2, 1) 至此, 所有点都有了标号, 得到一条增广链(vs,v1,v2,v3,vt), 故转入调整过程.　 (5) 检查v3. 在弧(v3, vt)上, f3t=1c3