2012/12/2
1
第九章 网络
9.1 流
.
9.3 Menger 定理进阶
9.4 可行流
9.1 流
一个网络(Network)N是由一有向图(称
为基础有向图(underlying digraph);及
二特定的不相交顶点子集X和Y;以及弧集A
上定义的非负整数值函数c(⋅)(容量函数)。
X的每个顶点称为发点(source);
Y的每个顶点称为收点(sink);
I = V \ (X ∪ Y)中每个顶点称为中间顶点
(intermediate vertex);
每弧a上c(a)的值称为a的容量(capacity)。
例
x
1
v
1
1
1
6
3
4
5
1 2
2
x
2
v
3
v
2
v
4
y
2
3
2
5 3
4
4
6
3
流
定义在A(D)上的整数值函数f(·)若满足以下条
件,就称为网络N上的流(flow):
① 0 ≤ f(a) ≤ c(a) ,∀ a ∈ A(D) ,称为容量
约束(capacity constraint)。
② f+(v) = f -(v), ∀ v ∈ I ,称为守恒
条件(conservation condition)。
流的存在性,零流
记号
设f(.)为网络N上的任一流,对任一顶点子集
S,令: K=(S, ):
记:
S
(,)
() (,) (,);
uv S S
fS fSS fuv
S
SS
wz
+
∈
−
==
==
∑
(,)
()
()
() (, ) ({}, \{});
() ( ,) ( \{},{});
() ():
() ():
wz S S
wN v
wN v
vfvwfvVv
vfwvfVvv
fS fS S
valf f X f X f
+
−
∈
+
∈
−
∈
+−
+−
==
==
−
=−
∑
∑
流出 的合成流量;
的流值
最大流
流 f为最大流(maximum flow)⇔ 不存在流f‘,
使val f’ > valf 。
求最大流时考虑简化模型:
¾ 网络N
不
圈C,
得C
弧
的
量大于0;
¾ 网络N中不存在(xi,xj)-有向路P,使得P中每条弧
中的流量大于0;
¾ 只需讨论单发点,单收点的网络
评论0