05-2图与网络分析(5)

10
网络流
网络流：容量网络中，实际流过各弧的 流量集F={fij}
11
可行流 及其满足条件（1） ）
在容量网络上满足容量限制条件和中间 点平衡条件的一组流为可行流 可行流 容量限制条件：对所有弧有 容量限制条件
0 ≤ f (vi , v j ) ≤ c (vi , v j )
12
可行流 及其满足条件（2） ）
7
流、弧流量
流/弧流量：是指实际通过网络各条弧上 弧流量： 弧流量 的流量/负载量，或软件能力。 对加在弧（vi,vj）上的负载量记作f(vi,vj)， 或简写为fij， 如f13=4， f23 =0（ c13 =9， c23 =2 ）。 若网络上所有的fij=0，这个流称为零流 零流。 零流
8
容量网络
对网络流的研究是在容量网络上进行的。
容量网络是指对网络上的每条弧(vi，vj)都 容量网络 给出一个最大的通过能力 或标有弧容量cij的网络。
9
容量网络的发点、 容量网络的发点、收点与中间点
在容量网络中通常规定一个发点 发点(也称源点， 发点 记为s)和一个收点 收点(也称汇点，记为t)， 收点 网络中既非发点又非收点的点称为中间点 中间点
(V , V ) = {(s,2), (1,2), (3,2), (3, t )} c( V, V) = 19
27
(V , V ) = {(s,1), (4,3), (4, t )} c( V, V) = 24
(V , V ) = {(2,4), (3, t )} c( V, V) = 14
(V , V ) = {(1,3), ( 4,3), (4, t )} c( V, V) = 25
( i , j )∈(V ,V )
∑
( i , j )∈(V ,V )
根据前面定义：υ*(f) = f *(V,V ) − f *( V ,V) = c(V,V ) ≥ c*(V,V ) 又因为 υ* (f) = f * (V,V ) − f * ( V ,V) ≤ c* (V,V ) 所以：网络最大流=网络最小割的容量
32
υ (f) = c (V,V )
* *
5.4
求网络最大流的标号算法
实质： 实质： 是判断有否增广链存在 并设法把增广链找出来
33
标号算法的步骤 第 1步 首先给发点s标号(0，ε(s))。 括弧中第一个数字 第一个数字是使这个点得到标号的 第一个数字 前一个点的代号，因s是发点，故记为0。 括弧中第二个数字 第二个数字ε(s)表示从上一标号点 第二个数字 到这个标号点的流量的最大允许调整值。 s为发点，不限允许调整量，故ε(s)=∞。
24
割的容量
割的容量： 割的容量：是组成它的集合中的各弧的 容量之和，用c(V, V )表示。
c(V ,V ) =
∑
c(vi , v j )
( i , j )∈(V ,V )
25
网络图的全部割
V s s, v1 s, v2 s, v1, v2 s, v1, v3 s, v2, v4 s, v1, v2, v3 s, v1, v2, v4 s, v1, v2, v3, v4
令
fi + θ f ′ = fi − θ f i
对所有µ + 对所有µ − 对非增广链上的弧
显然f仍是一个可行流，但较之原来的可 行流f，这时网络中从s→t的流量增大了 一个θ值（θ>0）。 因此只有当网络图中找不到增广链时， 因此只有当网络图中找不到增广链时， s→t 的流才不可能进一步增大 的流才不可能进一步增大。
第三步 重复第二步
可能出现两种结局 ① 标号过程中断，t得不到标号，说明该网络 中不存在增广链，给定的流量即为最大流。 记已标号点集合为 ，（V， ）为网 V 络的最小割； V ② t得到标号，这时可用反向追踪法在网络中 找出一条从s→t的由标号点及相应的弧连 接而成的增广链
36
第4步：修改流量
16
前向弧、 前向弧、后向弧
给出网络{cij,fij} 前向弧/正向弧 正向弧： 前向弧 正向弧：网络中所有指向为s→t 的弧，记作µ+； 后向弧/反向弧 反向弧： 后向弧 反向弧：网络中所有指向为t→s 的弧，记作µ-。
17
增广链
一条从网络的发点到网络的收点的链， 在这条链上所有指向为s→t的弧（前向 前向 弧存在f<c；所有指向为t→s的弧（后向 后向 弧存在f>0。 或一条从网络的发点到网络的收点的链， 且所有前向弧都为非饱和弧 非饱和弧，所有后向 非饱和弧 弧都为非零弧 非零弧。 非零弧
V
v1 , v2 , v3 , v4 , t v2 , v3 , v4 , t v1 , v3 , v4 , t v3 , v4 , t v2 , v4 , t v1 , v3 , t v4 , t v3 , t t
割 (s, 1) (s, 2) (s, 2) (1, 2) (1, 3) (s, 1) (2, 4) (1, 3) (2, 4) (s, 2) (1, 3) (3, 2) (3, t) (s, 1) (4, 3) (4, t) (2, 4) (3, t) (1, 3) (4, 3) (4, t) (3, t) (4, t)
20
增广链的作用
前向非饱和弧允许增大流量，后向非零 弧允许减小流量以维持节点平衡（流入= 流出），在增广链上存在增大输送能力 的潜力，即沿增广链可以增大流量。 增广链作用： 增广链作用：判断网络可行流是否为网 络最大流。
21
5.2
割和流量
22
割
割是指将容量网络中的发点和收点分割开， 并使s→t的流中断的一组弧的集合。 如下图中，KK将网络上的点分割成V和 V t 两个集合，并有 s ∈ V ，∈V ，称弧的集合 (V ,V ) = {(v , v ), (v , v )}是一个割。
18
找出网络图中的增广链（ 找出网络图中的增广链（前向弧为非饱和 后向弧为非零弧） 弧，后向弧为非零弧）
4(3) 3(3) 1(1) 5(1) 2(1) 1(1) 3(0) 5(3)
19
2(2)
增广链存在时，定义
(ci − f i ), 对µ + θ = min fi , 对µ −
θ >0
29
c*(V,V )
υ*(f) = f *(V,V ) − f *( V ,V) ≤ c*(V,V )
网络图6-16中从s→t的最大流量不超过14单位
5.3
最大流最小割定理
标号法求 网络最大流的依据
30
定理2 定理2 最大流最小割定理
在网络中s→t 的最大流量等于它的最小 割集的容量，即
υ (f) = c (V,V )
求网络的最大流
求网络的最大流， 求网络的最大流，是指满足容量限制条 件和中间点平衡的条件下， 件和中间点平衡的条件下，使v(f)值达 值达 到最大。 到最大
v( f ) = ∑ f (vs , v j ) = ∑ f (v j , vt )
j j
显然这是一个线性规划问题。但由于网络的特殊性，我们可以 寻求比单纯形法要简单得多的方法来求解。增广链、最小割
3
5.1
网络最大流的有关基本概念
有向图与容量网络 流与可行流
4
ቤተ መጻሕፍቲ ባይዱ
有向图与弧
有向图：网络图中两点之间的连线有规 有向图 定方向 弧：有向图上有规定指向的连线。 弧的代号：(vi，vj)表明方向是从vi点指向 弧的代号 vj点。 有向图是点与弧的集合，记作D(V，A)
5
6
弧的容量
弧的容量： 弧的容量：网络的组成弧所具有的通过 能力，也称为硬件能力 能力 硬件能力 弧的容量记为：c(vi,vj) c(v )或简写为cij。 c 如c13 =9， c23 =2
34
第二步
列出与已标号点相邻的所有未标号点
① 考虑从标号点 出发的弧 从标号点i出发的弧 前向弧） 从标号点 出发的弧(i,j)（前向弧），若fij=cij，不 给点j标号；若fij<cij，则对点j标号，记为(i,ε(j))。括弧 中的i表示点j的标号是从点i延伸过来的， ε(j)=min{ε(i)， ε(j)=min{ε(i)，(cij-fij)} )}； ② 考虑所有指向标号点 的弧 指向标号点i的弧 后向弧） 指向标号点 的弧(h,i) （后向弧） ，如果有 fhi=0，对h点不标号；若有fhi>0，则对点h标号，记 为(i,ε(h))，其中ε(h)=min{ε(i)，fhj}； ③ 如果某未标号点k有两个以上相邻的标号点，为减少 迭代次数，可按①、 ②中所述规则分别计算出ε(k)的 35 值，并以其中最大的一个标记。
13
网络流量
若以v(f)表示网络中从s→t的流量，则有
v( f ) = ∑ f (vs , v j ) = ∑ f (v j , vt )
j j
14
网络最大流：使得从网络发点到收点的总 网络最大流 容量达到最大的可行流。
网络的最大流
图 6-15
15
网络的最大流是指网络中从发点到收点 网络的最大流 之间允许通过的最大流量。 对有多个发点和多个收点的网络，可以 另外虚设一个总发点和一个总收点，并 将其分别与各发点、收点连起来(见图615)，就可以转换为只含一个发点和一个 收点的网络
割的容量 15 21 17 18 19 24 14 25 15
26
(V , V ) = {(s,1), (s,2)} c( V, V) = 15
(V , V ) = {(s,2), (1,2), (1,3)} c( V, V) = 21
(V , V ) = {(s,1), (2,4)} c( V, V) = 17
* *
31
最大流最小割定理的证明