图论与网络模型一,图论与网络介绍二,网络最大流问题一、图的基本概念
1.关系图,表示若干事物之间具有的某种关系的图,
例,若有 A,B,C,D,E五个人,他们之间相互认识的情况为,A与 C,D,E认识 ;B与 C,E认识 ;C与 A、
D认识 ;D与 A,C,E认识 ;E与 A,B,D认识,
我们用 点 分别表示 人,相互 认识 用 线 连接,就得到下面的图,
A ° ° B
° CE °
D °
2,图 是由若干个点和连线构成的,记为,
G = (V,E)
其中,V----点集 ; E----边集,
点 v 称为顶点 ; 连线 e 称为边 (或弧 ).
例,哥尼斯堡七桥问题 (从某点出发,经过七座桥各一次后回到起点 )
A
B
C
D
° A
B°
C°
D °
若两个点 v1,v2 有边 e 连接,则称 e与 v1,v2 是关联的 ;
若两条边 e1,e2 有公共顶点 v,则称 e1,e2 是相邻的,
3.点的度 ---- 与点 v关联的边的条数,记为 d (v)
奇点 ----度数为奇数的点偶点 ----度数为偶数的点结论,一个图中奇点的个数必为偶数,
4.连通图,在一个图中,若任何两个顶点之间至少有一条路线连接,则称这个图为连通图,
5,圈 Cn,一条封闭的路线称为圈,
6.完全图 Kn,n个点之间都有边相连的图,
如图,° °
K2
°
° °K3
° °
° °
K4
7.网络,当图的边 (弧 )有 方向,且各弧给予一定的 权 的图,
二、网络最大流问题最大流问题 就是在一定条件下,使网络系统中的某种流的流量达到最大的问题,
例如,公路系统中的 车辆流 ;水利系统中的 水流 ;电力系统中的 电流 ;服务系统中的 顾客流,信息系统中的 信息流 等等,
如图为某物资的运输网络,问从 vs到 vt的最大运输流量是多少? 弧线边的数字表示路线的容量,即该弧的能够容纳的最大流量,
1
vs
2
3
4
vt
9
5
3
4
3
5
2
7
6
1.基本概念,
(1)网络流,指在一定条件下流过一个网络的某种流在各弧上的流量的集合,
对一个网络 D=(V,A)
一定条件指,
(i)有一个起点 vs和终点 vt ;
(ii)流过网络的流量有一定的方向 ;
(iii)每一弧都有一个容量,表示容许通过该弧的最大流量,
(2)弧 (vi,vj)的容量记为 rij ;
(3)弧 (vi,vj)的流量记为 xij ;流 X={xij| (vi,vj)?A}
(4)可行流,满足下述条件的流 X={xij| (vi,vj)?A}称为可行流,
(i)弧的流量限制 0?xij?rij,(vi,vj)?A ;
(ii)中间点 vi 的平衡条件,
.,,0 tsixx
j jij ij
f=f(X) 表示可行流 X 从 vs 到 vt 的流量
ti
si
f
fxx
j
ji
j
ij?
当当
,
,
(5)最大流,在网络中,流量最大的可行流,
从 vi流出的总量流进 vi的总量最大流问题的数学模型
Avvrx
ti
tsi
si
f
f
xx
ts
f
jiijij
j
ji
j
ij
),(,0
,
,
,0
,
..
m a x
这是一个特殊的线性规划问题,由于它的特殊性,
用网络分析的方法求解比较方便,
1
vs
2
3
4
vt
(9,7)
(5,3)
(3,2)
(4,4)
(3,1)
(5,5)
(2,1)
(7,7)
(6,3)
前面问题的一个可行流,
vi vj(rij,xij)
f=10,是不是最大流呢?
(6)链的 前向弧 与 后向弧,设 P是网络中的一条从 vs到
vt的链,则 P上与链的方向一致的弧称为前向弧,记为
P+; P上与链方向相反的弧称为后向弧,记为 P -.
如在 P中
vs 1 4 3 vt(9,7) (3,1) (2,1) (6,3)
(7)增广链 (或可扩充链 ),设 X={xij}是可行流,P是从 vi到 vj的一条链,若 P上各弧的流量满足下述条件,
0,),()ii(;,),()i(
ijji
ijijji
xPvv
rxPvv
时当时当则称 P为一条关于可行流 X的增广链,
2.最大流定理调整量 },,m i n { 21
}),(m i n {1 Pvvxr jiijij?其中
}.),(m in {2 Pvvx jiij?
在网络 D=(V,A)中,对可行流 X,若不存在增广链,则此可行流为 最大流,
若存在增广链 P,则此可行流不是最大流,进行调整,可使流值增加,
3.求最大流的方法一,伴随增量网络法
2
Vs Vt
3
4
12
7 1
7
3
5
3
4
3
2 212
1 1
比如,还有标号法1
vs
2
3
4
vt
(9,7)
(5,3)
(3,2)
(4,4)
(3,1)
(5,5)
(2,1)
(7,7)
(6,3)
回到前面的例子
s 1 4 3 t
21
增广链 (也即是伴随增量网络中的路径 ):
2
Vs Vt
3
4
12
7 1
7
3
5
3
4
3
2 212
1 1
2 2 1 3
12 1
方案调整,在增广链的正向弧流量增加 θ,反向弧流量减少 θ,其他不变,
再次研究此网络流,发现不存在从起点到终点的路径,也即不存在增广链,见下页,
最大流量为 11.
1
vs
2
3
4
vt
(9,8)
(5,3)
(3,2)
(4,4)
(3,2)
(5,5)
(2,0)
(7,7)
(6,4)
2
Vs Vt
3
4
11
8 2
7
2
5
4
3
2 112
2
4
1
vs
2
3
4
vt
(9,8)
(5,3)
(3,2)
(4,4)
(3,2)
(5,5)
(2,0)
(7,7)
(6,4)
求下面网络的最大流,
s
1
2
3
4
5
t
13
9
4
5
5
6
5
5
4
4 10
9
给出初始可行流,
s
1
2
3
4
5
t
(13,9)
(9,9)
(4,0)
(5,5)
(5,4)
(6,4)
(5,5)
(5,4)
(4,0)
(4,4)
(10,9)
(9,9)
先给出伴随增量网络如下,
Vs 3
2
1
5
4
Vt
4
4
1
4
2
1
9
9 4
5
4
1
4
5
9
9
4
增广链,Vs 1 3 Vt
调整量,
2
调整后的网络如下,
s
1
2
3
4
5
t
(13,11)
(9,9)
(4,0) (5,4)
(6,6) (5,4)
(4,2)
(4,4)
(10,9)
(9,9)
(5,5)
(5,5)
其伴随增量网络如下,
Vs 3
2
1
5
4
Vt
2
2
1
4
1
9
9 4
5
4
1
6
5
11
9
4
2
结论,不存在从 Vs到 Vt的路径,即不存在增广链,因此此网络流即为最大流,但是最大流的网络并不唯一,还有其他的最大流,如
s
1
2
3
4
5
t
(13,11)
(9,9)
(4,0) (5,4)
(6,6) (5,2)
(4,4)
(4,4)
(10,9)
(9,7)
(5,5)
(5,5)
s
1
2
3
4
5
t
(13,11)
(9,9)
(4,0) (5,4)
(6,6) (5,3)
(4,3)
(4,4)
(10,9)
(9,8)
(5,5)
(5,5)
最大流之二最大流之三
6.最小费用最大流
.)(
),(
Aji ijij
xlXl
对运输网络而言,两个城市之间往往可以通过不同的道路运送同等的货物,但是我们感兴趣的是,哪一条道路的运费最低,这就是最小费用最大流问题,其数学描述为,
对网络 D=(V,A)的每一段弧 (Vi,Vj),除了容量 rij外,
还附加有一个非负的实数 lij,我们称之为费用,求从源到汇的最大网络流 X,同时使流 X的费用最小,
求最小费用最大流方法,每次都是求当前的最小费用流,从零流出发,设目前的流量为 f,
在构造的伴随增量网络中,定义一个新的费用,正向弧就是原来的费用,反向弧则为原来费用的相反数,从所有的从源到汇的路径中选出费用最小的路径,设其相应的流的调整量为 θ,则它是流量 f+ θ的最小费用流,继续下去,直到伴随网络中没有从源到汇的路径,即求得最小费用最大流,
1.关系图,表示若干事物之间具有的某种关系的图,
例,若有 A,B,C,D,E五个人,他们之间相互认识的情况为,A与 C,D,E认识 ;B与 C,E认识 ;C与 A、
D认识 ;D与 A,C,E认识 ;E与 A,B,D认识,
我们用 点 分别表示 人,相互 认识 用 线 连接,就得到下面的图,
A ° ° B
° CE °
D °
2,图 是由若干个点和连线构成的,记为,
G = (V,E)
其中,V----点集 ; E----边集,
点 v 称为顶点 ; 连线 e 称为边 (或弧 ).
例,哥尼斯堡七桥问题 (从某点出发,经过七座桥各一次后回到起点 )
A
B
C
D
° A
B°
C°
D °
若两个点 v1,v2 有边 e 连接,则称 e与 v1,v2 是关联的 ;
若两条边 e1,e2 有公共顶点 v,则称 e1,e2 是相邻的,
3.点的度 ---- 与点 v关联的边的条数,记为 d (v)
奇点 ----度数为奇数的点偶点 ----度数为偶数的点结论,一个图中奇点的个数必为偶数,
4.连通图,在一个图中,若任何两个顶点之间至少有一条路线连接,则称这个图为连通图,
5,圈 Cn,一条封闭的路线称为圈,
6.完全图 Kn,n个点之间都有边相连的图,
如图,° °
K2
°
° °K3
° °
° °
K4
7.网络,当图的边 (弧 )有 方向,且各弧给予一定的 权 的图,
二、网络最大流问题最大流问题 就是在一定条件下,使网络系统中的某种流的流量达到最大的问题,
例如,公路系统中的 车辆流 ;水利系统中的 水流 ;电力系统中的 电流 ;服务系统中的 顾客流,信息系统中的 信息流 等等,
如图为某物资的运输网络,问从 vs到 vt的最大运输流量是多少? 弧线边的数字表示路线的容量,即该弧的能够容纳的最大流量,
1
vs
2
3
4
vt
9
5
3
4
3
5
2
7
6
1.基本概念,
(1)网络流,指在一定条件下流过一个网络的某种流在各弧上的流量的集合,
对一个网络 D=(V,A)
一定条件指,
(i)有一个起点 vs和终点 vt ;
(ii)流过网络的流量有一定的方向 ;
(iii)每一弧都有一个容量,表示容许通过该弧的最大流量,
(2)弧 (vi,vj)的容量记为 rij ;
(3)弧 (vi,vj)的流量记为 xij ;流 X={xij| (vi,vj)?A}
(4)可行流,满足下述条件的流 X={xij| (vi,vj)?A}称为可行流,
(i)弧的流量限制 0?xij?rij,(vi,vj)?A ;
(ii)中间点 vi 的平衡条件,
.,,0 tsixx
j jij ij
f=f(X) 表示可行流 X 从 vs 到 vt 的流量
ti
si
f
fxx
j
ji
j
ij?
当当
,
,
(5)最大流,在网络中,流量最大的可行流,
从 vi流出的总量流进 vi的总量最大流问题的数学模型
Avvrx
ti
tsi
si
f
f
xx
ts
f
jiijij
j
ji
j
ij
),(,0
,
,
,0
,
..
m a x
这是一个特殊的线性规划问题,由于它的特殊性,
用网络分析的方法求解比较方便,
1
vs
2
3
4
vt
(9,7)
(5,3)
(3,2)
(4,4)
(3,1)
(5,5)
(2,1)
(7,7)
(6,3)
前面问题的一个可行流,
vi vj(rij,xij)
f=10,是不是最大流呢?
(6)链的 前向弧 与 后向弧,设 P是网络中的一条从 vs到
vt的链,则 P上与链的方向一致的弧称为前向弧,记为
P+; P上与链方向相反的弧称为后向弧,记为 P -.
如在 P中
vs 1 4 3 vt(9,7) (3,1) (2,1) (6,3)
(7)增广链 (或可扩充链 ),设 X={xij}是可行流,P是从 vi到 vj的一条链,若 P上各弧的流量满足下述条件,
0,),()ii(;,),()i(
ijji
ijijji
xPvv
rxPvv
时当时当则称 P为一条关于可行流 X的增广链,
2.最大流定理调整量 },,m i n { 21
}),(m i n {1 Pvvxr jiijij?其中
}.),(m in {2 Pvvx jiij?
在网络 D=(V,A)中,对可行流 X,若不存在增广链,则此可行流为 最大流,
若存在增广链 P,则此可行流不是最大流,进行调整,可使流值增加,
3.求最大流的方法一,伴随增量网络法
2
Vs Vt
3
4
12
7 1
7
3
5
3
4
3
2 212
1 1
比如,还有标号法1
vs
2
3
4
vt
(9,7)
(5,3)
(3,2)
(4,4)
(3,1)
(5,5)
(2,1)
(7,7)
(6,3)
回到前面的例子
s 1 4 3 t
21
增广链 (也即是伴随增量网络中的路径 ):
2
Vs Vt
3
4
12
7 1
7
3
5
3
4
3
2 212
1 1
2 2 1 3
12 1
方案调整,在增广链的正向弧流量增加 θ,反向弧流量减少 θ,其他不变,
再次研究此网络流,发现不存在从起点到终点的路径,也即不存在增广链,见下页,
最大流量为 11.
1
vs
2
3
4
vt
(9,8)
(5,3)
(3,2)
(4,4)
(3,2)
(5,5)
(2,0)
(7,7)
(6,4)
2
Vs Vt
3
4
11
8 2
7
2
5
4
3
2 112
2
4
1
vs
2
3
4
vt
(9,8)
(5,3)
(3,2)
(4,4)
(3,2)
(5,5)
(2,0)
(7,7)
(6,4)
求下面网络的最大流,
s
1
2
3
4
5
t
13
9
4
5
5
6
5
5
4
4 10
9
给出初始可行流,
s
1
2
3
4
5
t
(13,9)
(9,9)
(4,0)
(5,5)
(5,4)
(6,4)
(5,5)
(5,4)
(4,0)
(4,4)
(10,9)
(9,9)
先给出伴随增量网络如下,
Vs 3
2
1
5
4
Vt
4
4
1
4
2
1
9
9 4
5
4
1
4
5
9
9
4
增广链,Vs 1 3 Vt
调整量,
2
调整后的网络如下,
s
1
2
3
4
5
t
(13,11)
(9,9)
(4,0) (5,4)
(6,6) (5,4)
(4,2)
(4,4)
(10,9)
(9,9)
(5,5)
(5,5)
其伴随增量网络如下,
Vs 3
2
1
5
4
Vt
2
2
1
4
1
9
9 4
5
4
1
6
5
11
9
4
2
结论,不存在从 Vs到 Vt的路径,即不存在增广链,因此此网络流即为最大流,但是最大流的网络并不唯一,还有其他的最大流,如
s
1
2
3
4
5
t
(13,11)
(9,9)
(4,0) (5,4)
(6,6) (5,2)
(4,4)
(4,4)
(10,9)
(9,7)
(5,5)
(5,5)
s
1
2
3
4
5
t
(13,11)
(9,9)
(4,0) (5,4)
(6,6) (5,3)
(4,3)
(4,4)
(10,9)
(9,8)
(5,5)
(5,5)
最大流之二最大流之三
6.最小费用最大流
.)(
),(
Aji ijij
xlXl
对运输网络而言,两个城市之间往往可以通过不同的道路运送同等的货物,但是我们感兴趣的是,哪一条道路的运费最低,这就是最小费用最大流问题,其数学描述为,
对网络 D=(V,A)的每一段弧 (Vi,Vj),除了容量 rij外,
还附加有一个非负的实数 lij,我们称之为费用,求从源到汇的最大网络流 X,同时使流 X的费用最小,
求最小费用最大流方法,每次都是求当前的最小费用流,从零流出发,设目前的流量为 f,
在构造的伴随增量网络中,定义一个新的费用,正向弧就是原来的费用,反向弧则为原来费用的相反数,从所有的从源到汇的路径中选出费用最小的路径,设其相应的流的调整量为 θ,则它是流量 f+ θ的最小费用流,继续下去,直到伴随网络中没有从源到汇的路径,即求得最小费用最大流,
