2007-6-26
第三章 图与网络分析
(Graph and Network Analysis)
3.1 图的基本概念
3.2 网络分析
http://www.tju.edu.cn
第三章图与网络分析
A
B
C
D
A
C
B
D
图论起源—— 哥尼斯堡七桥问题结论：每个结点关联的边数均为偶数。
问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？
http://www.tju.edu.cn
第三章图与网络分析
3.1 图的基本概念由点和边组成，记作G=(V，E)，其中
V=(v
1
，v
2
,……，v
n
)为结点的集合，
E=(e
1
，e
2
,……，e
m
) 为边的集合。
点表示研究对象边表示表示研究对象之间的特定关系
1,图
http://www.tju.edu.cn
第三章图与网络分析图无向图，记作G=(V,E)
有向图，记作D=(V,A)
例 1：哥尼斯堡桥问题的图为一个无向图。
有向图的边称为弧 。
例 2：五个球队的比赛情况，
v
1
v
2
表示v
1
胜 v
2
。
v
1
v
2
v
3
v
4
v
5
2、图的分类
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
2
v
3
v
4
v
5
3、链与路、圈与回路链 点边交错的序列 圈 起点= 终点的链路点弧交错的序列 回路起点= 终点的路
v
1
v
2
v
3
v
4
v
5
无向图：
有向图：
http://www.tju.edu.cn
第三章图与网络分析
4、连通图任何两点之间至少存在一条链的图称为连通图，
否则称为不连通图。
G
1
G
2
G
1
为不连通图,G
2
为连通图例 3：
http://www.tju.edu.cn
第三章图与网络分析
5、支撑子图图 G=(V,E)和 G'=(V ',E ')，若V =V ' 且
E ' E,则称 G' 为 G的 支撑子图。
G
2
为 G
1
的支撑子图
v
1
v
2
v
3
v
4
v
5
G
1
v
1
v
2
v
3
v
4
v
5
G
2
例 4,
http://www.tju.edu.cn
第三章图与网络分析
6、赋权图（网络）
图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作 D=(V,A,C)。
5
5.5
v
1
v
2
v
3
v
4
v
5
3.5
7.5 4
2
3
例 5,
http://www.tju.edu.cn
第三章图与网络分析
3.2 网络分析网络分析主要内容：
——最小部分树、最短路、最大流。
http://www.tju.edu.cn
第三章图与网络分析一,最小支撑树问题
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
3.5
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
5 4
5
2
6
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
（ 1）树中任两点中有且仅有一条链；
（ 2）树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。
（ 3）边数 = 顶点数 –1。
树 无圈连通图
(A) (B) (C)
树的性质：
例 判断下面图形哪个是树：
1、树的概念与性质
http://www.tju.edu.cn
第三章图与网络分析若一个图 G =（ V,E）的支撑子图 T=（ V,E′） 构成树，则称 T 为 G的支撑树，又称生成树,部分树。
(G)
2、图的支撑树
(G
1
)
(G
2
)
(G
3
)(G
4
)
例
http://www.tju.edu.cn
第三章图与网络分析
[例 7] 某地新建 5处居民点，拟修道路连接5处，经勘测其道路可铺成如图所示。为使5处居民点都有道路相连，问至少要铺几条路？
解：
该问题实为求图的支撑树问题，
共需铺 4条路。
v
1
v
2
v
3
v
4
v
5
图的支撑树的应用举例
v
1
v
2
v
3
v
4
v
5
5
5.5
3.5
7.5 4
2
3
http://www.tju.edu.cn
第三章图与网络分析问题：求网络的支撑树，使其权和最小。
3、最小支撑树问题
5
5.5
v
1
v
2
v
3
v
4
v
5
3.5
7.5 4
2
3
算法 1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1 条边为止（n 为结点数） 。
[例 7] 求上例中的最小支撑树
3
解：
v
1
2
v
4
v
5
4
5
v
2
3.5
v
3
http://www.tju.edu.cn
第三章图与网络分析算法 2（破圈法）：
在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。
5
5.5
v
1
v
2
v
3
v
4
v
5
3.5
7.5 4
2
3
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
3.5
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
5 4
5
2
6
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
3.5
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
4
5
2
6
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
3.5
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
5
2
6
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
3.5
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
2
6
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
2
6
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
I
A
B
C
D
E
F
G
H
J
K
S
2
2
2
2
2
2
2
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
I
J
A
B
C
D
E
F
G
H
K
S
2
2
2
2
2
2
2
3
4
3
1
此即为最经济的煤气管道路线，所需的总费用为 25万元
http://www.tju.edu.cn
第三章图与网络分析二、
二、
最短路问题最短路问题问题：求网络中起点到其它点之间的一条最短路线。
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
10
4
4
[例 8] 求网络中 v
1
到 v
9
的最短路
http://www.tju.edu.cn
第三章图与网络分析算法：Dijkstra（狄克斯拉）标号法基本思想：从起点v
s
开始，逐步给每个结点v
j
标号[d
j
，v
i
]，其中d
j
为起点v
s
到v
j
的最短距离，v
i
为该最短路线上的前一节点。
10
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
[0,v
1
]
[1,v
1
]
(1) 给起点 v
1
标号 [0,v
1
]
(3) 考虑所有这样的边 [v
i
,v
j
]，其中 v
i
∈ V
A
,v
j
∈ V
B
，挑选其中与起点 v
1
距离最短（ min{d
i
+c
ij
}）的v
j
，对v
j
进行标号
(2) 把顶点集V 分成
V
A
：已标号点集
V
B
：未标号点集
(4) 重复 (2),(3)，直至终点v
n
标上号 [d
n
,v
i
]，则 d
n
即为
v
1
→ v
n
的最短距离，反向追踪可求出最短路。
步骤：
[0,v
1
]
[1,v
1
]
[3,v
1
]
(1) 给起点 v
1
标号 [0,v
1
]
(3) 考虑所有这样的边 [v
i
,v
j
]，其中 v
i
∈ V
A
,v
j
∈ V
B
，挑选其中与起点 v
1
距离最短（ min{d
i
+c
ij
}）的v
j
，对v
j
进行标号
(4) 重复 (2),( 3)，直至终点v
n
标上号 [d
n
,v
i
]，则 d
n
即为
v
1
→ v
n
的最短距离，反向追踪可求出最短路。
步骤：
(2) 把顶点集V 分成
V
A
：已标号点集
V
B
：未标号点集
10
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析
[0,v
1
]
[1,v
1
]
[3,v
1
]
[5,v
3
]
10
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析
[0,v
1
]
[1,v
1
]
[3,v
1
]
[5,v
3
]
[6,v
2
]
10
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析
[0,v
1
]
[1,v
1
]
[3,v
1
]
[5,v
3
]
[6,v
2
]
[9,v
5
]
10
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析
[0,v
1
]
[1,v
1
]
[3,v
1
]
[5,v
3
]
[6,v
2
]
[9,v
5
]
[10,v
5
]
10
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析
[0,v
1
]
[1,v
1
]
[3,v
1
]
[5,v
3
]
[6,v
2
]
[9,v
5
]
[10,v
5
]
[12,v
5
]
10
此时终点v
9
已标号 [12,v
5
]，则 12即为v
1
→ v
n
的最短距离，反向追踪可求出最短路
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析
[0,v
1
]
[1,v
1
]
[3,v
1
]
[5,v
3
]
[6,v
2
]
[9,v
5
]
[10,v
5
]
[12,v
5
]
10
v
1
到 v
9
的最短路为,v
1
→ v
3
→ v
2
→ v
5
→ v
9，
最短距离为12
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析练习题 P129 习题5.3
[0,v
1
]
[4,v
1
]
[3,v
1
]
[5,v
2
]
[6,v
2
]
[9,v
7
]
[7,v
4
/ v
6
]
[8.5,v
6
]
[6,v
2
]
v
2
v
1
v
5
v
4
v
3
v
6
v
8
v
7
v
9
4
3
2
3
2.5
3
3
5
2
3
4
2
1
http://www.tju.edu.cn
第三章图与网络分析练习题 无向图情形求网络中v
1
至 v
7
的最短路。
v
1
v
2
v
3
v
4 v
5
v
6
v
7
2
2
5
3
5
5
7
1
5
7
1
3
最短路模型的应用—— 设备更新问题 （ P119 例 5.3）
v
2
v
1
v
3
v
4
v
5
v
6
第 i年 12 3 45
价格 a
i
11 11 12 12 13
使用寿命 0~1 1~2 2~3 3~4 4~5
费用b
j
568118
[0,v
1
]
[16,v
1
]
[22,v
1
]
[30,v
1
]
[41,v
1
]
[53,v
3
/v
4
]
16
30
22
41
59
16
22
30
41
17
23
31
17
23
18
分析：
结点,V={v
1
,…,v
6
},v
i
表示第 i年初；
边,E={(v
i
,v
j
)} 表示第 i年初购买，用至第 j年初； i= 1,…,5; j= 2,…,6
权 c
ij
,i年初 ~ j年初的费用，即 c
ij
=i年初购买费+ （ j-i）年里的维修费
http://www.tju.edu.cn
第三章图与网络分析
v
2
v
1
v
3
v
4
v
5
v
6
[0,v
1
]
[16,v
1
]
[22,v
1
]
[30,v
1
]
[41,v
1
]
[53,v
3
/v
4
]
16
30
22
41
59
16
22
30
41
17
23
31
17
23
18
http://www.tju.edu.cn
第三章图与网络分析三、网络最大流问题三、网络最大流问题例 9：下图为V
1
到 V
6
的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从V
1
到 V
6
的产品数量最多。
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
http://www.tju.edu.cn
第三章图与网络分析设有网络D=(V,A,C)，其中C={c
ij
},c
ij
为弧(v
i
,v
j
)
上的容量，现在D上要通过一个流f={f
ij
},f
ij
为弧
(v
i
,v
j
)上的流量。
问题：如何安排f
ij
，可使网络D上的总流量V最大？
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
1、一般提法：
http://www.tju.edu.cn
第三章图与网络分析
2、最大流问题的模型
、最大流问题的模型
max v=v（ f）
ijij
cf ≤≤0
≠
=?
=
=?
∑∑
tsi
tifv
sifv
ff
jj
jiij
,0
)(
)(
容量约束平衡约束
s.t.
v
2
V
s
v
3
v
4
v
5
V
t
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
注：满足约束条件的流 f称为可行流
http://www.tju.edu.cn
第三章图与网络分析
3、基本概念与定理
、基本概念与定理
（
（
1）弧按流量分为
）弧按流量分为饱和弧 f
ij
=c
ij
非饱和弧 f
ij
<c
ij
零流弧 f
ij
=0
非零流弧 f
ij
≠ 0
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
http://www.tju.edu.cn
第三章图与网络分析
（
（
2）
）
增广链增广链
f为一可行流，u 为 v
s
至 v
t
的链，令
u
+
={正向弧},u
-
={反向弧 }。若u
+
中弧皆非饱，且u
-
中弧皆非零，则称 u为关于f 的一条增广链。
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
http://www.tju.edu.cn
第三章图与网络分析
（
（
2）
）
增广链增广链
f为一可行流，u 为 v
s
至 v
t
的链，令
u
+
={正向弧},u
-
={反向弧 }。若u
+
中弧皆非饱，且u
-
中弧皆非零，则称 u为关于f 的一条增广链。
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
http://www.tju.edu.cn
第三章图与网络分析
（
（
2）
）
增广链增广链
f为一可行流，u 为 v
s
至 v
t
的链，令
u
+
={正向弧},u
-
={反向弧 }。若u
+
中弧皆非饱，且u
-
中弧皆非零，则称 u为关于f 的一条增广链。
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
http://www.tju.edu.cn
第三章图与网络分析
（
（
2）
）
增广链增广链
f为一可行流，u 为 v
s
至 v
t
的链，令
u
+
={正向弧},u
-
={反向弧 }。若u
+
中弧皆非饱，且u
-
中弧皆非零，则称 u为关于f 的一条增广链。
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
（
（
3）
）
截集与截量截集与截量把 V分成两部分,V
1
和 V
2
(V
1
∩ V
2
= φ,V
1
∪ V
2
= V)
且 v
s
∈ V
1
,v
t
∈ V
2
，则弧集 (V
1
,V
2
)称为 D的 截集。
截集上的容量和称为截量，记为C(V
1
,V
2
) 。
v
1
v
s
v
2
v
3
v
4
v
t
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
{(v
s
,v
2
),(v
1
,v
2
),(v
1
,v
3
),(v
1
,v
4
)}；
截量为,C(V
1
,V
2
) =8+4+5+3=20
例 若 V
1
={v
s
,v
1
}，则截集为：
（
（
4）流量与截量的关系
）流量与截量的关系任一可行流的流量都不会超过任一截集的截量
（∵ v(f)=f (V
1
,V
2
) - f (V
2
,V
1
) ≤ f (V
1
,V
2
) ≤ C (V
1
,V
2
) ）
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
最大流最小截定理：网络的最大流量等于最小截量。
http://www.tju.edu.cn
第三章图与网络分析例例
,如图所示的网络中，弧旁数字为如图所示的网络中，弧旁数字为(c
ij
,
f
ij
)
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（
（
1）确定所有的截集；
）确定所有的截集；
（
（
2）
）
求最小截集的容量；
求最小截集的容量；
（
（
3）证明图中的流为最大流；
）证明图中的流为最大流；
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（
（
1）所有的截集：
）所有的截集：
①
V
1
={v
s
}，
截集为截集为{(v
s
,v
1
),(v
s
,v
2
)}，截量为,6
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（
（
1）所有的截集：
）所有的截集：
① V
1
={v
s
}，
截集为截集为 {(v
s
,v
1
),(v
s
,v
2
)}，截量为,6
② V
1
={v
s
,v
1
}，
截集为截集为 {(v
s
,v
2
),(v
1
,v
t
)}，截量为：7
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（
（
1）所有的截集：
）所有的截集：
① V
1
={v
s
}，
截集为截集为 {(v
s
,v
1
),(v
s
,v
2
)}，截量为,6
② V
1
={v
s
,v
1
}，
截集为截集为 {(v
s
,v
2
),(v
1
,v
t
)}，截量为：7
③ V
1
={v
s
,v
2
}，
截集为截集为 {……}，截量为,7
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（
（
1）所有的截集：
）所有的截集：
① V
1
={v
s
}，
截集为截集为{(v
s
,v
1
),(v
s
,v
2
)}，截量为,6
② V
1
={v
s
,v
1
}，
截集为截集为{(v
s
,v
2
),(v
1
,v
t
)}，截量为：7
③ V
1
={v
s
,v
2
}，
截集为截集为{ ……}，截量为,7
④ V
1
={v
s
,v
3
}，
截集为截集为{ ……}，截量为,12
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（
（
1）所有的截集：
）所有的截集：
① V
1
={v
s
}，
截集为截集为{(v
s
,v
1
),(v
s
,v
2
)}，截量为,6
② V
1
={v
s
,v
1
}，
截集为截集为{(v
s
,v
2
),(v
1
,v
t
)}，截量为：7
③ V
1
={v
s
,v
2
}，
截集为截集为{ ……}，截量为,7
④ V
1
={v
s
,v
3
}，
截集为截集为{ ……}，截量为,12
⑤ V
1
={v
s
,v
1
,v
2
}，
截集为截集为{ ……}，截量为：5
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（ 1）所有的截集：
① V
1
={v
s
}，
截集为截集为 {(v
s
,v
1
),(v
s
,v
2
)}，截量为,6
② V
1
={v
s
,v
1
}，
截集为截集为 {(v
s
,v
2
),(v
1
,v
t
)}，截量为：7
③ V
1
={v
s
,v
2
}，
截集为截集为 {……}，截量为,7
④ V
1
={v
s
,v
3
}，
截集为截集为 {……}，截量为,12
⑤ V
1
={v
s
,v
1
,v
2
}，
截集为截集为 {……}，截量为：5
……
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（ 2） 最小截量 min C (V1,V2)= 5；
（ 3） ∵ v(f
*
)=5= min C (V1,V2)
∴ f
*
是最大流。
http://www.tju.edu.cn
第三章图与网络分析
4、求最大流方法
、求最大流方法
——标号法标号法理论依据：
不存在关于f 的增广链可行流 f是最大流思路：从始点开始标号，寻找是否存在增广链。
给 v
j
标号为 [θ
j
,v
i
]，其中θ
j
为调整量,v
i
为前一节点。
步骤,(1)给 v
s
标号为[∞,v
s
]，
流出未饱和弧(v
s
,v
j
),给 v
j
标号[θ
j
,v
s
],其中 θ
j
=c
sj
-f
sj
例例
10,图中网络弧旁数字为图中网络弧旁数字为 (c
ij
,
f
ij
)，用标号法求最大流。
[∞,v
s
]
[4,v
s
]
选与v
s
关联的
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
（
3
,
0
）
http://www.tju.edu.cn
第三章图与网络分析
(2)把节点集V 分为
V
A
：已标号点集
V
B
：未标号点集
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
（
3
,0
）
http://www.tju.edu.cn
第三章图与网络分析考虑所有弧 (v
i
,v
j
)或 (v
j
,v
i
),其中v
i
∈ V
A
,v
j
∈ V
B
，若该弧为流出未饱弧,则给 v
j
标号 [θ
j
,v
i
],其中θ
j
=c
ij
-f
ij
流入非零弧,则给 v
j
标号 [θ
j
,-v
i
],其中θ
j
= f
ij
(3)
[1,-v
1
]
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
（
3
,
0
）
http://www.tju.edu.cn
第三章图与网络分析
(4)
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
[1,-v
1
]
重复（ 2）,（ 3），依次进行的结局可能为
（
3
,
0
）
v
t
已标号，得到一条增广链u( 反向追踪 )，转（5）；
v
t
未标号，且无法再标号,此时的流为最大流,此时的截集 为 最小截。
http://www.tju.edu.cn
第三章图与网络分析
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
[1,-v
1
]
(4) 重复（ 2）,（ 3），依次进行的结局可能为
v
t
已标号，得到一条增广链u( 反向追踪 )，转（5）；
v
t
未标号，且无法再标号,此时的流为最大流,此时的截集 为 最小截。
[1,v
2
]
（
3
,
0
）
http://www.tju.edu.cn
第三章图与网络分析
(4) 重复（ 2）,（ 3），依次进行的结局可能为
v
t
已标号，得到一条增广链u( 反向追踪 )，转（5）；
v
t
未标号，且无法再标号,此时的流为最大流,此时的截集 为 最小截。
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
[1,-v
1
][1 v
2
]
（
3
,
0
）
[2,v
4
]
http://www.tju.edu.cn
第三章图与网络分析
(4) 重复（ 2）,（ 3），依次进行的结局可能为
v
t
已标号，得到一条增广链u( 反向追踪 )，转（5）；
v
t
未标号，且无法再标号,此时的流为最大流,此时的截集 为 最小截。
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
[1,-v
1
][1 v
2
]
（
3
,
0
）
[2,v
4
]
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
[1,-v
1
][1
2
]
（
3
,
0
）
[1,-v
2
]
[2,v
4
]
(5) 调整。取
}{min
j
uv
j
θθ
∈
=
，令
∈?
∈+
=
+
uvvf
uvvf
uvvf
f
jiij
jiij
jiij
ij
),(
),(
),(
'
θ
θ
，得新流
}{
'
ij
f
,转 (1)。
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
[1,-v
1
][1-v
2
]
（
3
,
0
）
[1,-v
2
]
[2,v
4
]
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
2
）
（
1
,
0
）
（ 2,2）
（
1
,
1
）
（
5
,
4
）
（
2
,
1
）
（ 4,4）
（
3
,
0
）
调整
http://www.tju.edu.cn
第三章图与网络分析
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
2
）
（
1
,
0
）
（ 2,2）
（
1
,
1
）
（
5
,
4
）
（
2
,
1
）
（ 4,4）
（
3
,
0
）
[∞,v
s
]
[3,v
s
]
http://www.tju.edu.cn
第三章图与网络分析
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
2
）
（
1
,
0
）
（ 2,2）
（
1
,
1
）
（
5
,
4
）
（
2
,
1
）
（ 4,4）
（
3
,
0
）
[∞,v
s
]
[3,v
s
]
此时标号无法进行，当前流为最大流，最大流量为
5；最小截为{(v
s
,v
2
),(v
1
,v
3
)}，截量为：5
http://www.tju.edu.cn
第三章图与网络分析例 11,图中 A,B,C,D,E,F分别表示陆地和岛屿，①
② ……⒁表示桥梁及其编号。河两岸分别互为敌对的双方部队占领，问至少应切断几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分析。
A
B
D
E
F
C
①
②
③
④
⑤
⑥
⑦
⑧
⑨
⑩
⑾
⑿
⒀⒁
分析：转化为一个网络图，
弧的容量为两点间的桥梁数。
则问题为求最小截。
A
B
D
E
F
C
①
②
③
④ ⑤
⑥
⑦
⑧
⑨
⑩
⑾
⑿
⒀⒁
A
B
C
D
E
F
2
1
1
1
1
1
2
2
2
2
2
2
分析：转化为一个网络图，
弧的容量为两点间的桥梁数。
答案：最小截为{AE、
CD,CF}
则问题为求最小截。
A
B
D
E
F
C
①
②
③
④ ⑤
⑥
⑦
⑧
⑨
⑩
⑾
⑿
⒀⒁
A
B
C
D
E
F
2
1
1
1
1
1
2
2
2
2
2
2
http://www.tju.edu.cn
第三章图与网络分析例12,有一批人从我国A城赴俄罗斯B城，可能的旅行路线如图：
边防队拟建立足够数量检查站以便使每辆汽车至少必经过一个检查站，建立检查站的费用根据各路段条件有所不同（如图数字所示），求最小费用解。
a
BA b
c
d
e
f
g
4
6
8
2
3
2
5
7
3
8
4
3
7
6
4
（分析：最小截问题）
http://www.tju.edu.cn
第三章图与网络分析引例：沏茶
1 3
2
4
烧水（ 10）
备茶
（ 3）
沏茶（ 2）
洗碗
（
2
）
3.3 网络计划
http://www.tju.edu.cn
第三章图与网络分析
1、问题描述一项工程，已知各工序完成时间t 及其先后关系求：工程完工期及关键工序关键工序：主矛盾工序，不能延期完工路线,从始点到终点的一条路关键路线：由关键工序组成的路线，是所有路线中时间最长的路线。
相关概念：
1 3
2
4
烧水（ 10）
备茶
（ 3）
沏茶（ 2）
洗碗
（
2
）
http://www.tju.edu.cn
第三章图与网络分析
2,求解方法—— 关键路径法（CPM）
分为三步：
? 绘制工程网络图
? 标号法求工期 T
? 标号法求关键路线
http://www.tju.edu.cn
第三章图与网络分析
? 将整个工程分解为若干工序
? 确定各工序的前后顺序（紧前、紧后）
? 确定工序完成时间三点估计法：最乐观时间 a、最可能时间 m、最悲观时间b
t
ij
=
6
a+4m+b
一点估计法准备工作
（ 1）绘制工程网络图
1）顺序：按工序的先后从左至右
2）图的结构弧：
i
j
表示工序，
i
j
、
为工序的起点、终点结点,相邻工序的时间分界点，称为事项权,工序的完成时间相邻弧,工序的前后衔接关系，称为紧前或紧后工序
3）绘图要求图中不能出现缺口、回路和多重边多重边的处理：
1 2
a
b
1 2
a
3
b
b '
虚工序
1 3
2
4
烧水
（ 10）
备茶
（ 3）
沏茶（ 2）
洗碗
（
2
）
http://www.tju.edu.cn
第三章图与网络分析例 13 某工厂进行技术改造，需要拆掉旧厂房、
建造新厂房和安排设备。这项改建工程可以分解为 7道工序，其相关资料如下表：
工序代号 工序名称 紧前工序 工序时间（周）
A
拆迁
/2
B
工程设计
/3
C
土建工程设计
B2.5
D
采购设备
B6
E
厂房土建
C,A20
F
设备安装
D,E4
G
设备调试
F2
http://www.tju.edu.cn
第三章图与网络分析
1
2
3
4 5
A（ 2）
B (3)
C (2.5)
D (6)
E (20)
F (4)
6
G (2)
工序代号 工序名称 紧前工序 工序时间（周）
A 拆迁 /2
B 工程设计 /3
C 土建工程设计 B2.5
D 采购设备 B6
E 厂房土建 C,A20
F 设备安装 D,E4
G 设备调试 F2
解：
工序代号 紧前工序工序时间（周）
A/ 2
B/ 3
C/ 2
DA 3
EA 4
工序代号 紧前工序工序时间（周）
FB 7
G 6
HD,E4
IB,C10
JG,I3
例 14,绘制工程网络图续左表解：
1
A (2)
D (3)
C (2)
2
E (4)
3
F(7)
B '(0)
G(6)
4
5
E'(0)
6
I (10)
7
J(3)
H (4)
8
B (3)
http://www.tju.edu.cn
第三章图与网络分析
② 四个工序 A,B,X,Y有如下关系：
A是 X的紧前工序，A和 B同时又是Y 的紧前工序
1 2 3
4 5 6
A
B
X
Y
A '
虚工序两种情况需要引入虚工序：
1 2
A
B
1 2
A
3
B
虚工序
① 两个工序A,B有相同的始点和终点
B '
http://www.tju.edu.cn
第三章图与网络分析练习,P150习题6.1
1
60
2
3
4
7
5
6 8 9 10
11 12 13 14
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
14
20
30
21
10
7
12
25
5
10
60
10
15 2 5
7
f '
b '
（ 2）用标号法求工期 T
步骤：
E
j
Ⅱ,给任意事项
j
标
，
E
j
=max{以
ij
t,}
为箭头的各箭之,箭尾
j
+箭长
（ 1）标出各事项的最早开始时间
（ 2）终点即为工期
n
的标号 T
1
A (2)
D (3)
C (2)
2
E (4)
3
F(7)
B '(0)
G(6)
4
5
E'(0)
6
I (10)
7
J(3)
H (4)
8
B (3)
0
2
3
3
6
6
13
16
Ⅰ、给始点①标
0
（ 3）用标号法求关键路线步骤：
1
A (2)
D (3)
C (2)
2
E (4)
3
F(7)
B '(0)
G(6)
4
5
E'(0)
6
I (10)
7
J(3)
H (4)
8
B (3)
0
2
3
3
6
6
13
16
（ 1）标出各事项的最晚开始时间
T
Ⅰ、给终点
n
标
L
i
=min{以
ij
t,}
为箭尾的各箭之,箭头 －箭长
Ⅱ,给任意事项
i 标
，
L
i
i
16
12
12
8
13
3
3
0
1
A (2)
D (3)
C (2)
2
E (4)
3
F(7)
B '(0)
G(6)
4
5
E'(0)
6
I (10)
7
J(3)
H (4)
8
B (3)
0
2
3
3
6
6
13
16
T
16
12
12
8
13
3
3
0
R
ij
= j
的
－ i 的 －
ij
t
（ 2）计算各工序
i
j 的时差 R
ij
：
则关键工序为R
ij
=0的工序。
注：关键工序头尾皆有
=
（反之未必成立）
http://www.tju.edu.cn
第三章图与网络分析练习,P150习题6.1
1
60
2
3
4
7
5
6 8 9 10
11 12 13 14
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
14
20
30
21
10
7
12
25
5
10
60
10
15 2 5
7
b '
f '
152
http://www.tju.edu.cn
第三章图与网络分析
3、工程工期的概率分析 ——计划评审技术（PERT ）
? PERT与 CPM的主要区别：
CPM工序时间是确定的；
),(~
2
σ
E
TNT
PERT工序时间 t
ij
是随机变量，而完工期 T 也是随机的，由概率知识,T 服从正态分布
T
Τ
Ε
http://www.tju.edu.cn
第三章图与网络分析
? 确定平均工序时间的三点估计法：
6
4
ijijij
ij
bma
t
++
=
2
2
6
=
ijij
ij
ab
σ
? 总工期 ),(~
2
σ
E
TNT
其中：
∑
∈
=
Iji
ijE
tT
),(
（ I 为关键路线）
∑
∈
=
Iji
ij
),(
22
σσ
)1,0(~ N
TT
E
σ
λ
=
T
Τ
Ε
标准化
http://www.tju.edu.cn
第三章图与网络分析
1,给定时间T
*
，求工期T ≤ T
*
内完工的概率
? PERT的主要问题方法：首先计算
σ
λ
E
TT?
=
*
*
，
∫
∞?
=≤=≤
*
2
d
2
1
*}{*}{
2
λ
π
λλ tePTTP
t
0
*
λ
λ
：阴影面积*)(λΦ
)(1)( λΦλΦ?=?
)(λΦ然后查表求
。
*)(
Δ
λΦ=
9
12.83
7.83
8.17
4
10.33
12.17
11
A
B
C
D
E
F
G
H
21
3 5
7
64
例 15、已知某工程网络图，以及各工序的时间参数。
工序
amb
A10
5
7
7
2
F 8 10 14
G101215
H 9 11 13
B
1513
8
8C
9
10
10
11D
E64
T
E
=42.33
0.44
/
1.00
/
/
0.25
/
0.69
2
ij
σ
11
12.17
10.33
4
9
8.17
7.83
12.83
t
ij
求工程在40 天内完工的概率。
关键路线I 为,A→ C→ F→ H；
∑
∈
=
Iji
ij
),(
22
σσ
38.2=
σ
λ
E
TT?
=
*
*
51.1
54.1
33.4240
=
=
解：
}40{ ≤TP
066.0)51.1( =?=Φ
http://www.tju.edu.cn
第三章图与网络分析
2,给定概率p,求完工可能性为 p的工期方法：首先查表求
*
λ
，使
p=*)(λΦ；
再由
σ
λ
E
TT?
=
*
*
*
T解出例、上例中，求完工可能性达95% 的工期。
95.0*)( =λΦ
解：由
，
查表；6.1
*
=λ
再由
54.1
33.42
**
*
=
=
TTT
E
σ
λ
解出
45
*
=T
第三章 图与网络分析
(Graph and Network Analysis)
3.1 图的基本概念
3.2 网络分析
http://www.tju.edu.cn
第三章图与网络分析
A
B
C
D
A
C
B
D
图论起源—— 哥尼斯堡七桥问题结论：每个结点关联的边数均为偶数。
问题：一个散步者能否从任一块陆地出发，走过七座桥，且每座桥只走过一次，最后回到出发点？
http://www.tju.edu.cn
第三章图与网络分析
3.1 图的基本概念由点和边组成，记作G=(V，E)，其中
V=(v
1
，v
2
,……，v
n
)为结点的集合，
E=(e
1
，e
2
,……，e
m
) 为边的集合。
点表示研究对象边表示表示研究对象之间的特定关系
1,图
http://www.tju.edu.cn
第三章图与网络分析图无向图，记作G=(V,E)
有向图，记作D=(V,A)
例 1：哥尼斯堡桥问题的图为一个无向图。
有向图的边称为弧 。
例 2：五个球队的比赛情况，
v
1
v
2
表示v
1
胜 v
2
。
v
1
v
2
v
3
v
4
v
5
2、图的分类
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
2
v
3
v
4
v
5
3、链与路、圈与回路链 点边交错的序列 圈 起点= 终点的链路点弧交错的序列 回路起点= 终点的路
v
1
v
2
v
3
v
4
v
5
无向图：
有向图：
http://www.tju.edu.cn
第三章图与网络分析
4、连通图任何两点之间至少存在一条链的图称为连通图，
否则称为不连通图。
G
1
G
2
G
1
为不连通图,G
2
为连通图例 3：
http://www.tju.edu.cn
第三章图与网络分析
5、支撑子图图 G=(V,E)和 G'=(V ',E ')，若V =V ' 且
E ' E,则称 G' 为 G的 支撑子图。
G
2
为 G
1
的支撑子图
v
1
v
2
v
3
v
4
v
5
G
1
v
1
v
2
v
3
v
4
v
5
G
2
例 4,
http://www.tju.edu.cn
第三章图与网络分析
6、赋权图（网络）
图的每条边都有一个表示一定实际含义的权数，称为赋权图。记作 D=(V,A,C)。
5
5.5
v
1
v
2
v
3
v
4
v
5
3.5
7.5 4
2
3
例 5,
http://www.tju.edu.cn
第三章图与网络分析
3.2 网络分析网络分析主要内容：
——最小部分树、最短路、最大流。
http://www.tju.edu.cn
第三章图与网络分析一,最小支撑树问题
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
3.5
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
5 4
5
2
6
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
（ 1）树中任两点中有且仅有一条链；
（ 2）树任删去一边则不连通，故树是使图保持连通且具有最少边数的一种图形。
（ 3）边数 = 顶点数 –1。
树 无圈连通图
(A) (B) (C)
树的性质：
例 判断下面图形哪个是树：
1、树的概念与性质
http://www.tju.edu.cn
第三章图与网络分析若一个图 G =（ V,E）的支撑子图 T=（ V,E′） 构成树，则称 T 为 G的支撑树，又称生成树,部分树。
(G)
2、图的支撑树
(G
1
)
(G
2
)
(G
3
)(G
4
)
例
http://www.tju.edu.cn
第三章图与网络分析
[例 7] 某地新建 5处居民点，拟修道路连接5处，经勘测其道路可铺成如图所示。为使5处居民点都有道路相连，问至少要铺几条路？
解：
该问题实为求图的支撑树问题，
共需铺 4条路。
v
1
v
2
v
3
v
4
v
5
图的支撑树的应用举例
v
1
v
2
v
3
v
4
v
5
5
5.5
3.5
7.5 4
2
3
http://www.tju.edu.cn
第三章图与网络分析问题：求网络的支撑树，使其权和最小。
3、最小支撑树问题
5
5.5
v
1
v
2
v
3
v
4
v
5
3.5
7.5 4
2
3
算法 1（避圈法）：把边按权从小到大依次添入图中，若出现圈，则删去其中最大边，直至填满n-1 条边为止（n 为结点数） 。
[例 7] 求上例中的最小支撑树
3
解：
v
1
2
v
4
v
5
4
5
v
2
3.5
v
3
http://www.tju.edu.cn
第三章图与网络分析算法 2（破圈法）：
在图中找圈，并删除其中最大边。如此进行下去，直至图中不存在圈。
5
5.5
v
1
v
2
v
3
v
4
v
5
3.5
7.5 4
2
3
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
3.5
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
5 4
5
2
6
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
3.5
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
4
5
2
6
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
3.5
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
5
2
6
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
3.5
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
2
6
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
A
B
C
D
E
F
G
H
I
J
K
S
2
2
2
2
2
2
2
6
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
I
A
B
C
D
E
F
G
H
J
K
S
2
2
2
2
2
2
2
3
4
5
3
1
http://www.tju.edu.cn
第三章图与网络分析
[例 6]今有煤气站 A，将给一居民区供应煤气，居民区各用户所在位置如图所示，铺设各用户点的煤气管道所需的费用（单位：万元）如图边上的数字所示。要求设计一个最经济的煤气管道路线，并求所需的总费用。
I
J
A
B
C
D
E
F
G
H
K
S
2
2
2
2
2
2
2
3
4
3
1
此即为最经济的煤气管道路线，所需的总费用为 25万元
http://www.tju.edu.cn
第三章图与网络分析二、
二、
最短路问题最短路问题问题：求网络中起点到其它点之间的一条最短路线。
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
10
4
4
[例 8] 求网络中 v
1
到 v
9
的最短路
http://www.tju.edu.cn
第三章图与网络分析算法：Dijkstra（狄克斯拉）标号法基本思想：从起点v
s
开始，逐步给每个结点v
j
标号[d
j
，v
i
]，其中d
j
为起点v
s
到v
j
的最短距离，v
i
为该最短路线上的前一节点。
10
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
[0,v
1
]
[1,v
1
]
(1) 给起点 v
1
标号 [0,v
1
]
(3) 考虑所有这样的边 [v
i
,v
j
]，其中 v
i
∈ V
A
,v
j
∈ V
B
，挑选其中与起点 v
1
距离最短（ min{d
i
+c
ij
}）的v
j
，对v
j
进行标号
(2) 把顶点集V 分成
V
A
：已标号点集
V
B
：未标号点集
(4) 重复 (2),(3)，直至终点v
n
标上号 [d
n
,v
i
]，则 d
n
即为
v
1
→ v
n
的最短距离，反向追踪可求出最短路。
步骤：
[0,v
1
]
[1,v
1
]
[3,v
1
]
(1) 给起点 v
1
标号 [0,v
1
]
(3) 考虑所有这样的边 [v
i
,v
j
]，其中 v
i
∈ V
A
,v
j
∈ V
B
，挑选其中与起点 v
1
距离最短（ min{d
i
+c
ij
}）的v
j
，对v
j
进行标号
(4) 重复 (2),( 3)，直至终点v
n
标上号 [d
n
,v
i
]，则 d
n
即为
v
1
→ v
n
的最短距离，反向追踪可求出最短路。
步骤：
(2) 把顶点集V 分成
V
A
：已标号点集
V
B
：未标号点集
10
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析
[0,v
1
]
[1,v
1
]
[3,v
1
]
[5,v
3
]
10
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析
[0,v
1
]
[1,v
1
]
[3,v
1
]
[5,v
3
]
[6,v
2
]
10
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析
[0,v
1
]
[1,v
1
]
[3,v
1
]
[5,v
3
]
[6,v
2
]
[9,v
5
]
10
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析
[0,v
1
]
[1,v
1
]
[3,v
1
]
[5,v
3
]
[6,v
2
]
[9,v
5
]
[10,v
5
]
10
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析
[0,v
1
]
[1,v
1
]
[3,v
1
]
[5,v
3
]
[6,v
2
]
[9,v
5
]
[10,v
5
]
[12,v
5
]
10
此时终点v
9
已标号 [12,v
5
]，则 12即为v
1
→ v
n
的最短距离，反向追踪可求出最短路
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析
[0,v
1
]
[1,v
1
]
[3,v
1
]
[5,v
3
]
[6,v
2
]
[9,v
5
]
[10,v
5
]
[12,v
5
]
10
v
1
到 v
9
的最短路为,v
1
→ v
3
→ v
2
→ v
5
→ v
9，
最短距离为12
v
2
v
1
v
3
v
4
v
5
v
6
v
7
v
8
v
9
1
6
3
2
2
2
2
6
6
1
3
3
10
4
4
http://www.tju.edu.cn
第三章图与网络分析练习题 P129 习题5.3
[0,v
1
]
[4,v
1
]
[3,v
1
]
[5,v
2
]
[6,v
2
]
[9,v
7
]
[7,v
4
/ v
6
]
[8.5,v
6
]
[6,v
2
]
v
2
v
1
v
5
v
4
v
3
v
6
v
8
v
7
v
9
4
3
2
3
2.5
3
3
5
2
3
4
2
1
http://www.tju.edu.cn
第三章图与网络分析练习题 无向图情形求网络中v
1
至 v
7
的最短路。
v
1
v
2
v
3
v
4 v
5
v
6
v
7
2
2
5
3
5
5
7
1
5
7
1
3
最短路模型的应用—— 设备更新问题 （ P119 例 5.3）
v
2
v
1
v
3
v
4
v
5
v
6
第 i年 12 3 45
价格 a
i
11 11 12 12 13
使用寿命 0~1 1~2 2~3 3~4 4~5
费用b
j
568118
[0,v
1
]
[16,v
1
]
[22,v
1
]
[30,v
1
]
[41,v
1
]
[53,v
3
/v
4
]
16
30
22
41
59
16
22
30
41
17
23
31
17
23
18
分析：
结点,V={v
1
,…,v
6
},v
i
表示第 i年初；
边,E={(v
i
,v
j
)} 表示第 i年初购买，用至第 j年初； i= 1,…,5; j= 2,…,6
权 c
ij
,i年初 ~ j年初的费用，即 c
ij
=i年初购买费+ （ j-i）年里的维修费
http://www.tju.edu.cn
第三章图与网络分析
v
2
v
1
v
3
v
4
v
5
v
6
[0,v
1
]
[16,v
1
]
[22,v
1
]
[30,v
1
]
[41,v
1
]
[53,v
3
/v
4
]
16
30
22
41
59
16
22
30
41
17
23
31
17
23
18
http://www.tju.edu.cn
第三章图与网络分析三、网络最大流问题三、网络最大流问题例 9：下图为V
1
到 V
6
的一交通网，权表示相应运输线的最大通过能力，制定一方案，使从V
1
到 V
6
的产品数量最多。
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
http://www.tju.edu.cn
第三章图与网络分析设有网络D=(V,A,C)，其中C={c
ij
},c
ij
为弧(v
i
,v
j
)
上的容量，现在D上要通过一个流f={f
ij
},f
ij
为弧
(v
i
,v
j
)上的流量。
问题：如何安排f
ij
，可使网络D上的总流量V最大？
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
1、一般提法：
http://www.tju.edu.cn
第三章图与网络分析
2、最大流问题的模型
、最大流问题的模型
max v=v（ f）
ijij
cf ≤≤0
≠
=?
=
=?
∑∑
tsi
tifv
sifv
ff
jj
jiij
,0
)(
)(
容量约束平衡约束
s.t.
v
2
V
s
v
3
v
4
v
5
V
t
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
注：满足约束条件的流 f称为可行流
http://www.tju.edu.cn
第三章图与网络分析
3、基本概念与定理
、基本概念与定理
（
（
1）弧按流量分为
）弧按流量分为饱和弧 f
ij
=c
ij
非饱和弧 f
ij
<c
ij
零流弧 f
ij
=0
非零流弧 f
ij
≠ 0
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
http://www.tju.edu.cn
第三章图与网络分析
（
（
2）
）
增广链增广链
f为一可行流，u 为 v
s
至 v
t
的链，令
u
+
={正向弧},u
-
={反向弧 }。若u
+
中弧皆非饱，且u
-
中弧皆非零，则称 u为关于f 的一条增广链。
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
http://www.tju.edu.cn
第三章图与网络分析
（
（
2）
）
增广链增广链
f为一可行流，u 为 v
s
至 v
t
的链，令
u
+
={正向弧},u
-
={反向弧 }。若u
+
中弧皆非饱，且u
-
中弧皆非零，则称 u为关于f 的一条增广链。
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
http://www.tju.edu.cn
第三章图与网络分析
（
（
2）
）
增广链增广链
f为一可行流，u 为 v
s
至 v
t
的链，令
u
+
={正向弧},u
-
={反向弧 }。若u
+
中弧皆非饱，且u
-
中弧皆非零，则称 u为关于f 的一条增广链。
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
http://www.tju.edu.cn
第三章图与网络分析
（
（
2）
）
增广链增广链
f为一可行流，u 为 v
s
至 v
t
的链，令
u
+
={正向弧},u
-
={反向弧 }。若u
+
中弧皆非饱，且u
-
中弧皆非零，则称 u为关于f 的一条增广链。
v
2
v
1
v
3
v
4
v
5
v
6
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
（
（
3）
）
截集与截量截集与截量把 V分成两部分,V
1
和 V
2
(V
1
∩ V
2
= φ,V
1
∪ V
2
= V)
且 v
s
∈ V
1
,v
t
∈ V
2
，则弧集 (V
1
,V
2
)称为 D的 截集。
截集上的容量和称为截量，记为C(V
1
,V
2
) 。
v
1
v
s
v
2
v
3
v
4
v
t
8
10
4
17
5
5
3
11
6
3
5
3
1
2
2
1
3
3
6
2
{(v
s
,v
2
),(v
1
,v
2
),(v
1
,v
3
),(v
1
,v
4
)}；
截量为,C(V
1
,V
2
) =8+4+5+3=20
例 若 V
1
={v
s
,v
1
}，则截集为：
（
（
4）流量与截量的关系
）流量与截量的关系任一可行流的流量都不会超过任一截集的截量
（∵ v(f)=f (V
1
,V
2
) - f (V
2
,V
1
) ≤ f (V
1
,V
2
) ≤ C (V
1
,V
2
) ）
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
最大流最小截定理：网络的最大流量等于最小截量。
http://www.tju.edu.cn
第三章图与网络分析例例
,如图所示的网络中，弧旁数字为如图所示的网络中，弧旁数字为(c
ij
,
f
ij
)
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（
（
1）确定所有的截集；
）确定所有的截集；
（
（
2）
）
求最小截集的容量；
求最小截集的容量；
（
（
3）证明图中的流为最大流；
）证明图中的流为最大流；
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（
（
1）所有的截集：
）所有的截集：
①
V
1
={v
s
}，
截集为截集为{(v
s
,v
1
),(v
s
,v
2
)}，截量为,6
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（
（
1）所有的截集：
）所有的截集：
① V
1
={v
s
}，
截集为截集为 {(v
s
,v
1
),(v
s
,v
2
)}，截量为,6
② V
1
={v
s
,v
1
}，
截集为截集为 {(v
s
,v
2
),(v
1
,v
t
)}，截量为：7
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（
（
1）所有的截集：
）所有的截集：
① V
1
={v
s
}，
截集为截集为 {(v
s
,v
1
),(v
s
,v
2
)}，截量为,6
② V
1
={v
s
,v
1
}，
截集为截集为 {(v
s
,v
2
),(v
1
,v
t
)}，截量为：7
③ V
1
={v
s
,v
2
}，
截集为截集为 {……}，截量为,7
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（
（
1）所有的截集：
）所有的截集：
① V
1
={v
s
}，
截集为截集为{(v
s
,v
1
),(v
s
,v
2
)}，截量为,6
② V
1
={v
s
,v
1
}，
截集为截集为{(v
s
,v
2
),(v
1
,v
t
)}，截量为：7
③ V
1
={v
s
,v
2
}，
截集为截集为{ ……}，截量为,7
④ V
1
={v
s
,v
3
}，
截集为截集为{ ……}，截量为,12
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（
（
1）所有的截集：
）所有的截集：
① V
1
={v
s
}，
截集为截集为{(v
s
,v
1
),(v
s
,v
2
)}，截量为,6
② V
1
={v
s
,v
1
}，
截集为截集为{(v
s
,v
2
),(v
1
,v
t
)}，截量为：7
③ V
1
={v
s
,v
2
}，
截集为截集为{ ……}，截量为,7
④ V
1
={v
s
,v
3
}，
截集为截集为{ ……}，截量为,12
⑤ V
1
={v
s
,v
1
,v
2
}，
截集为截集为{ ……}，截量为：5
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（ 1）所有的截集：
① V
1
={v
s
}，
截集为截集为 {(v
s
,v
1
),(v
s
,v
2
)}，截量为,6
② V
1
={v
s
,v
1
}，
截集为截集为 {(v
s
,v
2
),(v
1
,v
t
)}，截量为：7
③ V
1
={v
s
,v
2
}，
截集为截集为 {……}，截量为,7
④ V
1
={v
s
,v
3
}，
截集为截集为 {……}，截量为,12
⑤ V
1
={v
s
,v
1
,v
2
}，
截集为截集为 {……}，截量为：5
……
http://www.tju.edu.cn
第三章图与网络分析
v
1
v
s
v
2
v
3
v
t
（
2
，
2
）
（
4
，
3
）
（
3
，
1
）
（
1
，
0
）
（
3
，
3
）
（
5
，
2
）
（ 2,2）
（ 2） 最小截量 min C (V1,V2)= 5；
（ 3） ∵ v(f
*
)=5= min C (V1,V2)
∴ f
*
是最大流。
http://www.tju.edu.cn
第三章图与网络分析
4、求最大流方法
、求最大流方法
——标号法标号法理论依据：
不存在关于f 的增广链可行流 f是最大流思路：从始点开始标号，寻找是否存在增广链。
给 v
j
标号为 [θ
j
,v
i
]，其中θ
j
为调整量,v
i
为前一节点。
步骤,(1)给 v
s
标号为[∞,v
s
]，
流出未饱和弧(v
s
,v
j
),给 v
j
标号[θ
j
,v
s
],其中 θ
j
=c
sj
-f
sj
例例
10,图中网络弧旁数字为图中网络弧旁数字为 (c
ij
,
f
ij
)，用标号法求最大流。
[∞,v
s
]
[4,v
s
]
选与v
s
关联的
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
（
3
,
0
）
http://www.tju.edu.cn
第三章图与网络分析
(2)把节点集V 分为
V
A
：已标号点集
V
B
：未标号点集
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
（
3
,0
）
http://www.tju.edu.cn
第三章图与网络分析考虑所有弧 (v
i
,v
j
)或 (v
j
,v
i
),其中v
i
∈ V
A
,v
j
∈ V
B
，若该弧为流出未饱弧,则给 v
j
标号 [θ
j
,v
i
],其中θ
j
=c
ij
-f
ij
流入非零弧,则给 v
j
标号 [θ
j
,-v
i
],其中θ
j
= f
ij
(3)
[1,-v
1
]
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
（
3
,
0
）
http://www.tju.edu.cn
第三章图与网络分析
(4)
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
[1,-v
1
]
重复（ 2）,（ 3），依次进行的结局可能为
（
3
,
0
）
v
t
已标号，得到一条增广链u( 反向追踪 )，转（5）；
v
t
未标号，且无法再标号,此时的流为最大流,此时的截集 为 最小截。
http://www.tju.edu.cn
第三章图与网络分析
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
[1,-v
1
]
(4) 重复（ 2）,（ 3），依次进行的结局可能为
v
t
已标号，得到一条增广链u( 反向追踪 )，转（5）；
v
t
未标号，且无法再标号,此时的流为最大流,此时的截集 为 最小截。
[1,v
2
]
（
3
,
0
）
http://www.tju.edu.cn
第三章图与网络分析
(4) 重复（ 2）,（ 3），依次进行的结局可能为
v
t
已标号，得到一条增广链u( 反向追踪 )，转（5）；
v
t
未标号，且无法再标号,此时的流为最大流,此时的截集 为 最小截。
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
[1,-v
1
][1 v
2
]
（
3
,
0
）
[2,v
4
]
http://www.tju.edu.cn
第三章图与网络分析
(4) 重复（ 2）,（ 3），依次进行的结局可能为
v
t
已标号，得到一条增广链u( 反向追踪 )，转（5）；
v
t
未标号，且无法再标号,此时的流为最大流,此时的截集 为 最小截。
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
[1,-v
1
][1 v
2
]
（
3
,
0
）
[2,v
4
]
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
[1,-v
1
][1
2
]
（
3
,
0
）
[1,-v
2
]
[2,v
4
]
(5) 调整。取
}{min
j
uv
j
θθ
∈
=
，令
∈?
∈+
=
+
uvvf
uvvf
uvvf
f
jiij
jiij
jiij
ij
),(
),(
),(
'
θ
θ
，得新流
}{
'
ij
f
,转 (1)。
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
1
）
（
1
,
1
）
（ 2,2）
（
1
,
1
）
（
5
,
3
）
（
2
,
1
）
（ 4,3）
[∞,v
s
]
[4,v
s
]
[1,-v
1
][1-v
2
]
（
3
,
0
）
[1,-v
2
]
[2,v
4
]
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
2
）
（
1
,
0
）
（ 2,2）
（
1
,
1
）
（
5
,
4
）
（
2
,
1
）
（ 4,4）
（
3
,
0
）
调整
http://www.tju.edu.cn
第三章图与网络分析
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
2
）
（
1
,
0
）
（ 2,2）
（
1
,
1
）
（
5
,
4
）
（
2
,
1
）
（ 4,4）
（
3
,
0
）
[∞,v
s
]
[3,v
s
]
http://www.tju.edu.cn
第三章图与网络分析
v
2
V
s
v
1
v
4
v
3
V
t
（
3
,
3
）
（
5,
2
）
（
1
,
0
）
（ 2,2）
（
1
,
1
）
（
5
,
4
）
（
2
,
1
）
（ 4,4）
（
3
,
0
）
[∞,v
s
]
[3,v
s
]
此时标号无法进行，当前流为最大流，最大流量为
5；最小截为{(v
s
,v
2
),(v
1
,v
3
)}，截量为：5
http://www.tju.edu.cn
第三章图与网络分析例 11,图中 A,B,C,D,E,F分别表示陆地和岛屿，①
② ……⒁表示桥梁及其编号。河两岸分别互为敌对的双方部队占领，问至少应切断几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的。试用图论方法进行分析。
A
B
D
E
F
C
①
②
③
④
⑤
⑥
⑦
⑧
⑨
⑩
⑾
⑿
⒀⒁
分析：转化为一个网络图，
弧的容量为两点间的桥梁数。
则问题为求最小截。
A
B
D
E
F
C
①
②
③
④ ⑤
⑥
⑦
⑧
⑨
⑩
⑾
⑿
⒀⒁
A
B
C
D
E
F
2
1
1
1
1
1
2
2
2
2
2
2
分析：转化为一个网络图，
弧的容量为两点间的桥梁数。
答案：最小截为{AE、
CD,CF}
则问题为求最小截。
A
B
D
E
F
C
①
②
③
④ ⑤
⑥
⑦
⑧
⑨
⑩
⑾
⑿
⒀⒁
A
B
C
D
E
F
2
1
1
1
1
1
2
2
2
2
2
2
http://www.tju.edu.cn
第三章图与网络分析例12,有一批人从我国A城赴俄罗斯B城，可能的旅行路线如图：
边防队拟建立足够数量检查站以便使每辆汽车至少必经过一个检查站，建立检查站的费用根据各路段条件有所不同（如图数字所示），求最小费用解。
a
BA b
c
d
e
f
g
4
6
8
2
3
2
5
7
3
8
4
3
7
6
4
（分析：最小截问题）
http://www.tju.edu.cn
第三章图与网络分析引例：沏茶
1 3
2
4
烧水（ 10）
备茶
（ 3）
沏茶（ 2）
洗碗
（
2
）
3.3 网络计划
http://www.tju.edu.cn
第三章图与网络分析
1、问题描述一项工程，已知各工序完成时间t 及其先后关系求：工程完工期及关键工序关键工序：主矛盾工序，不能延期完工路线,从始点到终点的一条路关键路线：由关键工序组成的路线，是所有路线中时间最长的路线。
相关概念：
1 3
2
4
烧水（ 10）
备茶
（ 3）
沏茶（ 2）
洗碗
（
2
）
http://www.tju.edu.cn
第三章图与网络分析
2,求解方法—— 关键路径法（CPM）
分为三步：
? 绘制工程网络图
? 标号法求工期 T
? 标号法求关键路线
http://www.tju.edu.cn
第三章图与网络分析
? 将整个工程分解为若干工序
? 确定各工序的前后顺序（紧前、紧后）
? 确定工序完成时间三点估计法：最乐观时间 a、最可能时间 m、最悲观时间b
t
ij
=
6
a+4m+b
一点估计法准备工作
（ 1）绘制工程网络图
1）顺序：按工序的先后从左至右
2）图的结构弧：
i
j
表示工序，
i
j
、
为工序的起点、终点结点,相邻工序的时间分界点，称为事项权,工序的完成时间相邻弧,工序的前后衔接关系，称为紧前或紧后工序
3）绘图要求图中不能出现缺口、回路和多重边多重边的处理：
1 2
a
b
1 2
a
3
b
b '
虚工序
1 3
2
4
烧水
（ 10）
备茶
（ 3）
沏茶（ 2）
洗碗
（
2
）
http://www.tju.edu.cn
第三章图与网络分析例 13 某工厂进行技术改造，需要拆掉旧厂房、
建造新厂房和安排设备。这项改建工程可以分解为 7道工序，其相关资料如下表：
工序代号 工序名称 紧前工序 工序时间（周）
A
拆迁
/2
B
工程设计
/3
C
土建工程设计
B2.5
D
采购设备
B6
E
厂房土建
C,A20
F
设备安装
D,E4
G
设备调试
F2
http://www.tju.edu.cn
第三章图与网络分析
1
2
3
4 5
A（ 2）
B (3)
C (2.5)
D (6)
E (20)
F (4)
6
G (2)
工序代号 工序名称 紧前工序 工序时间（周）
A 拆迁 /2
B 工程设计 /3
C 土建工程设计 B2.5
D 采购设备 B6
E 厂房土建 C,A20
F 设备安装 D,E4
G 设备调试 F2
解：
工序代号 紧前工序工序时间（周）
A/ 2
B/ 3
C/ 2
DA 3
EA 4
工序代号 紧前工序工序时间（周）
FB 7
G 6
HD,E4
IB,C10
JG,I3
例 14,绘制工程网络图续左表解：
1
A (2)
D (3)
C (2)
2
E (4)
3
F(7)
B '(0)
G(6)
4
5
E'(0)
6
I (10)
7
J(3)
H (4)
8
B (3)
http://www.tju.edu.cn
第三章图与网络分析
② 四个工序 A,B,X,Y有如下关系：
A是 X的紧前工序，A和 B同时又是Y 的紧前工序
1 2 3
4 5 6
A
B
X
Y
A '
虚工序两种情况需要引入虚工序：
1 2
A
B
1 2
A
3
B
虚工序
① 两个工序A,B有相同的始点和终点
B '
http://www.tju.edu.cn
第三章图与网络分析练习,P150习题6.1
1
60
2
3
4
7
5
6 8 9 10
11 12 13 14
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
14
20
30
21
10
7
12
25
5
10
60
10
15 2 5
7
f '
b '
（ 2）用标号法求工期 T
步骤：
E
j
Ⅱ,给任意事项
j
标
，
E
j
=max{以
ij
t,}
为箭头的各箭之,箭尾
j
+箭长
（ 1）标出各事项的最早开始时间
（ 2）终点即为工期
n
的标号 T
1
A (2)
D (3)
C (2)
2
E (4)
3
F(7)
B '(0)
G(6)
4
5
E'(0)
6
I (10)
7
J(3)
H (4)
8
B (3)
0
2
3
3
6
6
13
16
Ⅰ、给始点①标
0
（ 3）用标号法求关键路线步骤：
1
A (2)
D (3)
C (2)
2
E (4)
3
F(7)
B '(0)
G(6)
4
5
E'(0)
6
I (10)
7
J(3)
H (4)
8
B (3)
0
2
3
3
6
6
13
16
（ 1）标出各事项的最晚开始时间
T
Ⅰ、给终点
n
标
L
i
=min{以
ij
t,}
为箭尾的各箭之,箭头 －箭长
Ⅱ,给任意事项
i 标
，
L
i
i
16
12
12
8
13
3
3
0
1
A (2)
D (3)
C (2)
2
E (4)
3
F(7)
B '(0)
G(6)
4
5
E'(0)
6
I (10)
7
J(3)
H (4)
8
B (3)
0
2
3
3
6
6
13
16
T
16
12
12
8
13
3
3
0
R
ij
= j
的
－ i 的 －
ij
t
（ 2）计算各工序
i
j 的时差 R
ij
：
则关键工序为R
ij
=0的工序。
注：关键工序头尾皆有
=
（反之未必成立）
http://www.tju.edu.cn
第三章图与网络分析练习,P150习题6.1
1
60
2
3
4
7
5
6 8 9 10
11 12 13 14
a
b
c
d
e
f
g
h
i
j
k
l
m
n
o
p
q
14
20
30
21
10
7
12
25
5
10
60
10
15 2 5
7
b '
f '
152
http://www.tju.edu.cn
第三章图与网络分析
3、工程工期的概率分析 ——计划评审技术（PERT ）
? PERT与 CPM的主要区别：
CPM工序时间是确定的；
),(~
2
σ
E
TNT
PERT工序时间 t
ij
是随机变量，而完工期 T 也是随机的，由概率知识,T 服从正态分布
T
Τ
Ε
http://www.tju.edu.cn
第三章图与网络分析
? 确定平均工序时间的三点估计法：
6
4
ijijij
ij
bma
t
++
=
2
2
6
=
ijij
ij
ab
σ
? 总工期 ),(~
2
σ
E
TNT
其中：
∑
∈
=
Iji
ijE
tT
),(
（ I 为关键路线）
∑
∈
=
Iji
ij
),(
22
σσ
)1,0(~ N
TT
E
σ
λ
=
T
Τ
Ε
标准化
http://www.tju.edu.cn
第三章图与网络分析
1,给定时间T
*
，求工期T ≤ T
*
内完工的概率
? PERT的主要问题方法：首先计算
σ
λ
E
TT?
=
*
*
，
∫
∞?
=≤=≤
*
2
d
2
1
*}{*}{
2
λ
π
λλ tePTTP
t
0
*
λ
λ
：阴影面积*)(λΦ
)(1)( λΦλΦ?=?
)(λΦ然后查表求
。
*)(
Δ
λΦ=
9
12.83
7.83
8.17
4
10.33
12.17
11
A
B
C
D
E
F
G
H
21
3 5
7
64
例 15、已知某工程网络图，以及各工序的时间参数。
工序
amb
A10
5
7
7
2
F 8 10 14
G101215
H 9 11 13
B
1513
8
8C
9
10
10
11D
E64
T
E
=42.33
0.44
/
1.00
/
/
0.25
/
0.69
2
ij
σ
11
12.17
10.33
4
9
8.17
7.83
12.83
t
ij
求工程在40 天内完工的概率。
关键路线I 为,A→ C→ F→ H；
∑
∈
=
Iji
ij
),(
22
σσ
38.2=
σ
λ
E
TT?
=
*
*
51.1
54.1
33.4240
=
=
解：
}40{ ≤TP
066.0)51.1( =?=Φ
http://www.tju.edu.cn
第三章图与网络分析
2,给定概率p,求完工可能性为 p的工期方法：首先查表求
*
λ
，使
p=*)(λΦ；
再由
σ
λ
E
TT?
=
*
*
*
T解出例、上例中，求完工可能性达95% 的工期。
95.0*)( =λΦ
解：由
，
查表；6.1
*
=λ
再由
54.1
33.42
**
*
=
=
TTT
E
σ
λ
解出
45
*
=T
