第十一章图与网络分析2.ppt
《第十一章图与网络分析2.ppt》由会员分享,可在线阅读,更多相关《第十一章图与网络分析2.ppt(110页珍藏版)》请在三一文库上搜索。
1、第十一章 图与网络分析,Graph theory and network analysis,第十一章 图与网络分析,11.1 引言 11.2 图与网络的基本概念 11.3 最短路问题 11.4 最小生成树问题 11.5 最大流问题,11.5 最大流问题,最大流问题是一类应用极为广泛的问题, 例如 交通运输网络中有人流、车流、物流, 供水网络中有水流; 金融系统中有现金流; 通讯系统中有信息流。 50年代福特(Ford)和富克逊(Fulkerson)建立的“网络流理论”,是网络应用的重要组成部分。,11.5 最大流问题,11.5 最大流问题,11.5 最大流问题,什么是最大流问题?,11.5 最
2、大流问题,什么是最大流问题?,假设图为输油网络, Vs为起点,Vt为终点,V2 , V3 , V4 , V5为中转站, 边上的数表示该管道的最大输油能力, 问该如何安排各管道输油量能使从Vs到Vt的总运输量最大? 管道网络中的每边的最大通过能力即容量是有限的, 实际流量也并不一定等于容量, 上述问题就是讨论如何充分利用装置的能力。,11.5 最大流问题,最大流问题有关概念,定义: 设有向连通图 G = (V, E), G 的每条边 (vi, vj ) 上有非负数 cij 称为边的容量, 仅有一个入次为0的点 vs 称为发点(源), 一个出次为0的点 vt 称为收点(汇), 其余点为中间点, 这
3、样的网络G称为容量网络, 常记做G=(V, E , C).,11.5 最大流问题,最大流问题有关概念,11.5 最大流问题,最大流问题有关概念,V5,定义: 对任一 G 中的边 ( vi, vj ) 有流量 fij , 称集合f = fij 为网络G上的一个流;称满足下列条件的流f 为可行流: (1)容量限制条件: 对 G 中每条边 (vi, vj ) ,有 0 fij cij (2)平衡条件: 对中间点vi ,有 fij fki (即从中间点vi的物资输入量与输出量相等) 对收发点 vs, vt 有 fsj fti = W (W为网络的总流量) (即从vs点出发的物资总量等于vt点输入的物资
4、总量),11.5 最大流问题,最大流问题有关概念,可行流总是存在的, 例如 f = 0 就是一个流量为0 的可行流。 最大流问题 在容量网络中,寻找流量最大的可行流。 饱和与不饱和 一个流 f = fij ,当fijcij,则称流 f 对边 (vi, vj) 是饱和的,否则称f 对边 (vi, vj) 不饱和。,11.5 最大流问题,最大流问题有关概念,11.5 最大流问题,最大流问题有关概念,最大流问题实际是个线性规划问题,但利用它与图的紧密关系,能更为直观简便地求解。,定义: 对任一 G 中的边 (vi, vj) 有流量 fij , 称集合f =fij 为网络G 上的一个流;称满足下列条件
5、的流 f 为可行流: (1)容量限制条件: 对 G 中每条边 (vi, vj ) ,有 0 fij cij (2)平衡条件: 对中间点vi ,有 fij fki (即从中间点vi的物资输入量与输出量相等) 对收发点 vs, vt 有 fsj fti = W (W为网络的总流量) (即从vs点出发的物资总量等于vt点输入的物资总量),11.5 最大流问题,最大流问题有关概念,V7,约束条件: (1)容量限制条件: fij cij (i= 1,2,3,4,5,6, j =2,3,4,5,6,7 ) 0 fij (i= 1,2,3,4,5,6, j =2,3,4,5,6,7 ),V5,定义: 对任一
6、 G 中的边 (vi, vj) 有流量 fij , 称集合f =fij 为网络G 上的一个流;称满足下列条件的流f 为可行流: (1)容量限制条件: 对 G 中每条边 (vi, vj ) ,有 0 fij cij (2)平衡条件: 对中间点vi ,有 fij fki (即从中间点vi的物资输入量与输出量相等) 对收发点 vs, vt 有 fsj fti = W (W为网络的总流量) (即从vs点出发的物资总量等于vt点输入的物资总量),11.5 最大流问题,最大流问题有关概念,V7,约束条件: (2)平衡条件: f12 = f23 f25 (V2),V5,V7,约束条件: (2)平衡条件: f
7、12 = f23 f25 (V2),V5,V7,约束条件: (2)平衡条件: f12 = f23 f25 (V2),V5,V7,6,3,5,2,2,2,4,1,2,6,3,V1,V2,V4,V3,V6,约束条件: (2)平衡条件: f12 = f23 f25 (V2),V5,V7,6,3,5,2,2,2,4,1,2,6,3,V1,V2,V4,V3,V6,约束条件: (2)平衡条件: f12 = f23 f25 (V2) f23 f43 = f34 f35 (V3),V5,V7,约束条件: (2)平衡条件: f12 = f23 f25 (V2) f23 f43 = f34 f35 (V3),V5
8、,V7,约束条件: (2)平衡条件: f12 = f23 f25 (V2) f23 f43 = f34 f35 (V3) f14 = f43 f46 f47 (V4),V5,V7,约束条件: (2)平衡条件: f12 = f23 f25 (V2) f23 f43 = f34 f35 (V3) f14 = f43 f46 f47 (V4),V5,V7,6,3,5,2,2,2,4,1,2,6,3,V1,V2,V4,V3,V6,约束条件: (2)平衡条件: f12 = f23 f25 (V2) f23 f43 = f34 f35 (V3) f14 = f43 f46 f47 (V4),f25 f35
9、 = f57 (V5),V5,V7,约束条件: (2)平衡条件: f12 = f23 f25 (V2) f23 f43 = f34 f35 (V3) f14 = f43 f46 f47 (V4),V5,f25 f35 = f57 (V5),V7,6,3,5,2,2,2,4,1,2,6,3,V1,V2,V4,V3,V6,约束条件: (2)平衡条件: f12 = f23 f25 (V2) f23 f43 = f34 f35 (V3) f14 = f43 f46 f47 (V4),V5,f25 f35 = f57 (V5) f36 f46 = f67 (V6),定义: 对任一 G 中的边 (vi,
10、vj) 有流量 fij , 称集合f =fij 为网络G 上的一个流;称满足下列条件的流f 为可行流: (1)容量限制条件: 对 G 中每条边 (vi, vj ) ,有 0 fij cij (2)平衡条件: 对中间点vi ,有 fij fki (即从中间点vi的物资输入量与输出量相等) 对收发点 vs, vt 有 fsj fti = W (W为网络的总流量) (即从vs点出发的物资总量等于vt点输入的物资总量),11.5 最大流问题,最大流问题有关概念,V7,约束条件: (2)平衡条件: f12 = f23 f25 (V2) f23 f43 = f34 f35 (V3) f14 = f43 f
11、46 f47 (V4),V5,f25 f35 = f57 (V5) f36 f46 = f67 (V6),V7,6,3,5,2,2,2,4,1,2,6,3,V1,V2,V4,V3,V6,约束条件: (2)平衡条件: f12 = f23 f25 (V2) f23 f43 = f34 f35 (V3) f14 = f43 f46 f47 (V4),V5,f25 f35 = f57 (V5) f36 f46 = f67 (V6) f47 f57 f67 = f12 f14 (W),11.5 最大流问题,最大流问题有关概念,目标函数 max f12 f14 约束条件 fij cij (i= 1,2,3
12、,4,5,6, j =2,3,4,5,6,7 ) 0 fij (i= 1,2,3,4,5,6, j =2,3,4,5,6,7 ) f12 = f23 f25 (V2) f23 f43 = f34 f35 (V3) f14 = f43 f46 f47 (V4) f25 f35 = f57 (V5) f36 f46 = f67 (V6) f47 f57 f67 = f12 f14 (W),11.5 最大流问题,最大流的标号算法 设已有一个可行流 f,标号的方法可分为两步 第一步是标号过程,通过标号来寻找可增广链; 第二步是调整过程,沿可增广链调整 f 以增加流量。,11.5 最大流问题,可增广链:
13、 容量网路G, 若u为网络中从Vs(发点)到Vt(收点)的一条链, 给u定向为从Vs到Vt,u上的边凡与u同向称为向前边, 凡于u反向的称为向后边,其集合分别用u+和u-表示, f 是一个可行流,如果满足 0 fij cij (vi, vj ) u+ 0 fij cij (vi, vj ) u- 则称u为从Vs到Vt的(关于f的)可增广链。,11.5 最大流问题,图为一个网络及初始可行流,每条边上的有序数表示( cij , fij ),求最大流。,(3,0),11.5 最大流问题,图为一个网络及初始可行流,每条边上的有序数表示( cij , fij ),求最大流。,(3,0),定义: 对任一
14、G 中的边 (vi, vj) 有流量 fij , 称集合f =fij 为网络G 上的一个流;称满足下列条件的流f 为可行流: (1)容量限制条件: 对 G 中每条边 (vi, vj ) ,有 0 fij cij (2)平衡条件: 对中间点vi ,有 fij fki (即从中间点vi的物资输入量与输出量相等) 对收发点 vs, vt 有 fsj fti = W (W为网络的总流量) (即从vs点出发的物资总量等于vt点输入的物资总量),11.5 最大流问题,最大流问题有关概念,11.5 最大流问题,图为一个网络及初始可行流,每条边上的有序数表示( cij , fij ),求最大流。,(3,0),
15、11.5 最大流问题,可增广链: 容量网路G, 若u为网络中从Vs(发点)到Vt(收点)的一条链, 给u定向为从Vs到Vt,u上的边凡与u同向称为前向边, 凡于u反向的称为后向边,其集合分别用u+和u-表示, f 是一个可行流,如果满足 0 fij cij (vi, vj ) u+ (前向边不饱和) 0 fij cij (vi, vj ) u- (后向边不为零) 则称u为从Vs到Vt的(关于f的)可增广链。,11.5 最大流问题,Vt,(5,5),Vs,V1,V3,V6,V2,V5,V4,(5,2),(3,3),(4,2),(3,3),(5,4),(2,2),(2,2),(3,2),(4,2)
16、,图为一个网络及初始可行流,每条边上的有序数表示( cij , fij ),求最大流。,(3,0),Vt,(5,5),Vs,V1,V3,V6,V2,V5,V4,(5,2),(3,3),(4,2),(3,3),(5,4),(2,2),(2,2),(3,2),(4,2),(3,0),若u为网络中从Vs(发点)到Vt(收点)的一条链, 0 fij cij (vi, vj ) u+ (前向边不饱和) 0 fij cij (vi, vj ) u- (后向边不为零) 则称u为从Vs到Vt的(关于f的)可增广链。,Vt,(5,5),Vs,V1,V3,V6,V2,V5,V4,(5,2),(3,3),(4,2)
17、,(3,3),(5,4),(2,2),(2,2),(3,2),(4,2),(3,0),若u为网络中从Vs(发点)到Vt(收点)的一条链, 0 fij cij (vi, vj ) u+ (向前边不饱和) 0 fij cij (vi, vj ) u- (向后边不为零) 则称u为从Vs到Vt的(关于f的)可增广链。,Vt,(5,5),Vs,V1,V3,V6,V2,V5,V4,(5,2),(3,3),(4,2),(3,3),(5,4),(2,2),(2,2),(3,2),(4,2),(3,0),若u为网络中从Vs(发点)到Vt(收点)的一条链, 0 fij cij (vi, vj ) u+ (向前边不
18、饱和) 0 fij cij (vi, vj ) u- (向后边不为零) 则称u为从Vs到Vt的(关于f的)可增广链。,可增广链的实际意义是: 沿着这条链从Vs(发点)到Vt输送的流,还有潜力可挖, 可以经过调整,将流量提高, 调整后的流,在各点仍然满足平衡条件及容量限制,11.5 最大流问题,最大流的标号算法 设已有一个可行流 f,标号的方法可分为两步 第一步是标号过程,通过标号来寻找可增广链; 第二步是调整过程,沿可增广链调整 f 以增加流量。,11.5 最大流问题,最大流的标号算法 1. 标号过程 (1)给发点以标号(,+) (2)选择边一个已标号的顶点Vi, 对于Vi的所有未给标号的相邻
19、点Vj 按下列规则处理: a) 若边(vj, vi) E,且fji 0 则令 j = min( fji, i ) 并给vj标号(- vi , j ) 反向非零弧 b) 若边(vi, vj) E,且fij cij 则令 j = min( cij -fij, i ) 并给vj标号(+ vi , j ) 正向非饱和弧 重复(2)直到收点Vt 被标号或不再有顶点可标号为止。,11.5 最大流问题,最大流的标号算法 如若Vt得到标号,说明存在一条可增广链, 进行调整,反之计算结束。 2. 调整过程 (1)若(vi, vj) 是可增广链上的前向边, 则f ij = fij + t 若(vi, vj) 是可
20、增广链上的后向边, 则f ij = fij - t 若(vi, vj) 不在可增广链上,则f ij = fij (2)去掉所有标号,回到第1步,11.5 最大流问题,11.5 最大流问题,最大流的标号算法 1. 标号过程 (1)给发点以标号(,+) (2)选择边一个已标号的顶点Vi, 对于Vi的所有未给标号的相邻点Vj 按下列规则处理: a) 若边(vj, vi) E,且fji 0 则令 j = min( fji, i ) 并给vj标号(- vi , j ) b) 若边(vi, vj) E,且fij cij 则令 j = min( cij -fij, i ) 并给vj标号(+ vi , j )
21、 重复(2)直到收点Vt 被标号或不再有顶点可标号为止。,,+,(3,0),11.5 最大流问题,最大流的标号算法 1. 标号过程 (1)给发点以标号(,+) (2)选择边一个已标号的顶点Vi, 对于Vi的所有未给标号的相邻点Vj 按下列规则处理: a) 若边(vj, vi) E,且fji 0 则令 j = min( fji, i ) 并给vj标号(- vi , j ) b) 若边(vi, vj) E,且fij cij 则令 j = min( cij -fij, i ) 并给vj标号(+ vi , j ) 正向非饱和弧 重复(2)直到收点Vt 被标号或不再有顶点可标号为止。,,+,(3,0),
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第十一 网络分析
链接地址:https://www.31doc.com/p-2529861.html