?管理与人文学院 忻展红
1999,4
第六章 图与网路分析
图是最直观的模型
2
B
A
C
D
图论 Graph Theory
? 哥尼斯堡七桥问题 (K?nigsberg Bridge Problem)
? Leonhard Euler (1707-1783) 在 1736年发表第一篇图论
方面的论文，奠基了图论中的一些基本定理
? 很多问题都可以用点和线来表示，一般点表示实体，
线表示实体间的关联
A
B
C D
3
6.1 图与网路的基本概念
6.1.1 图与网路
? 节点 (Vertex)
– 物理实体、事物、概念
– 一般 用 vi表示
? 边 (Edge)
– 节点间的连线，表示有
关联
– 一般 用 eij 表示
? 图 (Graph)
– 节点和边的集合
– 一般用 G(V,E) 表示
– 点集 V={v1,v2,…,vn}
– 边集 E={eij }
v
1
v
5
v
4
v
3
v
2
e
12
e
34
e
13
e
24
e
22
e'
13
e
45
图 6.1
网路 (Network)
边上具有表示连接强度
的权值，如 wij
又称 加权图 (Weighted
graph)
4
6.1.2 无向图与有向图
? 所有边都没有方向的图称为无向图，如图 6.1
? 在无向图中 eij=eji，或 (vi,vj)=(vj,vi)
? 当所有边都有方向时，称为有向图，用 G(V,A)表示
? 在有向图中，有向边又称为 弧,用 aij表示,i,j 的顺序
是不能颠倒的，图中弧的方向用箭头标识
? 图中既有边又有弧，称为混合图
6.1.3 端点，关联边，相邻，次
? 图中可以只有点，而没有边；而有边必有点
? 若节点 vi,vj 之间有一条边 eij，则称 vi,vj 是 eij 的 端点
(end vertex)，而 eij 是节点 vi,vj 的 关联边 (incident edge)
? 同一条边的两个端点称为 相邻 (adjacent)节点,具有共同
端点的边称为 相邻边
? 一条边的两个端点相同，称为 自环 (self-loop)；具有两
个共同端点的两条边称为 平行边 (parallel edges)
? 既没有自环也没有平行边的图称为 简单图 (simple graph)
? 在无向图中，与节点相关联边的数目，称为该节点的
,次, (degree),记为 d ；次数为奇数的点称为 奇点
(odd),次数为偶数的点称为 偶点 (even)；图中都是偶点的
图称为偶图 (even graph)
6
6.1.3 端点，关联边，相邻，次
? 有向图中，由节点向外指的弧的数目称为正次数，记
为 d+，指向该节点的弧的数目称为负次数，记为 d–
? 次数为 0 的点称为 孤立点 (isolated vertex),次数为 1 的
点称为 悬挂点 (pendant vertex)
定理 1：图中奇点的个数总是偶数个
6.1.4 链，圈，路径，回路，欧拉回路
? 相邻节点的序列 {v1?,v2?,…,vn?} 构成一条 链 (link)，又称
为 行走 (walk)；首尾相连的链称为 圈 (loop)，或 闭行走
? 在无向图中，节点不重复出现的链称为 路径 (path)；在
有向图中，节点不重复出现且链中所有弧的方向一致，
则称为 有向路径 (directed path)
? 首尾相连的路径称为 回路 (circuit)；
7
? 走过图中所有边且每条边仅走一次的闭行走称为 欧拉
回路
定理 2：偶图一定存在欧拉回路 (一笔画定理 )
6.1.5 连通图，子图，成分
? 设有两个图 G1(V1,E1),G2(V2,E2),若 V2 ?V1,E2 ?E1，
则 G2 是 G1 的子图
? 无向图中，若任意两点间至少存在一条路径，则称为
连通图 (connected graph)，否则为 非连通图 ( discon-
nected graph)；非连通图中的每个 连通子图 称为 成分
(component)
? 链，圈，路径 (简称路 )，回路都是原图的子图
? 平面图 (planar graph)，若在平面上可以画出该图而没
有任何边相交
8
6.2 树 图与最小生成树
? 一般研究无向图
? 树图：倒臵的树,根 (root)在上,树叶 (leaf)在下
? 多级辐射制的电信网络、管理的指标体系、家谱、分
类学、组织结构等都是典型的树图
C1
C2
C3
C4
根
叶
9
6.2.1 树的定义及其性质
? 任两点之间有且只有一条路径的图称为 树 (tree)，记为 T
树的性质,
? 最少边的连通子图，树中必不存在回路
? 任何树必存在次数为 1 的点
? 具有 n 个节点的树 T 的边恰好为 n?1 条，反之，任何有
n 个节点,n?1 条边的连通图必是一棵树
6.2.2 图的生成树
? 树 T 是连通图 G 的 生成树 (spanning tree)，若 T 是 G的
子图且包含图 G 的所有的节点；包含图 G 中部分指定节
点的树称为 steiner tree
? 每个节点有唯一标号的图称为标记图，标记图的生成树
称为 标记树 (labeled tree)
Caylay 定理, n (?2)个节点，有 nn?2个不同的 标记树
10
6.2.2 图的生成树
? 如何找到一棵生成树
– 深探法 (depth first search)：任选一点标记为 0 点开始搜
索，选一条未标记的边走到下一点，该点标记为 1，将
走过的边标记；假设已标记到 i点，总是从最新标记的
点向下搜索，若从 i 点无法向下标记，即与 i 点相关联
的边都已标记或相邻节点都已标记，则退回到 i ?1 点继
续搜索，直到所有点都被标记
– 广探法 (breadth first search)：是一种有层级结构的搜索，
一般得到的是树形图
A C
DB
A C
DB
A C
DB
A
D
C
B
11
6.2.3 最小生成树
? 有 n 个乡村，各村间道路的长度是已知的，如何敷设光
缆线路使 n 个乡村连通且总长度最短
? 显然，这要求在已知边长度的网路图中找最小生成树
最小生成树的算法,
? Kruskal 算法：将图中所有边按权值从小到大排列，依
次选所剩最小的边加入边集 T,只要不和前面加入的边
构成回路，直到 T 中有 n?1 条边，则 T 是最小生成树
? Kruskal 算法基于下述定理
定理 3 指定图中任一点 vi，如果 vj 是距 vi 最近的相邻节点，
则关联边 eij 必在某个最小生成树中。
推论 将网路中的节点划分为两个不相交的集合 V1和 V2，
V2=V?V1，则 V1和 V2间权值最小的边必定在某个最小生
成树中。
12
6.2.3 最小生成树
? 最小生成树不一定唯一
? 定理 3 推论是一个构造性定理，它指示了找最小生成树
的有效算法
? Prim 算法：不需要对边权排序，即可以直接在网路图上
操作，也可以在边权矩阵上操作，后者适合计算机运算
边权矩阵上的 Prim 算法,
1、根据网路写出边权矩阵，两点间若没有边，则用 ?表示；
2、从 v1 开始标记，在第一行打 ?,划去第一列；
3、从所有打 ? 的行中找出尚未划掉的最小元素，对该元素画圈，
划掉该元素所在列，与该列数对应的行打 ? ；
4、若所有列都划掉，则已找到最小生成树 (所有画圈元素所对应
的边 )；否则，返回第 3 步。
? 该算法中，打 ? 行对应的节点在 V1中，未划去的列在 V2中
13
6.2.3 最小生成树
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
??
??
???
?
97125.1917
9810
78711
1275.916
5.195.910
1710111610
? Prim算法是多项式算法
? Prim算法可以求最大生成树
? 网路的边权可以有多种解释，如效率
? 次数受限的最小生成树 —尚无有效算法
? 最小 Steiner 树 —尚无有效算法
v
1
v
4
v
6
v
3
v
5
v
2
10
10
8
11
7
7
16
9.5
17
12
9
19.5
?
?
?
?
?
?
14
6.3 最短路问题
6.3.1 狄克斯特拉算法 (Dijkstra algorithm,1959)
? 计算两节点之间或一个节点到所有节点之间的最短路
令 dij 表示 vi 到 vj 的直接距离 (两点之间有边 )，若两点之间
没有边，则令 dij = ?，若 两点之间是有向边，则 dji = ?；
令 dii = 0,s 表示始点,t表示终点
0、令 始点 Ts=0，并用 框住,所有其它节点临时标记 Tj=? ；
1、从 vs 出发，对其相邻节点 vj1进行临时标记，有 Tj1=ds,j1；
2、在所有临时标记中找出最小者,并用 框住，设其为 vr 。若
此时全部节点都永久标记，算法结束 ；否则到下一步；
3、从新的永久标记节点 vr 出发，对其相邻的临时标记节点进行
再标记，设 vj2为其相邻节点，则 Tj2=min{Tj2,Tr+dr,j2 }，返回
第 2步。
15
例 1 狄克斯特拉算法
2
s
5
t
6
3
4
10
7
4
9
1
8
8
15
2
20
2
30
0
?
?
? ?
?
?
8
15
10
12
15
11
31
13
16
Dijkstra最短路算法的 特点 和 适应范围
? 一种隐阶段的动态规划方法，而且是正向递推
? 每次迭代只有一个节点获得永久标记，若有两个或两个以上
节点的临时标记同时最小，可任选一个永久标记；总是从一
个新的永久标记开始新一轮的临时标记，是一种 深探法
? 被框住的永久标记 Tj 表示 vs 到 vj 的最短路，因此 要求 dij?0，
第 k 次迭代得到的永久标记，其最短路中最多有 k条边，因
此最多有 n?1次迭代
? 可以应用于 简单 有向图和混合图，在临时标记时，所谓相邻
必须是箭头指向的节点；若第 n?1次迭代后仍有节点的标记
为 ?，则表明 vs 到该节点无有向路径
? 如果只求 vs 到 vt 的最短路，则当 vt 得到永久标记算法就结束
了；但算法复杂度是一样的
? 应用 Dijkstra 算法 n?1 次,可以求所有点间的最短路
? vs 到所有点的最短路也是一棵生成树，但不是最小生成树
17
6.3.2 Warshall-Floyd算法 (1962)
? Warshall-Floyd算法可以解决有 负权值 边 (弧 )的最短路问题
? 该算法是一种整体算法，一次求出所有点间的最短路
? 该算法不允许有 负权值回路,但可以发现负权值回路
? 该算法基于基本的三角运算
定义 对给定的点间初始距离矩阵 {dij}，令 dii=?,?i。对一
个固定点 j，运算 dik=min{dik,dij+djk},? i,k ? j,称为 三角
运算。 (注意，这里允许 i=k)
定理 依次对 j=1,2,…,n 执行三角运算，则 dik 最终等于 i 到
k 间最短路的长度。
k
j
i
d
ij
d
jk
d
ik
18
6.3.2 Floyd-Warshall 算法 (1962)
for i=1 to n do dii=?;
for all eij=0;
for j=1 to n do
for i=1 to n do if i?j then
for k=1 to n do if k?j then
begin
dik=min{dik,dij+djk};
if dik>dij+djk then eik=j
end;
例 1 中 1 到 7 点的最短路是 1 - 2 - 5 - 7
查伴随矩阵 E 的第一行
1 2 3 4 5 6 7
1 0 0 2 0 2 5 5
? 若网路中存在负回路，则计算
中，某些 dii 会小于 0，此时应
中断算法
? 显然,Floyd 算法要进行
n(n-1)2 次加法和比较
? 如何回溯找出任两点之间的最
短路？
? 在 Floyd 算法中设一伴随矩阵
E={eik},eik 记录了 i到 k 最短
路中最后一个中间节点
19
小结
? 最短路有广泛的应用 (6.3.4节 市话局扩容方案 )
? 最短路的多种形式：无向图，有向图无循环圈，有向
图，混合图，无负边权，有负边权，有负回路,k-最
短路等
? 当存在负权值边时,Floyd算法比 Dijkstra算法效率高，
且程序极简单。但 Dijkstra算法灵活
? 若图是前向的，则 Dijkstra算法也可以求两点间最长路
? 一般情况下，两点间最长路是 NP-complete，但最短
路是 P算法
? 两点间 k-最短路：分为边不相交的和边相交的
求边 不相交的 k-最短路非常容易：先求最短路，将该
最短路中的边从网路删去，再用 Dijkstra算法可求次最
短路，以此类推
20
6.3.4 最短路应用举例 ——市话扩容 (实装率 =0.8)
?ê o? 0 1 2 3 4 5 6 7 8 9 10 11 12
?¤2a êy 1,6 1,8 2,0 2,2 2,5 2,8 3,1 3,5 3,9 4,4 4,9 5,5 6,2
t
0
2000
t
6
4000
t
8
5000
t
9
6000
t
11
7000
t
12
8000
t
3
3000
1,4
2,7
6,13
5,12
4,8,8
3,8,3
1,3,5
2,6,0
4,8,3
3,7,1
5,8,9
1,3
2,4,5
3,6,8
4,7,5
1,2,5
2,4,3
3,5,5
21
最短路应用举例 —市话扩容
0 3 6 121198
4
12
8.8
7
22.32.533.5
8.9
8.3
7.1
6
4
7.5
6.8
4.5
8.3
13
5.5
4.3
22
6.4 网路的最大流和最小截
6.4.1 网路的最大流的概念
? 网路流一般在有向图上讨论
? 定义网路上支路的 容量 为其最大通过能力，记为 cij,
支路上的实际 流量 记为 fij
? 图中规定一个发点 s，一个收点 t
? 节点没有容量限制，流在节点不会存储
? 容量限制条件, 0?fij ? cij
? 平衡条件,
?
?
?
?
?
??
?
?
?? ??
??
tifv
tsi
sifv
ff
ijij vBv
ji
vAv
ij
)(
,0
)(
)()(
? 满足上述条件的网路流称为 可行流,总存在 最大可行流
? 当支路上 fij = cij,称为 饱和弧
? 最大流问题也是一个线性规划问题
vi A(v
i)B(vi)
23
6.4.2 截集与截集容量
定义,把网路分割为两个成分的弧的最小集合，其中一
个成分包含 s 点，另一个包含 t 点 。
? 一般包含 s 点的成分中的节点集合用 V表示，包含 t 点
的成分中的节点集合用 V表示
? 截集容量 是指截集中正向弧的容量之和
?
?
?
?
Vj
Vi ij
cVVC ),(
? 福特 -富克森定理,网路的最大流等于最小截集容量。
当达到最大流时，最小截集中的反向弧流量必为零
s t
53
42
( 4,0 )
( 3,0 )
( 2,0 )
( 1,0 )( 1,0 )
( 5,0 )
( 3,0 )
( 2,0 )
( 5,0 )
24
6.4.3 确定网路最大流的标号法
? 从任一个初始可行流出发，如 0 流
? 基本算法：找一条从 s 到 t 点的 增广链 (augmenting path)
? 若在当前可行流下找不到增广链，则已得到最大流
? 增广链中与 s 到 t 方向一致的弧称为 前向弧,反之 后向弧
? 增广过程：前向弧 f?ij=fij +q,后向弧 f?ij=fij ?q
? 增广后仍是可行流
s t5432
( 3,0 ) ( 5,3 )( 1,1 )( 5,1 ) ( 1,1 )
q
s2
= 4 q
5t
= 2q
45
= 3q
43
= 1q
32
= 1
增广量 q = m in
q
ij
= m in ( 4,1,1,3,2) = 1
s t5432
( 3,1 ) ( 5,4 )( 1,0 )( 5,2 ) ( 1,0 )
?
?
? ?
?
后向弧
前向弧
ij
ijij
ij
f
fc
q
25
最大流最小截的标号法步骤
第一步：标号过程，找一条增广链
1,给源点 s 标号 [s+,q(s)=?]，表示从 s 点有无限流出潜力
2,找出与已标号节点 i 相邻的所有未标号节点 j，若
(1) (i,j)是前向弧且饱和，则节点 j 不标号；
(2) (i,j)是前向弧且未饱和，则节点 j 标号为 [i+,q(j)]，表示从节点 i 正
向 流出，可增广 q(j)=min[q(i),cij?fij] ；
(3) (j,i)是后向弧，若 fji=0，则节点 j 不标号；
(4) (j,i)是后向弧，若 fji>0，则节点 j 标号为 [i?,q(j)]，表示从节点 j 流
向 i,可增广 q(j)=min[q(i),fji] ；
3,重复步骤 2，可能出现两种情况：
(1) 节点 t 尚未标号，但无法继续标记，说明网路中已不存在增广链，
当前流 v(f) 就是最大流；所有获标号的节点在 V 中，未获标号节
点在 V 中,V 与 V 间的弧即为最小截集；算法结束
(2)节点 t 获得标号，找到一条增广链，由节点 t 标号回溯可找出该增
广链；到第二步
26
最大流最小截的标号法步骤
第二步：增广过程
1、对 增广链中的前向弧，令 f?=f+q(t),q(t) 为节点 t 的标记值
2,对 增广链中的后向弧，令 f?=f?q(t)
3、非增广链上的所有支路流量保持不变
第三步：抹除图上所有标号，回到第一步
? 以上算法是按广探法描述的，但在实际图上作业时，按深
探法进行更快捷
? 一次只找一条增广链，增广一次换一张图
? 最后一次用广探法，以便找出最小截集
27
最大流最小截集的标号法举例
s t
1
3 4
2 5
6
(14,
14)
(9,
9)
(15,9)
(16,15)
(3,
1)
(12,10)
(6,
6)
(4,3)
(5,
5)
(22,
22)
(13,
12)
(7,
5)(6,
3)
(19,
10)
s t
1
3 4
2 5
6
(14,
14)
(9,
9)
(15,10)
(16,15)
(3,
1)
(12,10)
(6,
5)
(4,4)
(5,
5)
(22,
22)
(13,
12)
(7,
5)(6,
3)
(19,
11)
(s+,?)
(s+,6)
(2?,6) (3+,1)
(4+,1)
(s+,?)
(s+,5)
(2+,2)
(5?,2)
(4+,2)
28
最大流最小截集的标号法举例
s t
1
3 4
2 5
6
(14,
14)
(9,
9)
(15,10)
(16,15)
(3,
1)
(12,10)
(6,
5)
(4,4)
(5,
5)
(22,
22)
(13,
12)
(7,
5)(6,
3)
(19,
11)
s t
1
3 4
2 5
6
(14,
14)
(9,
9)
(15,12)
(16,15)
(3,
1)
(12,12)
(6,
5)
(4,4)
(5,
5)
(22,
22)
(13,
12)
(7,
5)(6,
1)
(19,
13)
(s+,?)
(s+,3)
(2?,3)
最小截集
(4+,2)
29
最大流标号法的复杂度讨论 s t
v
u
20002000
20002000
1
? 找一条增广链的计算量是容易估计的，不会超过 O(n2)
? 但是最多迭代多少次 (即增广的次数 )就很难估计，在最坏情
况下，与边的容量有关；如上图：先增广 s ? u ? v ? t,
然后增广 s ? v ? u ? t，每次只能增广 1 个单位，故要增
广 4000次才能结束
? 克服这种缺点的经验方法：
– 尽量先用段数少的增广链
– 尽量不重复前面出现过的增广链
30
6.4.4 多端网路问题
1 8
7
6
4
3
52
(1 5,0 )
(1 0,0 )
(2 0,0 )
(5,0 )
(5,0 )
(5,0 )
(5,0 )
(5,0 )
(1 0,0 )
(1 0,0 )
(1 0,0 )
(1 0,0 )
发点 1
20
发点 2
20
收点 1
15
收点 2
20
(5,0 )
,1 )
(1 0,1 0 )
5
5
5
5
5
5
(1 0,1 0 )
5
虚发点
虚收点
s
t
(2 0,1 5 )
(2 0,1 5 )
(2 0,1 5 )
(1 5,1 5 )
(5,0 )
31
6.4.5 最小费用最大流
? 双权网路,每条弧不但有容量，还有单位流量的通过费用
? 两种解法：一种基于最小费用路径算法；一种基于可行弧集
的最大流算法
? 基于最小费用路径算法,总是在当前找到的最小费用的路径
上增广流；缺点是每次增广后要改变弧的费用，且出现负权
值费用的弧
? 基于可行弧集的最大流算法,从 0 费用弧集开始应用最大流
算法，然后根据计算信息提高费用的限界 P，使可行弧集增
大，再应用最大流算法，直至所有弧都进入可行弧集。这种
算法是一种主 -对偶规划的解法。使用这种方法的还有运输
问题、匹配问题
1999,4
第六章 图与网路分析
图是最直观的模型
2
B
A
C
D
图论 Graph Theory
? 哥尼斯堡七桥问题 (K?nigsberg Bridge Problem)
? Leonhard Euler (1707-1783) 在 1736年发表第一篇图论
方面的论文，奠基了图论中的一些基本定理
? 很多问题都可以用点和线来表示，一般点表示实体，
线表示实体间的关联
A
B
C D
3
6.1 图与网路的基本概念
6.1.1 图与网路
? 节点 (Vertex)
– 物理实体、事物、概念
– 一般 用 vi表示
? 边 (Edge)
– 节点间的连线，表示有
关联
– 一般 用 eij 表示
? 图 (Graph)
– 节点和边的集合
– 一般用 G(V,E) 表示
– 点集 V={v1,v2,…,vn}
– 边集 E={eij }
v
1
v
5
v
4
v
3
v
2
e
12
e
34
e
13
e
24
e
22
e'
13
e
45
图 6.1
网路 (Network)
边上具有表示连接强度
的权值，如 wij
又称 加权图 (Weighted
graph)
4
6.1.2 无向图与有向图
? 所有边都没有方向的图称为无向图，如图 6.1
? 在无向图中 eij=eji，或 (vi,vj)=(vj,vi)
? 当所有边都有方向时，称为有向图，用 G(V,A)表示
? 在有向图中，有向边又称为 弧,用 aij表示,i,j 的顺序
是不能颠倒的，图中弧的方向用箭头标识
? 图中既有边又有弧，称为混合图
6.1.3 端点，关联边，相邻，次
? 图中可以只有点，而没有边；而有边必有点
? 若节点 vi,vj 之间有一条边 eij，则称 vi,vj 是 eij 的 端点
(end vertex)，而 eij 是节点 vi,vj 的 关联边 (incident edge)
? 同一条边的两个端点称为 相邻 (adjacent)节点,具有共同
端点的边称为 相邻边
? 一条边的两个端点相同，称为 自环 (self-loop)；具有两
个共同端点的两条边称为 平行边 (parallel edges)
? 既没有自环也没有平行边的图称为 简单图 (simple graph)
? 在无向图中，与节点相关联边的数目，称为该节点的
,次, (degree),记为 d ；次数为奇数的点称为 奇点
(odd),次数为偶数的点称为 偶点 (even)；图中都是偶点的
图称为偶图 (even graph)
6
6.1.3 端点，关联边，相邻，次
? 有向图中，由节点向外指的弧的数目称为正次数，记
为 d+，指向该节点的弧的数目称为负次数，记为 d–
? 次数为 0 的点称为 孤立点 (isolated vertex),次数为 1 的
点称为 悬挂点 (pendant vertex)
定理 1：图中奇点的个数总是偶数个
6.1.4 链，圈，路径，回路，欧拉回路
? 相邻节点的序列 {v1?,v2?,…,vn?} 构成一条 链 (link)，又称
为 行走 (walk)；首尾相连的链称为 圈 (loop)，或 闭行走
? 在无向图中，节点不重复出现的链称为 路径 (path)；在
有向图中，节点不重复出现且链中所有弧的方向一致，
则称为 有向路径 (directed path)
? 首尾相连的路径称为 回路 (circuit)；
7
? 走过图中所有边且每条边仅走一次的闭行走称为 欧拉
回路
定理 2：偶图一定存在欧拉回路 (一笔画定理 )
6.1.5 连通图，子图，成分
? 设有两个图 G1(V1,E1),G2(V2,E2),若 V2 ?V1,E2 ?E1，
则 G2 是 G1 的子图
? 无向图中，若任意两点间至少存在一条路径，则称为
连通图 (connected graph)，否则为 非连通图 ( discon-
nected graph)；非连通图中的每个 连通子图 称为 成分
(component)
? 链，圈，路径 (简称路 )，回路都是原图的子图
? 平面图 (planar graph)，若在平面上可以画出该图而没
有任何边相交
8
6.2 树 图与最小生成树
? 一般研究无向图
? 树图：倒臵的树,根 (root)在上,树叶 (leaf)在下
? 多级辐射制的电信网络、管理的指标体系、家谱、分
类学、组织结构等都是典型的树图
C1
C2
C3
C4
根
叶
9
6.2.1 树的定义及其性质
? 任两点之间有且只有一条路径的图称为 树 (tree)，记为 T
树的性质,
? 最少边的连通子图，树中必不存在回路
? 任何树必存在次数为 1 的点
? 具有 n 个节点的树 T 的边恰好为 n?1 条，反之，任何有
n 个节点,n?1 条边的连通图必是一棵树
6.2.2 图的生成树
? 树 T 是连通图 G 的 生成树 (spanning tree)，若 T 是 G的
子图且包含图 G 的所有的节点；包含图 G 中部分指定节
点的树称为 steiner tree
? 每个节点有唯一标号的图称为标记图，标记图的生成树
称为 标记树 (labeled tree)
Caylay 定理, n (?2)个节点，有 nn?2个不同的 标记树
10
6.2.2 图的生成树
? 如何找到一棵生成树
– 深探法 (depth first search)：任选一点标记为 0 点开始搜
索，选一条未标记的边走到下一点，该点标记为 1，将
走过的边标记；假设已标记到 i点，总是从最新标记的
点向下搜索，若从 i 点无法向下标记，即与 i 点相关联
的边都已标记或相邻节点都已标记，则退回到 i ?1 点继
续搜索，直到所有点都被标记
– 广探法 (breadth first search)：是一种有层级结构的搜索，
一般得到的是树形图
A C
DB
A C
DB
A C
DB
A
D
C
B
11
6.2.3 最小生成树
? 有 n 个乡村，各村间道路的长度是已知的，如何敷设光
缆线路使 n 个乡村连通且总长度最短
? 显然，这要求在已知边长度的网路图中找最小生成树
最小生成树的算法,
? Kruskal 算法：将图中所有边按权值从小到大排列，依
次选所剩最小的边加入边集 T,只要不和前面加入的边
构成回路，直到 T 中有 n?1 条边，则 T 是最小生成树
? Kruskal 算法基于下述定理
定理 3 指定图中任一点 vi，如果 vj 是距 vi 最近的相邻节点，
则关联边 eij 必在某个最小生成树中。
推论 将网路中的节点划分为两个不相交的集合 V1和 V2，
V2=V?V1，则 V1和 V2间权值最小的边必定在某个最小生
成树中。
12
6.2.3 最小生成树
? 最小生成树不一定唯一
? 定理 3 推论是一个构造性定理，它指示了找最小生成树
的有效算法
? Prim 算法：不需要对边权排序，即可以直接在网路图上
操作，也可以在边权矩阵上操作，后者适合计算机运算
边权矩阵上的 Prim 算法,
1、根据网路写出边权矩阵，两点间若没有边，则用 ?表示；
2、从 v1 开始标记，在第一行打 ?,划去第一列；
3、从所有打 ? 的行中找出尚未划掉的最小元素，对该元素画圈，
划掉该元素所在列，与该列数对应的行打 ? ；
4、若所有列都划掉，则已找到最小生成树 (所有画圈元素所对应
的边 )；否则，返回第 3 步。
? 该算法中，打 ? 行对应的节点在 V1中，未划去的列在 V2中
13
6.2.3 最小生成树
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
?
???
??
??
???
?
97125.1917
9810
78711
1275.916
5.195.910
1710111610
? Prim算法是多项式算法
? Prim算法可以求最大生成树
? 网路的边权可以有多种解释，如效率
? 次数受限的最小生成树 —尚无有效算法
? 最小 Steiner 树 —尚无有效算法
v
1
v
4
v
6
v
3
v
5
v
2
10
10
8
11
7
7
16
9.5
17
12
9
19.5
?
?
?
?
?
?
14
6.3 最短路问题
6.3.1 狄克斯特拉算法 (Dijkstra algorithm,1959)
? 计算两节点之间或一个节点到所有节点之间的最短路
令 dij 表示 vi 到 vj 的直接距离 (两点之间有边 )，若两点之间
没有边，则令 dij = ?，若 两点之间是有向边，则 dji = ?；
令 dii = 0,s 表示始点,t表示终点
0、令 始点 Ts=0，并用 框住,所有其它节点临时标记 Tj=? ；
1、从 vs 出发，对其相邻节点 vj1进行临时标记，有 Tj1=ds,j1；
2、在所有临时标记中找出最小者,并用 框住，设其为 vr 。若
此时全部节点都永久标记，算法结束 ；否则到下一步；
3、从新的永久标记节点 vr 出发，对其相邻的临时标记节点进行
再标记，设 vj2为其相邻节点，则 Tj2=min{Tj2,Tr+dr,j2 }，返回
第 2步。
15
例 1 狄克斯特拉算法
2
s
5
t
6
3
4
10
7
4
9
1
8
8
15
2
20
2
30
0
?
?
? ?
?
?
8
15
10
12
15
11
31
13
16
Dijkstra最短路算法的 特点 和 适应范围
? 一种隐阶段的动态规划方法，而且是正向递推
? 每次迭代只有一个节点获得永久标记，若有两个或两个以上
节点的临时标记同时最小，可任选一个永久标记；总是从一
个新的永久标记开始新一轮的临时标记，是一种 深探法
? 被框住的永久标记 Tj 表示 vs 到 vj 的最短路，因此 要求 dij?0，
第 k 次迭代得到的永久标记，其最短路中最多有 k条边，因
此最多有 n?1次迭代
? 可以应用于 简单 有向图和混合图，在临时标记时，所谓相邻
必须是箭头指向的节点；若第 n?1次迭代后仍有节点的标记
为 ?，则表明 vs 到该节点无有向路径
? 如果只求 vs 到 vt 的最短路，则当 vt 得到永久标记算法就结束
了；但算法复杂度是一样的
? 应用 Dijkstra 算法 n?1 次,可以求所有点间的最短路
? vs 到所有点的最短路也是一棵生成树，但不是最小生成树
17
6.3.2 Warshall-Floyd算法 (1962)
? Warshall-Floyd算法可以解决有 负权值 边 (弧 )的最短路问题
? 该算法是一种整体算法，一次求出所有点间的最短路
? 该算法不允许有 负权值回路,但可以发现负权值回路
? 该算法基于基本的三角运算
定义 对给定的点间初始距离矩阵 {dij}，令 dii=?,?i。对一
个固定点 j，运算 dik=min{dik,dij+djk},? i,k ? j,称为 三角
运算。 (注意，这里允许 i=k)
定理 依次对 j=1,2,…,n 执行三角运算，则 dik 最终等于 i 到
k 间最短路的长度。
k
j
i
d
ij
d
jk
d
ik
18
6.3.2 Floyd-Warshall 算法 (1962)
for i=1 to n do dii=?;
for all eij=0;
for j=1 to n do
for i=1 to n do if i?j then
for k=1 to n do if k?j then
begin
dik=min{dik,dij+djk};
if dik>dij+djk then eik=j
end;
例 1 中 1 到 7 点的最短路是 1 - 2 - 5 - 7
查伴随矩阵 E 的第一行
1 2 3 4 5 6 7
1 0 0 2 0 2 5 5
? 若网路中存在负回路，则计算
中，某些 dii 会小于 0，此时应
中断算法
? 显然,Floyd 算法要进行
n(n-1)2 次加法和比较
? 如何回溯找出任两点之间的最
短路？
? 在 Floyd 算法中设一伴随矩阵
E={eik},eik 记录了 i到 k 最短
路中最后一个中间节点
19
小结
? 最短路有广泛的应用 (6.3.4节 市话局扩容方案 )
? 最短路的多种形式：无向图，有向图无循环圈，有向
图，混合图，无负边权，有负边权，有负回路,k-最
短路等
? 当存在负权值边时,Floyd算法比 Dijkstra算法效率高，
且程序极简单。但 Dijkstra算法灵活
? 若图是前向的，则 Dijkstra算法也可以求两点间最长路
? 一般情况下，两点间最长路是 NP-complete，但最短
路是 P算法
? 两点间 k-最短路：分为边不相交的和边相交的
求边 不相交的 k-最短路非常容易：先求最短路，将该
最短路中的边从网路删去，再用 Dijkstra算法可求次最
短路，以此类推
20
6.3.4 最短路应用举例 ——市话扩容 (实装率 =0.8)
?ê o? 0 1 2 3 4 5 6 7 8 9 10 11 12
?¤2a êy 1,6 1,8 2,0 2,2 2,5 2,8 3,1 3,5 3,9 4,4 4,9 5,5 6,2
t
0
2000
t
6
4000
t
8
5000
t
9
6000
t
11
7000
t
12
8000
t
3
3000
1,4
2,7
6,13
5,12
4,8,8
3,8,3
1,3,5
2,6,0
4,8,3
3,7,1
5,8,9
1,3
2,4,5
3,6,8
4,7,5
1,2,5
2,4,3
3,5,5
21
最短路应用举例 —市话扩容
0 3 6 121198
4
12
8.8
7
22.32.533.5
8.9
8.3
7.1
6
4
7.5
6.8
4.5
8.3
13
5.5
4.3
22
6.4 网路的最大流和最小截
6.4.1 网路的最大流的概念
? 网路流一般在有向图上讨论
? 定义网路上支路的 容量 为其最大通过能力，记为 cij,
支路上的实际 流量 记为 fij
? 图中规定一个发点 s，一个收点 t
? 节点没有容量限制，流在节点不会存储
? 容量限制条件, 0?fij ? cij
? 平衡条件,
?
?
?
?
?
??
?
?
?? ??
??
tifv
tsi
sifv
ff
ijij vBv
ji
vAv
ij
)(
,0
)(
)()(
? 满足上述条件的网路流称为 可行流,总存在 最大可行流
? 当支路上 fij = cij,称为 饱和弧
? 最大流问题也是一个线性规划问题
vi A(v
i)B(vi)
23
6.4.2 截集与截集容量
定义,把网路分割为两个成分的弧的最小集合，其中一
个成分包含 s 点，另一个包含 t 点 。
? 一般包含 s 点的成分中的节点集合用 V表示，包含 t 点
的成分中的节点集合用 V表示
? 截集容量 是指截集中正向弧的容量之和
?
?
?
?
Vj
Vi ij
cVVC ),(
? 福特 -富克森定理,网路的最大流等于最小截集容量。
当达到最大流时，最小截集中的反向弧流量必为零
s t
53
42
( 4,0 )
( 3,0 )
( 2,0 )
( 1,0 )( 1,0 )
( 5,0 )
( 3,0 )
( 2,0 )
( 5,0 )
24
6.4.3 确定网路最大流的标号法
? 从任一个初始可行流出发，如 0 流
? 基本算法：找一条从 s 到 t 点的 增广链 (augmenting path)
? 若在当前可行流下找不到增广链，则已得到最大流
? 增广链中与 s 到 t 方向一致的弧称为 前向弧,反之 后向弧
? 增广过程：前向弧 f?ij=fij +q,后向弧 f?ij=fij ?q
? 增广后仍是可行流
s t5432
( 3,0 ) ( 5,3 )( 1,1 )( 5,1 ) ( 1,1 )
q
s2
= 4 q
5t
= 2q
45
= 3q
43
= 1q
32
= 1
增广量 q = m in
q
ij
= m in ( 4,1,1,3,2) = 1
s t5432
( 3,1 ) ( 5,4 )( 1,0 )( 5,2 ) ( 1,0 )
?
?
? ?
?
后向弧
前向弧
ij
ijij
ij
f
fc
q
25
最大流最小截的标号法步骤
第一步：标号过程，找一条增广链
1,给源点 s 标号 [s+,q(s)=?]，表示从 s 点有无限流出潜力
2,找出与已标号节点 i 相邻的所有未标号节点 j，若
(1) (i,j)是前向弧且饱和，则节点 j 不标号；
(2) (i,j)是前向弧且未饱和，则节点 j 标号为 [i+,q(j)]，表示从节点 i 正
向 流出，可增广 q(j)=min[q(i),cij?fij] ；
(3) (j,i)是后向弧，若 fji=0，则节点 j 不标号；
(4) (j,i)是后向弧，若 fji>0，则节点 j 标号为 [i?,q(j)]，表示从节点 j 流
向 i,可增广 q(j)=min[q(i),fji] ；
3,重复步骤 2，可能出现两种情况：
(1) 节点 t 尚未标号，但无法继续标记，说明网路中已不存在增广链，
当前流 v(f) 就是最大流；所有获标号的节点在 V 中，未获标号节
点在 V 中,V 与 V 间的弧即为最小截集；算法结束
(2)节点 t 获得标号，找到一条增广链，由节点 t 标号回溯可找出该增
广链；到第二步
26
最大流最小截的标号法步骤
第二步：增广过程
1、对 增广链中的前向弧，令 f?=f+q(t),q(t) 为节点 t 的标记值
2,对 增广链中的后向弧，令 f?=f?q(t)
3、非增广链上的所有支路流量保持不变
第三步：抹除图上所有标号，回到第一步
? 以上算法是按广探法描述的，但在实际图上作业时，按深
探法进行更快捷
? 一次只找一条增广链，增广一次换一张图
? 最后一次用广探法，以便找出最小截集
27
最大流最小截集的标号法举例
s t
1
3 4
2 5
6
(14,
14)
(9,
9)
(15,9)
(16,15)
(3,
1)
(12,10)
(6,
6)
(4,3)
(5,
5)
(22,
22)
(13,
12)
(7,
5)(6,
3)
(19,
10)
s t
1
3 4
2 5
6
(14,
14)
(9,
9)
(15,10)
(16,15)
(3,
1)
(12,10)
(6,
5)
(4,4)
(5,
5)
(22,
22)
(13,
12)
(7,
5)(6,
3)
(19,
11)
(s+,?)
(s+,6)
(2?,6) (3+,1)
(4+,1)
(s+,?)
(s+,5)
(2+,2)
(5?,2)
(4+,2)
28
最大流最小截集的标号法举例
s t
1
3 4
2 5
6
(14,
14)
(9,
9)
(15,10)
(16,15)
(3,
1)
(12,10)
(6,
5)
(4,4)
(5,
5)
(22,
22)
(13,
12)
(7,
5)(6,
3)
(19,
11)
s t
1
3 4
2 5
6
(14,
14)
(9,
9)
(15,12)
(16,15)
(3,
1)
(12,12)
(6,
5)
(4,4)
(5,
5)
(22,
22)
(13,
12)
(7,
5)(6,
1)
(19,
13)
(s+,?)
(s+,3)
(2?,3)
最小截集
(4+,2)
29
最大流标号法的复杂度讨论 s t
v
u
20002000
20002000
1
? 找一条增广链的计算量是容易估计的，不会超过 O(n2)
? 但是最多迭代多少次 (即增广的次数 )就很难估计，在最坏情
况下，与边的容量有关；如上图：先增广 s ? u ? v ? t,
然后增广 s ? v ? u ? t，每次只能增广 1 个单位，故要增
广 4000次才能结束
? 克服这种缺点的经验方法：
– 尽量先用段数少的增广链
– 尽量不重复前面出现过的增广链
30
6.4.4 多端网路问题
1 8
7
6
4
3
52
(1 5,0 )
(1 0,0 )
(2 0,0 )
(5,0 )
(5,0 )
(5,0 )
(5,0 )
(5,0 )
(1 0,0 )
(1 0,0 )
(1 0,0 )
(1 0,0 )
发点 1
20
发点 2
20
收点 1
15
收点 2
20
(5,0 )
,1 )
(1 0,1 0 )
5
5
5
5
5
5
(1 0,1 0 )
5
虚发点
虚收点
s
t
(2 0,1 5 )
(2 0,1 5 )
(2 0,1 5 )
(1 5,1 5 )
(5,0 )
31
6.4.5 最小费用最大流
? 双权网路,每条弧不但有容量，还有单位流量的通过费用
? 两种解法：一种基于最小费用路径算法；一种基于可行弧集
的最大流算法
? 基于最小费用路径算法,总是在当前找到的最小费用的路径
上增广流；缺点是每次增广后要改变弧的费用，且出现负权
值费用的弧
? 基于可行弧集的最大流算法,从 0 费用弧集开始应用最大流
算法，然后根据计算信息提高费用的限界 P，使可行弧集增
大，再应用最大流算法，直至所有弧都进入可行弧集。这种
算法是一种主 -对偶规划的解法。使用这种方法的还有运输
问题、匹配问题
