2010-5-14
--第 6章 图与网络分析 --
--1--
2010-5-14
--第 6章 图与网络分析 --
--2--
第六章 图与网络分析
? 图是一种模型，如公路、铁路交通图，
通讯网络图等。
? 图示对现实的抽象，以点和线段的连
接组合表示。
2010-5-14
--第 6章 图与网络分析 --
--3--
§ 6.1 图的基本概念和模型
一、概念
（ 1）图：点 V和边 E的集合，用以表示对某种现实事物
的抽象。记作 G=｛ V,E｝,V=｛ v1,v2,···,vn｝,
E=｛ e1,e2,···,em｝
点：表示所研究的事物对象；
边：表示事物之间的联系。
v1 v
2
v3 v4
v0e
1 e2
e3
e4
e5
e6 e7
e0
（ 2）若边 e的两个端点重
合，则称 e为环。
（ 3）多重边：若某两端点之
间多于一条边，则称为多重边。
2010-5-14
--第 6章 图与网络分析 --
--4--
（ 4）简单图：无环、无多重边的图称为简单图。
（ 5）链：点和边的交替序列，其中点可重复，但边不能
重复。
（ 6）路：点和边的交替序列，但点和边均不能重复。
（ 7）圈：始点和终点重合的链。
（ 8）回路：始点和终点重合的路。
（ 9）连通图：若一个图中，任意两点之间至少存在一条
链，称这样的图为连通图。
（ 10）子图，部分图：设图 G1=｛ V1,E1｝,G2={V2,E2},
如果有 V1?V2,E1?E2，则称 G1是 G2的一个子图；若
V1=V2,E1?E2，则称 G1是 G2的一个部分图。
（ 11）次：某点的关联边的个数称为该点的次，以 d(vi)表示。
2010-5-14
--第 6章 图与网络分析 --
--5--
二、图的模型
例：有甲、乙、丙、丁、戊、己六名运动员报名参加 A、
B,C,D,E,F六个项目的比赛。如表中所示，打,√”的
项目是各运动员报名参加比赛的项目。问：六个项目的比赛
顺序应如何安排，才能做到使每名运动员不连续地参加两项
比赛？
甲
乙
丙
丁
戊
己
人 A B C D E F
√ √
√ √ √
√ √
√ √
√ √
√ √
2010-5-14
--第 6章 图与网络分析 --
--6--
建立模型：
解：项目作为研究对象，排序。
设 点：表示运动项目。
边：若两个项目之间无同一名运动员参加。
A
B
C
D
E
F A— C— D— E— F— B
A— F— E— D— C— B
A— C— B— F— E— D
A— F— B— C— D— E
顺序：
2010-5-14
--第 6章 图与网络分析 --
--7--
§ 6.2 树图和图的最小部分树
（ 1）树：无圈的连通图称为树图，简称为树。
一、树图的概念
2010-5-14
--第 6章 图与网络分析 --
--8--
（ 2）树的特性：
① 树是边数最多的 无圈 连通图。在树中任加一条边，就会形成圈。
② 树是边数最少的连通图。在树中任减一条边，则不连通。
（ 3）图的最小部分树：
定义：若 G1是 G2的一个部分图，且为树图，则称 G1是
G2的一个部分树。
G2,A
B
C
D
5
47
3
6 5
5
7
6
G1,A C
B
D
2010-5-14
--第 6章 图与网络分析 --
--9--
定义：树枝总长为最短的部分树称为图的最小部分树。
二、最小部分树的求法
例：要在下图所示的各个位置之间建立起通信网
络，试确定使总距离最佳的方案。
树枝：树图中的边称为树枝。
2010-5-14
--第 6章 图与网络分析 --
--10--
S
A
B
C
D
E
T5
4
5 5
最小部分树长 Lmin=14
2010-5-14
--第 6章 图与网络分析 --
--11--
1,避圈法：将图中所有的点分 V为 V两部分，
V—— 最小部分树内点的集合
V—— 非最小部分树内点的集合
⑴ 任取一点 vi加粗，令 vi∈ V，
⑵ 取 V中与 V相连的边中一条最短的边 (vi,vj)，
加粗 (vi,vj)，令 vj∈ V
⑶ 重复⑵,至所有的点均在 V之内。
2,破圈法：
⑴ 任取一圈，去掉其中一条最长的边，
⑵ 重复，至图中不存在任何的圈为止。
2010-5-14
--第 6章 图与网络分析 --
--12--
S
A
B
C
D
E
T5
4
5 5× ×
×
最小部分树长 Lmin=14
2010-5-14
--第 6章 图与网络分析 --
--13--
§ 6.3 最短路问题
在图示的网络图中，从给定的点 S出发，要到达目
的地 T。问：选择怎样的行走路线，可使总行程最短？
方法,Dijkstra（ D氏）标号法 —— 按离出发点的距离由
近至远逐渐标出最短距离和最佳行进路线。
S
1．求某两点间最短距离的 D（ Dijkstra）氏标号法
2 4 7
2010-5-14
--第 6章 图与网络分析 --
--14--
S
A
B
C
D
E
T5
4
5 5
0
2
4
4 7
89 14 135
4
最短路线,S ? A?B ? E ? D ? T
最短距离,Lmin=13
2010-5-14
--第 6章 图与网络分析 --
--15--
2．求任意两点间最短距离的矩阵算法
⑴ 构造任意两点间直接到达的最短距离矩阵 D（ 0） = ? dij（ 0） ?
S A B C D E T
S 0 2 5 4 ? ? ?
A 2 0 2 ? 7 ? ?
B 5 2 0 1 5 3 ?
C 4 ? 1 0 ? 4 ?
D ? 7 5 ? 0 1 5
E ? ? 3 4 1 0 7
T ? ? ? ? 5 7 0
D（ 0） =
⑵ 构造任意两点间直接到达、或者最多经过 1个中间点到达的最
短距离矩阵 D（ 1） = ? dij（ 1） ?
2010-5-14
--第 6章 图与网络分析 --
--16--
其中 dij（ 1） = min { dir（ 0） + drj（ 0） },
S A B C D E T
S 0 2 4 4 9 8 ?
A 2 0 2 3 7 5 12
B 4 2 0 1 4 3 10
C 4 3 1 0 5 4 11
D 9 7 4 5 0 1 5
E 8 5 3 4 1 0 6
T ? 12 10 11 5 7 0
D（ 1） =
i r j
dir（ 0） drj（ 0）
r
dSE（ 1） = min {dSS（ 0） +dSE（ 0）,dSA（ 0） +dAE（ 0）,dSB（ 0） +dBE（ 0）,dSC（ 0） +dCE（ 0
）,
dSD（ 0） + dDE（ 0）,dSE（ 0） + dEE（ 0）,dST（ 0） + dTE（ 0） } =8
例如
2010-5-14
--第 6章 图与网络分析 --
--17--
其中 dij（ 2） = min { dir（ 1） + drj（ 1） }
S A B C D E T
S 0 2 4 4 8 7 14
A 2 0 2 3 6 5 11
B 4 2 0 1 4 3 9
C 4 3 1 0 5 4 10
D 8 6 4 5 0 1 5
E 7 5 3 4 1 0 6
T 14 11 9 10 5 6 0
D（ 2） =
i r jdir（ 1） drj（ 1）
r
⑶ 构造任意两点间最多可经过 3个中间点到达的最短距
离矩阵 D（ 2） = ? dij（ 2） ?
2010-5-14
--第 6章 图与网络分析 --
--18--
其中 dij（ 3） = min { dir（ 2） + drj（ 2） }
S A B C D E T
S 0 2 4 4 8 7 13
A 2 0 2 3 6 5 11
B 4 2 0 1 4 3 9
C 4 3 1 0 5 4 10
D 8 6 4 5 0 1 5
E 7 5 3 4 1 0 6
T 13 11 9 10 5 6 0
D（ 3） =
i
r
j
dir（ 2） drj（ 2）
r
⑷ 构造任意两点间最多可经过 7个中间点到达的最短距
离矩阵 D（ 3） = ? dij（ 3） ?
2010-5-14
--第 6章 图与网络分析 --
--19--
说明：
一般，对于 D（ k） = ? dij（ k） ?，其中
dij（ k） = min ?{dir（ k-1） + drj（ k-1） }, k=0,1,2,3,·····
最多可经过 2k-1个中间点,其数列为
{0,1,3,7,15,31,·····,2k-1,·····}
收敛条件：
① 当 D（ k+1） = D（ k） 时，计算结束；
② 设网络中有 p个点，即有 p-2个中间点，
则 2k-1-1 <p-2?? 2k-1 ? k-1<log2 (p-1) ? k
∴ K<log2(p-1)+1，
∴ 计算到 k=lg(p-1)/lg2 +1时，收敛，计算结束。
2010-5-14
--第 6章 图与网络分析 --
--20--
例：有 7个村镇要联合建立一所小学，已知各村镇小学
生的人数大致为 S— 30人,A— 40人,B— 20人,C— 15人，
D— 35人,E— 25人,T— 50人。问：学校应建在那一个地
点，可使学生总行程最少？
S A B C D E T
S 0 2 4 4 8 7 13
A 2 0 2 3 6 5 11
B 4 2 0 1 4 3 9
C 4 3 1 0 5 4 10
D 8 6 4 5 0 1 5
E 7 5 3 4 1 0 6
T 13 11 9 10 5 6 0
L=
30
40
20
15
35
25
50
人数
= [1325 1030 880 1035 910 865 1485]T
解：
2010-5-14
--第 6章 图与网络分析 --
--21--
§ 6.4 中国邮路问题
问题：一名邮递员从邮局出发，试选择一条最短的投
递路线？
v1
v2
v3
v4
v5
v6
v8 v
7
v9
v10
v11
v12
v13邮局
4
4 4
5
5
1 2
4
1
2
5 4 4
7 4
2
2
2010-5-14
--第 6章 图与网络分析 --
--22--
2010-5-14
--第 6章 图与网络分析 --
--23--
奇点：图中次为奇数的点称为奇点。
偶点：图中次为偶数的点称为偶点。
结论,最短投递路线应具有下述特征：
⑴ 若图中所有的点均为偶点，则可不重
复走遍所有街道；
⑵ 重复走的路线长度应不超过所在回路
总长度的一半。
2010-5-14
--第 6章 图与网络分析 --
--24--
步骤：
1,两两连接所有的奇点，使之均成为偶点；
2,检查重复走的路线长度，是否不超过其所在
回路总长的一半，若超过，则调整连线，改
走另一半。
2010-5-14
--第 6章 图与网络分析 --
--25--
v1
v2
v3
v4
v5
v6
v8 v
7
v9
v10
v11
v12
v13邮局
4
4 4
5
5
1 2
4
1
2
5 4 4
7 4
2
2
投递距离,L=60+18=78
2010-5-14
--第 6章 图与网络分析 --
--26--
§ 6.5 网络最大流问题
一、网络最大流中有关概念
⑴ 有向图：含有以箭头指示方向的边的网络图。
⑵ 弧：有向图上的边称为弧。用（ vi,vj）表示。
⑶ 弧的容量：弧上通过负载的最大能力，简称容量。以 cij表示。
⑷ 流：加在网络每条弧上的一组负载量，以 fij表示。
⑸ 可行流：能够通过网络的负载量，通常应满足两个条件：
① 容量限制条件：对所有的弧,0 ? fij?cij
② 中间点平衡条件：对任何一个中间点，流入量 =流出量
⑹ 发点、收点、中间点：流的起源点称发点，终到点称收点，其余的
点称中间点。
⑺ 最大流；能够通过网络的最大流量。
⑻ 割集：一组弧的集合，割断这些弧，能使流中断。简称割。
2010-5-14
--第 6章 图与网络分析 --
--27--
v1
vs
v2
v3
v4
vt
9(4)
9(9)
6(1)
(0,+∞)
(vs,2)
(v2,2) (v1,2)
(v3,1)
(v4,1)
5(4)
cij fij
2010-5-14
--第 6章 图与网络分析 --
--28--
⑼ 割的容量：割集中各弧的容量之和。
⑽ 最小割：所有割集中容量之和为最小的一个割集。
⑾ 前向弧 μ+：一条发点到收点链中，由发点指向收点的弧，又称正向弧。
⑿ 后向弧 μ-：一条发点到收点链中，由收点指向发点的弧，又称逆向弧。
⒀ 增广链：由发点到收点之间的一条链，如果在前向弧上满足流量
小于容量，即 fij<cij，后向弧上满足流量大于 0，即 fij>0，则称这样的
链为增广链。
定理：网络的最大流量等于它的最小割集的容量。
定理：当网络中不存在任何增广链时，则网络达到最大流状态。
二、两个定理
2010-5-14
--第 6章 图与网络分析 --
--29--
s
t
设有如下增广链：
∵ △ f=1
∴ 该网络没有达到最大流状态。
2010-5-14
--第 6章 图与网络分析 --
--30--
三、网络最大流的标号算法 (Ford-Fulkerson标号算法 )
基本思想：寻找增广链，改善流量分布；再重复，直到不
存在任何增广链为止。
步骤：
① 给始点标号：（ 0,+∞）
② 从已标号点 i出发，看与其相关联的未标号点 j上的弧，
对 μ+，若有 0?fij<cij，则可对 j点标号，记（ i,ε (j)），
其中 ε (j)=min{ε (i), cij - fij}
对 μ-，若有 0 < fji? cij，也可对 j点标号，记（ i,ε (j)），
其中 ε (j)=min{ε (i), fji}
（注：若有多个可标号点，可任选其中之一。）
若标号中断，则得到最大流状态，否则，重复②，继续标
号，至收点得到标号，转③。
2010-5-14
--第 6章 图与网络分析 --
--31--
③ 当收点得到标号，则沿标号得到的增广链进行流量调整：
对 μ+,f?ij = fij +ε (t)
对 μ-,f?ij = fij -ε (t)
其余弧上的流量不变。
④ 重复上述过程。
⑤ 最小割集：已标号点集合与未标号点集合相连接的弧中，
流量 =容量的弧。
2010-5-14
--第 6章 图与网络分析 --
--32--
v1
vs
v2
v3
v4
vt
9(5)
9(9)
6(0)5(3)
(0,+∞)
(vs,1)
(v2,1) (v
1,1)
最大流量,fmax=14
最小割集：｛ (v3,vt),(v2,v4)｝
2010-5-14
--第 6章 图与网络分析 --
--33--
§ 6.6 网络模型的实际应用
例 1,王经理花费 12000元购买了一台微型车，以后年度的
维护费用取决于年初时汽车的役龄，如表示。为避免使用旧
车带来较高的维护费用，王经理可选择卖掉旧车，购买新车
使用的方案，旧车的预计收入如表示。为简化计算，假定任
何时刻购买新车都需花费 12000元，王经理的目标是使净费用
最小（购置费 +维护费 -卖旧车收入）。
役龄 (年 )
年维护费
预计收入
单位：元
0 1 2 3 4 5
2000 4000 5000 9000 12000 ——
—— 7000 6000 2000 1000 0
2010-5-14
--第 6章 图与网络分析 --
--34--
解,用网络图模型描述，归结为最短路问题。
7 7 7 7 71 2 3 4 5 6
12 12 12 12
21 21 21
31 31
44
1年初 5年末
2010-5-14
--第 6章 图与网络分析 --
--35--
例 2：图示岛屿与河岸有数座桥相联，问至少需要炸
毁几座桥，可中断两岸的交通？
A
B C
D
E
F
2010-5-14
--第 6章 图与网络分析 --
--36--
A
B C
F
ED
2 2
2 1
3
1
1
1
1
2010-5-14
--第 6章 图与网络分析 --
--37--
例 3：有 3根相同的轴 A1,A2,A3，另有三根相同的齿轮
B1,B2,B3。因为精度不高，不能做到任意的互相配合，
其中 A1能与 B1,B2配合,A2能与 B2,B3配合,A3能与
B1,B3配合。要求确定合适的配合方案，以得到最多的
配合数，将此问题归为网络最大流问题。
A1
A2
A3
B1
B2
B3
1
1
1
1
1
1
S T
1
1
1
1
1
1
2010-5-14
--第 6章 图与网络分析 --
--38--
--第 6章 图与网络分析 --
--1--
2010-5-14
--第 6章 图与网络分析 --
--2--
第六章 图与网络分析
? 图是一种模型，如公路、铁路交通图，
通讯网络图等。
? 图示对现实的抽象，以点和线段的连
接组合表示。
2010-5-14
--第 6章 图与网络分析 --
--3--
§ 6.1 图的基本概念和模型
一、概念
（ 1）图：点 V和边 E的集合，用以表示对某种现实事物
的抽象。记作 G=｛ V,E｝,V=｛ v1,v2,···,vn｝,
E=｛ e1,e2,···,em｝
点：表示所研究的事物对象；
边：表示事物之间的联系。
v1 v
2
v3 v4
v0e
1 e2
e3
e4
e5
e6 e7
e0
（ 2）若边 e的两个端点重
合，则称 e为环。
（ 3）多重边：若某两端点之
间多于一条边，则称为多重边。
2010-5-14
--第 6章 图与网络分析 --
--4--
（ 4）简单图：无环、无多重边的图称为简单图。
（ 5）链：点和边的交替序列，其中点可重复，但边不能
重复。
（ 6）路：点和边的交替序列，但点和边均不能重复。
（ 7）圈：始点和终点重合的链。
（ 8）回路：始点和终点重合的路。
（ 9）连通图：若一个图中，任意两点之间至少存在一条
链，称这样的图为连通图。
（ 10）子图，部分图：设图 G1=｛ V1,E1｝,G2={V2,E2},
如果有 V1?V2,E1?E2，则称 G1是 G2的一个子图；若
V1=V2,E1?E2，则称 G1是 G2的一个部分图。
（ 11）次：某点的关联边的个数称为该点的次，以 d(vi)表示。
2010-5-14
--第 6章 图与网络分析 --
--5--
二、图的模型
例：有甲、乙、丙、丁、戊、己六名运动员报名参加 A、
B,C,D,E,F六个项目的比赛。如表中所示，打,√”的
项目是各运动员报名参加比赛的项目。问：六个项目的比赛
顺序应如何安排，才能做到使每名运动员不连续地参加两项
比赛？
甲
乙
丙
丁
戊
己
人 A B C D E F
√ √
√ √ √
√ √
√ √
√ √
√ √
2010-5-14
--第 6章 图与网络分析 --
--6--
建立模型：
解：项目作为研究对象，排序。
设 点：表示运动项目。
边：若两个项目之间无同一名运动员参加。
A
B
C
D
E
F A— C— D— E— F— B
A— F— E— D— C— B
A— C— B— F— E— D
A— F— B— C— D— E
顺序：
2010-5-14
--第 6章 图与网络分析 --
--7--
§ 6.2 树图和图的最小部分树
（ 1）树：无圈的连通图称为树图，简称为树。
一、树图的概念
2010-5-14
--第 6章 图与网络分析 --
--8--
（ 2）树的特性：
① 树是边数最多的 无圈 连通图。在树中任加一条边，就会形成圈。
② 树是边数最少的连通图。在树中任减一条边，则不连通。
（ 3）图的最小部分树：
定义：若 G1是 G2的一个部分图，且为树图，则称 G1是
G2的一个部分树。
G2,A
B
C
D
5
47
3
6 5
5
7
6
G1,A C
B
D
2010-5-14
--第 6章 图与网络分析 --
--9--
定义：树枝总长为最短的部分树称为图的最小部分树。
二、最小部分树的求法
例：要在下图所示的各个位置之间建立起通信网
络，试确定使总距离最佳的方案。
树枝：树图中的边称为树枝。
2010-5-14
--第 6章 图与网络分析 --
--10--
S
A
B
C
D
E
T5
4
5 5
最小部分树长 Lmin=14
2010-5-14
--第 6章 图与网络分析 --
--11--
1,避圈法：将图中所有的点分 V为 V两部分，
V—— 最小部分树内点的集合
V—— 非最小部分树内点的集合
⑴ 任取一点 vi加粗，令 vi∈ V，
⑵ 取 V中与 V相连的边中一条最短的边 (vi,vj)，
加粗 (vi,vj)，令 vj∈ V
⑶ 重复⑵,至所有的点均在 V之内。
2,破圈法：
⑴ 任取一圈，去掉其中一条最长的边，
⑵ 重复，至图中不存在任何的圈为止。
2010-5-14
--第 6章 图与网络分析 --
--12--
S
A
B
C
D
E
T5
4
5 5× ×
×
最小部分树长 Lmin=14
2010-5-14
--第 6章 图与网络分析 --
--13--
§ 6.3 最短路问题
在图示的网络图中，从给定的点 S出发，要到达目
的地 T。问：选择怎样的行走路线，可使总行程最短？
方法,Dijkstra（ D氏）标号法 —— 按离出发点的距离由
近至远逐渐标出最短距离和最佳行进路线。
S
1．求某两点间最短距离的 D（ Dijkstra）氏标号法
2 4 7
2010-5-14
--第 6章 图与网络分析 --
--14--
S
A
B
C
D
E
T5
4
5 5
0
2
4
4 7
89 14 135
4
最短路线,S ? A?B ? E ? D ? T
最短距离,Lmin=13
2010-5-14
--第 6章 图与网络分析 --
--15--
2．求任意两点间最短距离的矩阵算法
⑴ 构造任意两点间直接到达的最短距离矩阵 D（ 0） = ? dij（ 0） ?
S A B C D E T
S 0 2 5 4 ? ? ?
A 2 0 2 ? 7 ? ?
B 5 2 0 1 5 3 ?
C 4 ? 1 0 ? 4 ?
D ? 7 5 ? 0 1 5
E ? ? 3 4 1 0 7
T ? ? ? ? 5 7 0
D（ 0） =
⑵ 构造任意两点间直接到达、或者最多经过 1个中间点到达的最
短距离矩阵 D（ 1） = ? dij（ 1） ?
2010-5-14
--第 6章 图与网络分析 --
--16--
其中 dij（ 1） = min { dir（ 0） + drj（ 0） },
S A B C D E T
S 0 2 4 4 9 8 ?
A 2 0 2 3 7 5 12
B 4 2 0 1 4 3 10
C 4 3 1 0 5 4 11
D 9 7 4 5 0 1 5
E 8 5 3 4 1 0 6
T ? 12 10 11 5 7 0
D（ 1） =
i r j
dir（ 0） drj（ 0）
r
dSE（ 1） = min {dSS（ 0） +dSE（ 0）,dSA（ 0） +dAE（ 0）,dSB（ 0） +dBE（ 0）,dSC（ 0） +dCE（ 0
）,
dSD（ 0） + dDE（ 0）,dSE（ 0） + dEE（ 0）,dST（ 0） + dTE（ 0） } =8
例如
2010-5-14
--第 6章 图与网络分析 --
--17--
其中 dij（ 2） = min { dir（ 1） + drj（ 1） }
S A B C D E T
S 0 2 4 4 8 7 14
A 2 0 2 3 6 5 11
B 4 2 0 1 4 3 9
C 4 3 1 0 5 4 10
D 8 6 4 5 0 1 5
E 7 5 3 4 1 0 6
T 14 11 9 10 5 6 0
D（ 2） =
i r jdir（ 1） drj（ 1）
r
⑶ 构造任意两点间最多可经过 3个中间点到达的最短距
离矩阵 D（ 2） = ? dij（ 2） ?
2010-5-14
--第 6章 图与网络分析 --
--18--
其中 dij（ 3） = min { dir（ 2） + drj（ 2） }
S A B C D E T
S 0 2 4 4 8 7 13
A 2 0 2 3 6 5 11
B 4 2 0 1 4 3 9
C 4 3 1 0 5 4 10
D 8 6 4 5 0 1 5
E 7 5 3 4 1 0 6
T 13 11 9 10 5 6 0
D（ 3） =
i
r
j
dir（ 2） drj（ 2）
r
⑷ 构造任意两点间最多可经过 7个中间点到达的最短距
离矩阵 D（ 3） = ? dij（ 3） ?
2010-5-14
--第 6章 图与网络分析 --
--19--
说明：
一般，对于 D（ k） = ? dij（ k） ?，其中
dij（ k） = min ?{dir（ k-1） + drj（ k-1） }, k=0,1,2,3,·····
最多可经过 2k-1个中间点,其数列为
{0,1,3,7,15,31,·····,2k-1,·····}
收敛条件：
① 当 D（ k+1） = D（ k） 时，计算结束；
② 设网络中有 p个点，即有 p-2个中间点，
则 2k-1-1 <p-2?? 2k-1 ? k-1<log2 (p-1) ? k
∴ K<log2(p-1)+1，
∴ 计算到 k=lg(p-1)/lg2 +1时，收敛，计算结束。
2010-5-14
--第 6章 图与网络分析 --
--20--
例：有 7个村镇要联合建立一所小学，已知各村镇小学
生的人数大致为 S— 30人,A— 40人,B— 20人,C— 15人，
D— 35人,E— 25人,T— 50人。问：学校应建在那一个地
点，可使学生总行程最少？
S A B C D E T
S 0 2 4 4 8 7 13
A 2 0 2 3 6 5 11
B 4 2 0 1 4 3 9
C 4 3 1 0 5 4 10
D 8 6 4 5 0 1 5
E 7 5 3 4 1 0 6
T 13 11 9 10 5 6 0
L=
30
40
20
15
35
25
50
人数
= [1325 1030 880 1035 910 865 1485]T
解：
2010-5-14
--第 6章 图与网络分析 --
--21--
§ 6.4 中国邮路问题
问题：一名邮递员从邮局出发，试选择一条最短的投
递路线？
v1
v2
v3
v4
v5
v6
v8 v
7
v9
v10
v11
v12
v13邮局
4
4 4
5
5
1 2
4
1
2
5 4 4
7 4
2
2
2010-5-14
--第 6章 图与网络分析 --
--22--
2010-5-14
--第 6章 图与网络分析 --
--23--
奇点：图中次为奇数的点称为奇点。
偶点：图中次为偶数的点称为偶点。
结论,最短投递路线应具有下述特征：
⑴ 若图中所有的点均为偶点，则可不重
复走遍所有街道；
⑵ 重复走的路线长度应不超过所在回路
总长度的一半。
2010-5-14
--第 6章 图与网络分析 --
--24--
步骤：
1,两两连接所有的奇点，使之均成为偶点；
2,检查重复走的路线长度，是否不超过其所在
回路总长的一半，若超过，则调整连线，改
走另一半。
2010-5-14
--第 6章 图与网络分析 --
--25--
v1
v2
v3
v4
v5
v6
v8 v
7
v9
v10
v11
v12
v13邮局
4
4 4
5
5
1 2
4
1
2
5 4 4
7 4
2
2
投递距离,L=60+18=78
2010-5-14
--第 6章 图与网络分析 --
--26--
§ 6.5 网络最大流问题
一、网络最大流中有关概念
⑴ 有向图：含有以箭头指示方向的边的网络图。
⑵ 弧：有向图上的边称为弧。用（ vi,vj）表示。
⑶ 弧的容量：弧上通过负载的最大能力，简称容量。以 cij表示。
⑷ 流：加在网络每条弧上的一组负载量，以 fij表示。
⑸ 可行流：能够通过网络的负载量，通常应满足两个条件：
① 容量限制条件：对所有的弧,0 ? fij?cij
② 中间点平衡条件：对任何一个中间点，流入量 =流出量
⑹ 发点、收点、中间点：流的起源点称发点，终到点称收点，其余的
点称中间点。
⑺ 最大流；能够通过网络的最大流量。
⑻ 割集：一组弧的集合，割断这些弧，能使流中断。简称割。
2010-5-14
--第 6章 图与网络分析 --
--27--
v1
vs
v2
v3
v4
vt
9(4)
9(9)
6(1)
(0,+∞)
(vs,2)
(v2,2) (v1,2)
(v3,1)
(v4,1)
5(4)
cij fij
2010-5-14
--第 6章 图与网络分析 --
--28--
⑼ 割的容量：割集中各弧的容量之和。
⑽ 最小割：所有割集中容量之和为最小的一个割集。
⑾ 前向弧 μ+：一条发点到收点链中，由发点指向收点的弧，又称正向弧。
⑿ 后向弧 μ-：一条发点到收点链中，由收点指向发点的弧，又称逆向弧。
⒀ 增广链：由发点到收点之间的一条链，如果在前向弧上满足流量
小于容量，即 fij<cij，后向弧上满足流量大于 0，即 fij>0，则称这样的
链为增广链。
定理：网络的最大流量等于它的最小割集的容量。
定理：当网络中不存在任何增广链时，则网络达到最大流状态。
二、两个定理
2010-5-14
--第 6章 图与网络分析 --
--29--
s
t
设有如下增广链：
∵ △ f=1
∴ 该网络没有达到最大流状态。
2010-5-14
--第 6章 图与网络分析 --
--30--
三、网络最大流的标号算法 (Ford-Fulkerson标号算法 )
基本思想：寻找增广链，改善流量分布；再重复，直到不
存在任何增广链为止。
步骤：
① 给始点标号：（ 0,+∞）
② 从已标号点 i出发，看与其相关联的未标号点 j上的弧，
对 μ+，若有 0?fij<cij，则可对 j点标号，记（ i,ε (j)），
其中 ε (j)=min{ε (i), cij - fij}
对 μ-，若有 0 < fji? cij，也可对 j点标号，记（ i,ε (j)），
其中 ε (j)=min{ε (i), fji}
（注：若有多个可标号点，可任选其中之一。）
若标号中断，则得到最大流状态，否则，重复②，继续标
号，至收点得到标号，转③。
2010-5-14
--第 6章 图与网络分析 --
--31--
③ 当收点得到标号，则沿标号得到的增广链进行流量调整：
对 μ+,f?ij = fij +ε (t)
对 μ-,f?ij = fij -ε (t)
其余弧上的流量不变。
④ 重复上述过程。
⑤ 最小割集：已标号点集合与未标号点集合相连接的弧中，
流量 =容量的弧。
2010-5-14
--第 6章 图与网络分析 --
--32--
v1
vs
v2
v3
v4
vt
9(5)
9(9)
6(0)5(3)
(0,+∞)
(vs,1)
(v2,1) (v
1,1)
最大流量,fmax=14
最小割集：｛ (v3,vt),(v2,v4)｝
2010-5-14
--第 6章 图与网络分析 --
--33--
§ 6.6 网络模型的实际应用
例 1,王经理花费 12000元购买了一台微型车，以后年度的
维护费用取决于年初时汽车的役龄，如表示。为避免使用旧
车带来较高的维护费用，王经理可选择卖掉旧车，购买新车
使用的方案，旧车的预计收入如表示。为简化计算，假定任
何时刻购买新车都需花费 12000元，王经理的目标是使净费用
最小（购置费 +维护费 -卖旧车收入）。
役龄 (年 )
年维护费
预计收入
单位：元
0 1 2 3 4 5
2000 4000 5000 9000 12000 ——
—— 7000 6000 2000 1000 0
2010-5-14
--第 6章 图与网络分析 --
--34--
解,用网络图模型描述，归结为最短路问题。
7 7 7 7 71 2 3 4 5 6
12 12 12 12
21 21 21
31 31
44
1年初 5年末
2010-5-14
--第 6章 图与网络分析 --
--35--
例 2：图示岛屿与河岸有数座桥相联，问至少需要炸
毁几座桥，可中断两岸的交通？
A
B C
D
E
F
2010-5-14
--第 6章 图与网络分析 --
--36--
A
B C
F
ED
2 2
2 1
3
1
1
1
1
2010-5-14
--第 6章 图与网络分析 --
--37--
例 3：有 3根相同的轴 A1,A2,A3，另有三根相同的齿轮
B1,B2,B3。因为精度不高，不能做到任意的互相配合，
其中 A1能与 B1,B2配合,A2能与 B2,B3配合,A3能与
B1,B3配合。要求确定合适的配合方案，以得到最多的
配合数，将此问题归为网络最大流问题。
A1
A2
A3
B1
B2
B3
1
1
1
1
1
1
S T
1
1
1
1
1
1
2010-5-14
--第 6章 图与网络分析 --
--38--
