2009-7-29
第二节 网络分析网络 ——赋权图，记 D=（ V,E,C）,其中 C={c1,…,cn}，
ci为边 ei上的权（设 ci ）。
网络分析主要内容 ——最小部分树、最短路、最大流。
0?
2009-7-29
一,最小部分（支撑）树问题问题：求网络 D的部分树，使其权和最小。
方法：避圈法 （ Kruskal,1956）,破圈法 (管梅谷,1975)。
例 2 求如图网络的最小部分树。
v5
v1 v3 v6
v4
v2
v7
2
5 5
2
33
5
7
5
71 1
2009-7-29
避圈法是一种选边的过程，其步骤如下：
1,从网络 D中任选一点 vi,找出与 vi相关联的权最小的边 [vi,vj],得第二个顶点 vj；
2,把顶点集 V分为互补的两部分 V1,1,其中V
集；不与已选边相关联的点，
，与已选边相关联的点集，
1
1
V
V
其中权最小的；
挑选其中考虑所有这样的边
,,],,[ 3,11 VvVvvv
。即，直至全部顶点属于重复 )(3 4,11VV
2009-7-29
用避圈法解例 2
v5
v1 v3 v6
v4
v2
v7
2
5 5
2
33
5
7
5
71 1
最小部分树如图上红线所示；
最小权和为 14。
思考：破圈法是怎样做的呢？
——见圈就破，去掉其中权最大的。
2009-7-29
最小部分树问题的应用例子已知有 A,B,C,D,E,F六 个城镇间的道路网络如图，现要在六个城镇间架设通讯网络（均沿道路架设），每段道路上的架设费用如图。求能保证各城镇均能通话且总架设费用最少的架设方案。
E
A
C
B
F
D
5
10
6
9
3
5
3
9
78 2
8
4
2009-7-29
二,最短路问题
1,问题：求网络 D中一定点 v1到其它点的最短路。
例 3 求如图网络中 v1至 v7的最短路，图中数字为两点间距离。
v5
v1 v3 v6
v4
v2
v7
2
5 5
2
33
5
7
5
71 1
2,方法：标号法 （ Dijkstra,1959）
给每点 vj标号 [dj,vi],其中 dj为 v1至 vj的最短距,vi为最短路上的前一点。
2009-7-29
标号法步骤：

。反向追踪可求出最短路即最短距，
，则）标上号，直至终点（本例即重复进行标号。的距最短（挑选其中与其中考虑所有这样的边未标号点集；
已标号点集，
分为互补的两部分把顶点集
，标号给
],[3 4.
)
,,],,[ 3.
:
:
2.
];[0 1.
7
77
1
11
1
1
11
d
vdv
vcdv
VvVvvv
V
V
V
vv
m i n?

2009-7-29
用标号法解例 3
v5
v1 v3 v6
v4
v2
v7
2
5 5
2
33
5
7
5
71 1
[0,v1]
[2,v1]
[3,v1]
其中 2=min{0+2,0+5,0+3}
其中 3=min{0+3,0+5,2+2,2+7}
[4,v2]
[7,v3]
[8,v5] [13,v6]
最短距为 13；
最短路为 v1-v2-v3-v5-v6-v7。
2009-7-29
最短路问题的应用例子某汽车公司正在制订 5年内购买汽车的计划 。
下面给出一辆新汽车的价格以及一辆汽车的使用维修费用 (万元 )：
年号 1 2 3 4 5
价格 2 2.1 2.3 2.4 2.6
汽车使用年龄 0–1 1–2 2–3 3–4 4–5
维修费用 0.7 1.1 1.5 2 2.5
试用网络分析中求最短路的方法确定公司可采用的最优策略 。
方法：以年号作顶点绘图，连线表示连续使用期间，以费用作路长。
2009-7-29
三,最大流问题
1,问题 已知网络 D=（ V,A,C）,其中 V为顶点集,A为弧集,C={cij}为容量集,cij 为弧（ vi,vj ）
上的容量。现 D上要通过一个流 f={fij},其中 fij 为弧
（ vi,vj ） 上的流量。问应如何安排流量 fij可使 D上通过的总流量 v最大？
例如：
v4v2
vs
v1
vt
v3
2
1
3
1
4
5
3
2
5
2009-7-29
2,数学模型
,,fvv ）上的流量各弧（决策变量：
)( fv M a x v?目标函数：




tifv
tsi
sifv
ff
cf
),(
,,0
),(
0
约束条件,（容量约束）
（平衡条件）
问题：最大流问题的决策变量、目标函数、约束条件各是什么？
2009-7-29
3,基本概念与定理
0
( 1 )
f
cf
c f
零流弧：
未饱和弧：
饱和弧：
弧按流量分为如：在前面例举的网络流问题中，若已给定一个可行流
（如括号中后一个数字所示），请指出相应的弧的类型。
v4v2
vs
v1
vt
v3（ 2,2）
（ 1,1）
（ 3,3）
（ 1,1）
（ 4,3）
（ 5,1）
（ 3,0）
（ 2,1）
（ 5,3）
2009-7-29
（ 2）可增值链（增广链）
一条可增值链。
的中关于可行流为，则称中弧皆非零中弧皆未饱若
，
中的反向弧集：
中的正向弧集：
，记的链至中由
fD
vvD


v4v2
vs
v1
vt
v3（ 2,2）
（ 1,1）
（ 3,3）
（ 1,1）
（ 4,3）
（ 5,1）
（ 3,0）
（ 2,1）
（ 5,3）
2009-7-29
（ 3） 截集与截量

）。的一个截集，记为（为
）（。称弧集使
，与分为二非空互补集截集（割集）：将
11
1111
11
,
,,,
VVD
VvVvvvVvVv
VVV

截量：截集上的容量和，记为 。 ），（ VVC
v4v2
vs
v1
vt
v3（ 2,2）
（ 1,1）
（ 3,3）
（ 1,1）
（ 4,3）
（ 5,1）
（ 3,0）
（ 2,1）
（ 5,3）
例 4 对于下图，若 V1={vs,v1},请指出相应的截集与截量。
2009-7-29
例 4 对于下图，若 V1={vs,v1},请指出相应的截集与截量。
解：
v4v2
vs
v1
vt
v3（ 2,2）
（ 1,1）
（ 3,3）
（ 1,1）
（ 4,3）
（ 5,1）
（ 3,0）
（ 2,1）
（ 5,3）
，）），（（）（,,,vvvvVV?
523,）（ VVC
2009-7-29
（ 4） 流量与截量的关系
）（）（）（）（,,,VVCVVfVVffv
截集上的流量和相应于截集的反向弧上流量和
）（）（,VVM in CfM a x v?
最大流最小割定理：
v4v2
vs
v1
vt
v3（ 2,2）
（ 1,1）
（ 3,3）
（ 1,1）
（ 4,3）
（ 5,1）
（ 3,0）
（ 2,1）
（ 5,3）
2009-7-29
4,解法
链）。调整的过程（调可增值的前接点；为为可增值上限，其中标号链）：给每点标号的过程（找可增值分两大步
vv
v
v
],,[
（ 5） 最大流的判别条件的可增值链。关于中不存在是最大流的充要条件是可行流
f
Df
2009-7-29

；
）为流入非零弧（，
）为流出未饱弧（
其中标流入非零弧，则给
）为流出未饱或或反之，若（
），其中）考虑所有这样的弧（（
未标号点集已标号点集分为）把顶点集（
标号）给（

jiiji
jiijiji
j
ijj
jij
iji
ss
vvf
vvfc
vv
vvVv
Vvvv
V
V
V
vv
,,m i n
,,,m i n
],,[
,
,,3;
:
:
2
];,[1
1
1
1
1
步骤：
2009-7-29


）；时得最小截集（
同可增值链，当前流即存在但进行不下去，说明不
），，转（追踪找出
，反向说明存在可增值链依此进行的结局
11
1
1
,
,
,
4
,
VV
f
V
V

）。后，转（得新流
，）（
，）（
，）（
令）调整：取（
1
m i n
f
vvf
vvf
vvf
f






,,
,,
,,
,4
2009-7-29
例 5 用标号法求下面网络的最大流。
解：第一次标号及所得可增值链如图，调量 =1，调后进行第二次标号如图。第二次标号未进行到底，得最大流如图，最大流量 v=5,同时得最小截
。）），（（）（ 31211,,,vvvvVV?
v4v2
vs
v1
vt
v3（ 2,2）
（ 1,1）
（ 3,3）
（ 1,1）
（ 4,3）
（ 5,1）
（ 3,0）
（ 2,1）
（ 5,3）
],[ sv?
],[ 2v1
],[ 2v1],[ 1v1
][4,sv
],[ 3v1
],[ sv?
][3,sv
2
0
2
0
2009-7-29
最大流问题的应用例子汽车由 A城通往 B城的可能的路线如下图所示 。 环境保护部门拟建立足够数量的汽车尾气检查站,以便使每辆汽车至少必须经过一个检查站 。 建立检查站的费用根据各路段的条件而有所不同 (如图上数字所示 )。 若求这个问题的最小费用解,可使用 模型 。
a,最短路模型； b.最大流模型； c.最小支撑树模型
A
a
c
b
d
e
f
g
B
82
4
45
2
6
4
3
3
6
7
3
7
8