?管理与人文学院 忻展红
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)
最小截集
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，使可行弧集增
大，再应用最大流算法，直至所有弧都进入可行弧集。这种
算法是一种主 -对偶规划的解法。使用这种方法的还有运输
问题、匹配问题
32
6.4.5 以最短路为基础汇总网路上的流
1
32
4 5
电路交换网
1
32
4 5
传输网
? 在电路网中每两点之间都有中继电路群需求，但并不是任
两点都有物理传输链路
? 根据两点间最短传输路径将该两点间的电路需求量加载到
这条传输路径上去：设 a25=10 是节点 2 和 5 之间的电路需
求，节点 2 和 5 之间的最短传输路径为 2?1?3?5，则加载过
程为, T21=T21+10,T13=T13+10,T35=T35+10； Tij 是传输链路
i?j 上加载的电路数；当所有点间电路都加载完则算法结束
33
6.5 欧拉回路和中国邮递员问题
? 中国邮递员问题 (Chinese Postman Problem,CPP)是由我国
管梅谷教授于 1962年首先提出并发表的
? 问题是从邮局出发，走遍邮区的所有街道至少一次再回到
邮局，走什么路由才能使总的路程最短？
? 如果街区图是一个偶图，根据定理 3，一定有欧拉回路，
CPP 问题也就迎刃而解了
? 若街区图不是偶图，则必然有一些街道要被重复走过才能
回到原出发点
? 显然要在奇次点间加重复边
? 如何使所加的边长度最少
? 归结为求奇次点间的最小
匹配 ( minimum weighted
match) — 由 Edmons 给出
多项式算法 (1965)
A
B
C D
34
解中国邮递员问题的步骤
0、将图中的所有悬挂点依次摘去
1、求所有奇次点间的最短距离和最短路径
2、根据奇次点间的最短距离求最小完全匹配
3、根据最小完全匹配和最短路径添加重复边
4、将悬挂点逐一恢复，并加重复边
5、根据得到的偶图，给出欧拉回路的若干种走法
1
3
2
4
5
9
8
7
6
0
5
5 4
3
4
4
42
6
6 2
1
3
2
4
5
9
8
7
6
5
5 4
3
4
4
42
6
6
35
解中国邮递员问题的步骤
2 4 6 8
2 - 5 3 5
4 - 5 5,7
6 - 5,9
8 -
转接矩阵
2 4 6 8
2 0 10 7 10
4 0 7 8
6 0 7
8 0
最短距离矩阵
1
5
9
5
5 4
3
4
4
42
6
6
2
1
2
4
5
96
0
8
74
6
2
3
0
3
8
7
添
加
重
复
边
找
出
所
有
基
本
回
路
36
6.6 哈密尔顿回路及旅行推销员问题
6.6.1 哈密尔顿回路 ( Hamiltonian circuit)
? 连通图 G(V,E)中的回路称为 哈密尔顿回路,若该回路包括图中
所有的点。显然哈密尔顿回路有且只有 n条边，若 |V|=n
? 连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是
由爱尔兰数学家 哈密尔顿 1859年 提出的，但至今仍未解决
? 欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访
问的问题
? 搜索哈密尔顿回路的难度是 NP-complete
? 任两点间都有边的图称为 完全图 (或全连接图 )
? 完全图中有多少个不同的哈密尔顿回路？
? 完全图中有多少个边不相交的哈密尔顿回路？
? 最小哈密尔顿回路问题 (NP-complete)
? 哈密尔顿路径,包含图中所有点的路径
? 为什么说找两点间的最长路是非常困难的问题？
(n?1)!/2
(n?1)/2
37
6.6.2 旅行推销员问题 (Traveling Salesman Problem)
? 旅行推销员问题 (TSP)：设 v1,v2,...,vn 为 n 个已知城市，城市
之间的旅程也是已知的，要求推销员从 v1出发，走遍所有城
市一次且仅一次又回到出发点，并使总旅程最短
? 这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路
问题
? 一般旅行推销员问题 (GTSP)：允许点重复的 TSP
? 当网路边权满足三角不等式时，一般旅行推销员问题就等价
于最小哈密尔顿回路问题
? 当网路边权不满足三角不等式时，只要用两点间最短路的距
离代替原来的边权，就可以满足三角不等式，在此基础上求
最小哈密尔顿回路
典型的应用,
? 乡邮员的投递路线
? 邮递员开邮箱取信的路线问题
? 邮车到各支局的转趟问题
38
TSP 的启发式算法 (Heuristic algorithm)
? 穷举法,指数算法
? 分支定界法,隐枚举法
? 二交换法 (two-option,Lin’s algorithm)
– 哈密尔顿回路可以用点的序列表示
– 从任一个哈密尔顿回路 (即任何一个序列 )出发
– 按照一定顺序试图交换相邻两个点的顺序，若路程减少则完
成交换，继续下一个交换；若没有改善，则不进行本次交换，
尝试下一个交换；若所有的相临交换都试过而不能改善，则
算法结束，得到一个局部最优点
? 模拟退火 (Simulated Annealing)
– 随机地采用二交换法
– 当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率
被接受，但这种概率是随模拟的温度下降而减少的
– 发挥了计算机的优点，尽量减少陷入局部极值点
– 模拟物理机制
39
二交换法举例
2
3
45
1
2311
2
6
10
1
3 1
817
2
45
2311
2
6
10
1
1
31
初始解,1-2-3-4-5
? 1-3-2-4-5
1
23
1
2
6
10
13
2
3
45
1-3-2-4-5 ? 1-3-4-2-5
2
3
45
1
1
2 10
13
1-3-4-2-5 ? 1-3-4-5-2 ?
? 5-3-4-2-1 ? ? 3-1-4-2-5 ?
40
算法复杂度
? Prim算法
– i=1 n ? 1 次比较，最多 n ? 1 次赋值
– i=2 2(n ? 2) 次比较，最多 2(n ? 2) 次赋值
– i=k k(n ? k) 次比较，最多 k(n ? k) 次赋值
)1(31)12()1(622 )1(2)(2 2
1
1
?????????
?
?
nnnnnnnnknk
n
k
? Dijkstra算法
– i=1 n ? 1 次临时标记，永久标记 n ? 1 次比较和赋值
– i=2 n ? 2 次临时标记，永久标记 n ? 2 次比较和赋值
– i=k n ? k 次临时标记，永久标记 n ? k 次比较和赋值
)1(2)(4
1
1
????
?
?
nnkn
n
k
41
Prim算法的改进
增加一个辅助记录型数组，用以记录当前 V 中各节点到 V的最小边，
minedge[i].cost 记录该边的权值,minedge[i].vex 记录该边 V 中的
顶点。若 minedge[i].cost<0 则表明 i 点进入集合 V
for i:=2 to n do begin minedge[i].vex:=1; minedge[i].cost:=w[1,i] end;
for i:=1 to n ? 1 do
begin
mi:=maxint;
for j:=2 to n do if (minedge[j].cost>0) and (minedge[j].cost<mi) then
begin k:=j; mi:=minedge[j].cost end;
minedge[k].cost:= ?minedge[k].cost; {找到 k，将 k 加入集合 V}
for j:=2 to n do if (w[k,j]<minedge[j].cost) then
begin
minedge[j].cost:=w[k,j];
minedge[j].vex:=k;
end;
end; { 该算法复杂度 约为 5n(n-1) }
42
匹配问题 (Matching Problem)
定义,图中一组边的集合，当图中的每个节点最多只与
该集合中的一条边相关联，则该边集就成为 匹配 。
1,两部图 的匹配问题
? 图中的节点可分为两个集合,X,Y,X 与 Y 之间有边相连，
但 X 内部和 Y 内部无关联边，称为两部图
– 运输问题实际上是两部图的最小费用最大流问题
– 任务分配问题实际上是两部图的最小完全匹配问题
2,非 两部图 的匹配问题
(1) 最大基数匹配 (maximum cardinality matching)
(2) 最大权匹配 (maximum weight matching)
(3) 最小完全匹配 (minimum weight perfect matching)
(4) 最优分数匹配 (optimal fractional matching)
43
两部图的最小完全匹配 ?? 匈亚利算法
? 任务分配问题的抽象就是两部图的最小完全匹配问题
? 匈亚利算法 (Hungarian method)由 Kuhn教授提出, 它实际
上是主对偶算法的先驱
? 匈亚利算法借助于效率矩阵和两部图来完成运算
? 任务分配问题的 效率矩阵对应的是两部图的边权 {cij},对偶
问题的解对应的是每条边的两个端点 {ai,bj}；对偶约束为
ai,＋ bj ? cij
? 匈亚利算法的实质是通过构造 对偶问题的可行解, 得到一
个 等值边子图, 即所有 ai,＋ bj ＝ cij 的边构成的图；然后在
等值边子图 上求最大基数匹配；当得到原问题的完全匹配,
则算法结束
? 对偶问题的可行解 ? 等值边子图 ? 满足互补松弛定理求
原问题的解 (部分可行解 )? 检验 ? 扩充 等值边子图 ?
44
最大基数匹配
? 最大基数匹配是基于 交错树的算法
? 敞露点, 根, 交错链, 外点, 内点, 增广链
– 尚未匹配的节点称为 敞露点
– 以敞露点为根, 由非匹配边和匹配边交替构成的链称为
交错链
– 交错链 的根为外点, 其后内点与外点交替；外点是交错
链的生长点
– 以内点结束的交错链称为 增广链, 因为反转该链上各边
的匹配状态可使匹配的边数增加一条
???í?÷????
?ù ???? ???? ??????
??????
45
匈亚利算法步骤
1 令所有 ai＝ 0
2 在效率矩阵中找每列最小值 qj,令 bj＝ qj,故 ? i,j,满足
ai＋ bj ? cij
3 在满足 ai＋ bj ＝ cij 的边构成的等值子图中求最大基数匹配；
若达到完全匹配则结束, 否则到下一步
4 对敞露点求每列的最小松弛量
sj＝ min i* {ci*j－ ai*－ bj }
5 求最大增广量
S＝ 0.5 ? min j {sj}
7 增广等值子图,
? j,bj ＝ bj ＋ S
? i*(敞露点 ),aj ＝ aj ＋ S ； ? i (非敞露点 ),aj ＝ aj － S
? 返回到第 3 步
46
匈亚利算法举例
b
a
1 2 1 2
* 0 3 3 5 3
0 3 ( 2 ) 5 2
0 ( 1 ) 5 1 6
* 0 4 6 4 10
s l a c k 2 1 3 1
nbour 1 1 4 1
S * = 0, 5
*
*
47
匈亚利算法举例
*
b
a
1, 5 2, 5 1, 5 2, 5
0,5 3 ( 3 ) 5 3
- 0, 5 3 2 5 ( 2 )
- 0, 5 ( 1 ) 5 1 6
* 0, 5 4 6 4 10
s l a c k 2 3 2 7
nbour 4 4 4 4
S * = 1
48
匈亚利算法举例
b
a
2, 5 3, 5 2, 5 3, 5
- 0, 5 3 ( 3 ) 5 3
- 1, 5 3 2 5 ( 2 )
- 1, 5 1 5 ( 1 ) 6
1, 5 ( 4 ) 6 4 10
s l a c k
nbour
49
任务分配问题、匹配问题和 TSP的关系
? 三个问题都有一个 n?n 正权值的边权矩阵
? 三个问题的解都可以用代数臵换 (permutation)表示
???
?
???
?
???
?
???
?
15423
54321 54321
54321 iiiii
? i1,i2,i3,i4,i5 是 1,2,3,4,5 的任一排列，表示元素位臵
的交换
? 轮换，全轮换，对换
? TSP的解必须是一个全轮换
? 任务分配问题的解可以是任一个臵换
? 匹配的解必须是 n/2 个对换
? 任务分配问题是匹配问题的松弛问题
50
6.7 选址问题
? 使所选地址到最远的服务对象距离尽可能小 ——中心点
? 使所选地址到各服务对象的总距离最小 ——中位点
? 有时间限制的多用中心点，如乡邮局
? 总资源约束的多用中位点，如电话交换局
6.7.1 各点之间的距离
? 节点到节点间的最短距离，称为节点 —节点距离
? 边上某点到节点的最短距离，称为点 —节点距离
? 节点到某边上最远一点的距离，称为节点 —边距离
? 边上一点到另一边上最远点的距离，称为点 —边距离
1 6
2 5
7 3 4
2
1
11
1
3
2
51
1,边上某点到节点的最短距离
– dij 代表 vi 与 vj 间的最短距离,ars 代表边 (r,s)的边长，
令 h 为边 (r,s)上一点的 百分位, 0? h?1
– 边上对应 h 的一点到 vj 的最短距离为
d[h(r,s),j]=min[h?ars+drj,(1?h)?ars+dsj]
2,节点到某边上最远一点的距离
– 指定节点 j，它到边 (r,s)上对应 h百分位点有两条路，最
远点必使两条路一样长，故有
d[j,(r,s)]=0.5[djr+ djs+ ars]
3,边上指定一点到其他边上最远点的距离
– h 是边 (r,s)上指定的百分位点，另一边为 (u,t)
d[h(r,s),(u,t)]=min[h?ars+d[r,(u,t)],(1?h)?ars+d [s,(u,t)] ]
52
6.7.2 中心的选择
? 中心：以节点 —节点距离为基础，大中取小 (max min)
? 一般中心：以节点 —边距离为基础，大中取小
? 绝对中心：以点 —节点距离为基础，大中取小
? 一般绝对中心：以点 —边距离为基础，大中取小
? 左图的中心是 v1；而三个节点都是一般中心
? 类似也有四种中位点：
– 中位点
– 一般中位点
– 绝对中位点
– 一般绝对中位点
3
3
2 1
2
5 4
2
1
4
3
3
2
1
5
2
7
53
例 6.7.1~6.7.2
m a x m i n ? m i n
0 2 3 4 4 4 ? 13
2 0 1 5 2 5 10 ?
3 1 0 6 3 6 13
4 5 6 0 3 6 18
4 2 3 3 0 4 ? 12
编号 1 23 4 5 6 7
边 ( i,j ) ( 1,2 ) ( 1,4 ) ( 2,3 ) ( 2,5 ) ( 3,5 ) ( 4,5 )
边长 2 4 1 2 5 3
m a x m i n ? m i n
2 4 3 4 6 5, 5 6 2 4, 5
2 5, 5 1 2 4 5 5, 5 ? 1 9, 5 ?
3 6, 5 1 3 4 6 6, 5 2 3, 5
5, 5 4 6 5 7 3 7 3 0, 5
4 5, 5 3 2 4 3 5, 5 ? 2 1, 5
中心
一般中心
中位点
一般中位点
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)
最小截集
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，使可行弧集增
大，再应用最大流算法，直至所有弧都进入可行弧集。这种
算法是一种主 -对偶规划的解法。使用这种方法的还有运输
问题、匹配问题
32
6.4.5 以最短路为基础汇总网路上的流
1
32
4 5
电路交换网
1
32
4 5
传输网
? 在电路网中每两点之间都有中继电路群需求，但并不是任
两点都有物理传输链路
? 根据两点间最短传输路径将该两点间的电路需求量加载到
这条传输路径上去：设 a25=10 是节点 2 和 5 之间的电路需
求，节点 2 和 5 之间的最短传输路径为 2?1?3?5，则加载过
程为, T21=T21+10,T13=T13+10,T35=T35+10； Tij 是传输链路
i?j 上加载的电路数；当所有点间电路都加载完则算法结束
33
6.5 欧拉回路和中国邮递员问题
? 中国邮递员问题 (Chinese Postman Problem,CPP)是由我国
管梅谷教授于 1962年首先提出并发表的
? 问题是从邮局出发，走遍邮区的所有街道至少一次再回到
邮局，走什么路由才能使总的路程最短？
? 如果街区图是一个偶图，根据定理 3，一定有欧拉回路，
CPP 问题也就迎刃而解了
? 若街区图不是偶图，则必然有一些街道要被重复走过才能
回到原出发点
? 显然要在奇次点间加重复边
? 如何使所加的边长度最少
? 归结为求奇次点间的最小
匹配 ( minimum weighted
match) — 由 Edmons 给出
多项式算法 (1965)
A
B
C D
34
解中国邮递员问题的步骤
0、将图中的所有悬挂点依次摘去
1、求所有奇次点间的最短距离和最短路径
2、根据奇次点间的最短距离求最小完全匹配
3、根据最小完全匹配和最短路径添加重复边
4、将悬挂点逐一恢复，并加重复边
5、根据得到的偶图，给出欧拉回路的若干种走法
1
3
2
4
5
9
8
7
6
0
5
5 4
3
4
4
42
6
6 2
1
3
2
4
5
9
8
7
6
5
5 4
3
4
4
42
6
6
35
解中国邮递员问题的步骤
2 4 6 8
2 - 5 3 5
4 - 5 5,7
6 - 5,9
8 -
转接矩阵
2 4 6 8
2 0 10 7 10
4 0 7 8
6 0 7
8 0
最短距离矩阵
1
5
9
5
5 4
3
4
4
42
6
6
2
1
2
4
5
96
0
8
74
6
2
3
0
3
8
7
添
加
重
复
边
找
出
所
有
基
本
回
路
36
6.6 哈密尔顿回路及旅行推销员问题
6.6.1 哈密尔顿回路 ( Hamiltonian circuit)
? 连通图 G(V,E)中的回路称为 哈密尔顿回路,若该回路包括图中
所有的点。显然哈密尔顿回路有且只有 n条边，若 |V|=n
? 连通图具有哈密尔顿回路的充分必要条件是什么？这个问题是
由爱尔兰数学家 哈密尔顿 1859年 提出的，但至今仍未解决
? 欧拉回路是对边进行访问的问题，哈密尔顿回路是对点进行访
问的问题
? 搜索哈密尔顿回路的难度是 NP-complete
? 任两点间都有边的图称为 完全图 (或全连接图 )
? 完全图中有多少个不同的哈密尔顿回路？
? 完全图中有多少个边不相交的哈密尔顿回路？
? 最小哈密尔顿回路问题 (NP-complete)
? 哈密尔顿路径,包含图中所有点的路径
? 为什么说找两点间的最长路是非常困难的问题？
(n?1)!/2
(n?1)/2
37
6.6.2 旅行推销员问题 (Traveling Salesman Problem)
? 旅行推销员问题 (TSP)：设 v1,v2,...,vn 为 n 个已知城市，城市
之间的旅程也是已知的，要求推销员从 v1出发，走遍所有城
市一次且仅一次又回到出发点，并使总旅程最短
? 这种不允许点重复的旅行推销员问题就是最小哈密尔顿回路
问题
? 一般旅行推销员问题 (GTSP)：允许点重复的 TSP
? 当网路边权满足三角不等式时，一般旅行推销员问题就等价
于最小哈密尔顿回路问题
? 当网路边权不满足三角不等式时，只要用两点间最短路的距
离代替原来的边权，就可以满足三角不等式，在此基础上求
最小哈密尔顿回路
典型的应用,
? 乡邮员的投递路线
? 邮递员开邮箱取信的路线问题
? 邮车到各支局的转趟问题
38
TSP 的启发式算法 (Heuristic algorithm)
? 穷举法,指数算法
? 分支定界法,隐枚举法
? 二交换法 (two-option,Lin’s algorithm)
– 哈密尔顿回路可以用点的序列表示
– 从任一个哈密尔顿回路 (即任何一个序列 )出发
– 按照一定顺序试图交换相邻两个点的顺序，若路程减少则完
成交换，继续下一个交换；若没有改善，则不进行本次交换，
尝试下一个交换；若所有的相临交换都试过而不能改善，则
算法结束，得到一个局部最优点
? 模拟退火 (Simulated Annealing)
– 随机地采用二交换法
– 当交换后没有使目标函数改善，也可能以玻尔兹曼分布概率
被接受，但这种概率是随模拟的温度下降而减少的
– 发挥了计算机的优点，尽量减少陷入局部极值点
– 模拟物理机制
39
二交换法举例
2
3
45
1
2311
2
6
10
1
3 1
817
2
45
2311
2
6
10
1
1
31
初始解,1-2-3-4-5
? 1-3-2-4-5
1
23
1
2
6
10
13
2
3
45
1-3-2-4-5 ? 1-3-4-2-5
2
3
45
1
1
2 10
13
1-3-4-2-5 ? 1-3-4-5-2 ?
? 5-3-4-2-1 ? ? 3-1-4-2-5 ?
40
算法复杂度
? Prim算法
– i=1 n ? 1 次比较，最多 n ? 1 次赋值
– i=2 2(n ? 2) 次比较，最多 2(n ? 2) 次赋值
– i=k k(n ? k) 次比较，最多 k(n ? k) 次赋值
)1(31)12()1(622 )1(2)(2 2
1
1
?????????
?
?
nnnnnnnnknk
n
k
? Dijkstra算法
– i=1 n ? 1 次临时标记，永久标记 n ? 1 次比较和赋值
– i=2 n ? 2 次临时标记，永久标记 n ? 2 次比较和赋值
– i=k n ? k 次临时标记，永久标记 n ? k 次比较和赋值
)1(2)(4
1
1
????
?
?
nnkn
n
k
41
Prim算法的改进
增加一个辅助记录型数组，用以记录当前 V 中各节点到 V的最小边，
minedge[i].cost 记录该边的权值,minedge[i].vex 记录该边 V 中的
顶点。若 minedge[i].cost<0 则表明 i 点进入集合 V
for i:=2 to n do begin minedge[i].vex:=1; minedge[i].cost:=w[1,i] end;
for i:=1 to n ? 1 do
begin
mi:=maxint;
for j:=2 to n do if (minedge[j].cost>0) and (minedge[j].cost<mi) then
begin k:=j; mi:=minedge[j].cost end;
minedge[k].cost:= ?minedge[k].cost; {找到 k，将 k 加入集合 V}
for j:=2 to n do if (w[k,j]<minedge[j].cost) then
begin
minedge[j].cost:=w[k,j];
minedge[j].vex:=k;
end;
end; { 该算法复杂度 约为 5n(n-1) }
42
匹配问题 (Matching Problem)
定义,图中一组边的集合，当图中的每个节点最多只与
该集合中的一条边相关联，则该边集就成为 匹配 。
1,两部图 的匹配问题
? 图中的节点可分为两个集合,X,Y,X 与 Y 之间有边相连，
但 X 内部和 Y 内部无关联边，称为两部图
– 运输问题实际上是两部图的最小费用最大流问题
– 任务分配问题实际上是两部图的最小完全匹配问题
2,非 两部图 的匹配问题
(1) 最大基数匹配 (maximum cardinality matching)
(2) 最大权匹配 (maximum weight matching)
(3) 最小完全匹配 (minimum weight perfect matching)
(4) 最优分数匹配 (optimal fractional matching)
43
两部图的最小完全匹配 ?? 匈亚利算法
? 任务分配问题的抽象就是两部图的最小完全匹配问题
? 匈亚利算法 (Hungarian method)由 Kuhn教授提出, 它实际
上是主对偶算法的先驱
? 匈亚利算法借助于效率矩阵和两部图来完成运算
? 任务分配问题的 效率矩阵对应的是两部图的边权 {cij},对偶
问题的解对应的是每条边的两个端点 {ai,bj}；对偶约束为
ai,＋ bj ? cij
? 匈亚利算法的实质是通过构造 对偶问题的可行解, 得到一
个 等值边子图, 即所有 ai,＋ bj ＝ cij 的边构成的图；然后在
等值边子图 上求最大基数匹配；当得到原问题的完全匹配,
则算法结束
? 对偶问题的可行解 ? 等值边子图 ? 满足互补松弛定理求
原问题的解 (部分可行解 )? 检验 ? 扩充 等值边子图 ?
44
最大基数匹配
? 最大基数匹配是基于 交错树的算法
? 敞露点, 根, 交错链, 外点, 内点, 增广链
– 尚未匹配的节点称为 敞露点
– 以敞露点为根, 由非匹配边和匹配边交替构成的链称为
交错链
– 交错链 的根为外点, 其后内点与外点交替；外点是交错
链的生长点
– 以内点结束的交错链称为 增广链, 因为反转该链上各边
的匹配状态可使匹配的边数增加一条
???í?÷????
?ù ???? ???? ??????
??????
45
匈亚利算法步骤
1 令所有 ai＝ 0
2 在效率矩阵中找每列最小值 qj,令 bj＝ qj,故 ? i,j,满足
ai＋ bj ? cij
3 在满足 ai＋ bj ＝ cij 的边构成的等值子图中求最大基数匹配；
若达到完全匹配则结束, 否则到下一步
4 对敞露点求每列的最小松弛量
sj＝ min i* {ci*j－ ai*－ bj }
5 求最大增广量
S＝ 0.5 ? min j {sj}
7 增广等值子图,
? j,bj ＝ bj ＋ S
? i*(敞露点 ),aj ＝ aj ＋ S ； ? i (非敞露点 ),aj ＝ aj － S
? 返回到第 3 步
46
匈亚利算法举例
b
a
1 2 1 2
* 0 3 3 5 3
0 3 ( 2 ) 5 2
0 ( 1 ) 5 1 6
* 0 4 6 4 10
s l a c k 2 1 3 1
nbour 1 1 4 1
S * = 0, 5
*
*
47
匈亚利算法举例
*
b
a
1, 5 2, 5 1, 5 2, 5
0,5 3 ( 3 ) 5 3
- 0, 5 3 2 5 ( 2 )
- 0, 5 ( 1 ) 5 1 6
* 0, 5 4 6 4 10
s l a c k 2 3 2 7
nbour 4 4 4 4
S * = 1
48
匈亚利算法举例
b
a
2, 5 3, 5 2, 5 3, 5
- 0, 5 3 ( 3 ) 5 3
- 1, 5 3 2 5 ( 2 )
- 1, 5 1 5 ( 1 ) 6
1, 5 ( 4 ) 6 4 10
s l a c k
nbour
49
任务分配问题、匹配问题和 TSP的关系
? 三个问题都有一个 n?n 正权值的边权矩阵
? 三个问题的解都可以用代数臵换 (permutation)表示
???
?
???
?
???
?
???
?
15423
54321 54321
54321 iiiii
? i1,i2,i3,i4,i5 是 1,2,3,4,5 的任一排列，表示元素位臵
的交换
? 轮换，全轮换，对换
? TSP的解必须是一个全轮换
? 任务分配问题的解可以是任一个臵换
? 匹配的解必须是 n/2 个对换
? 任务分配问题是匹配问题的松弛问题
50
6.7 选址问题
? 使所选地址到最远的服务对象距离尽可能小 ——中心点
? 使所选地址到各服务对象的总距离最小 ——中位点
? 有时间限制的多用中心点，如乡邮局
? 总资源约束的多用中位点，如电话交换局
6.7.1 各点之间的距离
? 节点到节点间的最短距离，称为节点 —节点距离
? 边上某点到节点的最短距离，称为点 —节点距离
? 节点到某边上最远一点的距离，称为节点 —边距离
? 边上一点到另一边上最远点的距离，称为点 —边距离
1 6
2 5
7 3 4
2
1
11
1
3
2
51
1,边上某点到节点的最短距离
– dij 代表 vi 与 vj 间的最短距离,ars 代表边 (r,s)的边长，
令 h 为边 (r,s)上一点的 百分位, 0? h?1
– 边上对应 h 的一点到 vj 的最短距离为
d[h(r,s),j]=min[h?ars+drj,(1?h)?ars+dsj]
2,节点到某边上最远一点的距离
– 指定节点 j，它到边 (r,s)上对应 h百分位点有两条路，最
远点必使两条路一样长，故有
d[j,(r,s)]=0.5[djr+ djs+ ars]
3,边上指定一点到其他边上最远点的距离
– h 是边 (r,s)上指定的百分位点，另一边为 (u,t)
d[h(r,s),(u,t)]=min[h?ars+d[r,(u,t)],(1?h)?ars+d [s,(u,t)] ]
52
6.7.2 中心的选择
? 中心：以节点 —节点距离为基础，大中取小 (max min)
? 一般中心：以节点 —边距离为基础，大中取小
? 绝对中心：以点 —节点距离为基础，大中取小
? 一般绝对中心：以点 —边距离为基础，大中取小
? 左图的中心是 v1；而三个节点都是一般中心
? 类似也有四种中位点：
– 中位点
– 一般中位点
– 绝对中位点
– 一般绝对中位点
3
3
2 1
2
5 4
2
1
4
3
3
2
1
5
2
7
53
例 6.7.1~6.7.2
m a x m i n ? m i n
0 2 3 4 4 4 ? 13
2 0 1 5 2 5 10 ?
3 1 0 6 3 6 13
4 5 6 0 3 6 18
4 2 3 3 0 4 ? 12
编号 1 23 4 5 6 7
边 ( i,j ) ( 1,2 ) ( 1,4 ) ( 2,3 ) ( 2,5 ) ( 3,5 ) ( 4,5 )
边长 2 4 1 2 5 3
m a x m i n ? m i n
2 4 3 4 6 5, 5 6 2 4, 5
2 5, 5 1 2 4 5 5, 5 ? 1 9, 5 ?
3 6, 5 1 3 4 6 6, 5 2 3, 5
5, 5 4 6 5 7 3 7 3 0, 5
4 5, 5 3 2 4 3 5, 5 ? 2 1, 5
中心
一般中心
中位点
一般中位点
