运筹学课件第八章图与网络分析制作：北京理工大学 吴祈宗等
2
第八章 图与网络分析图的基本概念与基本定理树和最小支撑树最短路问题网络系统最大流问题网络系统的最小费用最大流问题中国邮递员问题本章内容重点引 言图论应用非常广泛：
控制论,信息论,工程技术,交通运输,经济管理,电子计算机等领域；
科学研究,市场和社会生活中的许多问题,可以用图论的理论和方法来加以解决 。
例如,通信线路的架设,输油管道的铺设,铁路或者公路交通网络的合理布局 。
4
引 言将复杂的工程系统和管理问题用图的理论加以描述,可以解决许多工程项目和管理决策的优化问题 。
图论越来越受到工程技术人员和经营管理人员的重视 。
5
引 言
1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文,
解决了著名的哥尼斯堡七座桥问题 。
德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,河的两岸和岛屿之间有七座桥相互连接,
如图 8-1a所示 。
引 言
A B
图 8-1 a）
C
D
引 言当地的居民热衷于这样一个问题,一个漫步者如何能够走过这七座桥,并且每座桥只能走过一次,最终回到原出发地 。
尽管试验者很多,但是都没有成功 。
为了寻找答案,1736年欧拉将这个问题抽象成图 8-1b所示图形的一笔画问题 。
即能否从某一点开始不重复地一笔画出这个图形,最终回到原点 。 欧拉在他的论文中证明了这是不可能的,因为这个图形中每一个顶点都与奇数条边相连接,不可能将它一笔画出,这就是古典图论中的第一个著名问题 。
8
引 言图 8-1 b）
A
C
D
B
在实际的生产和生活中,人们为了反映事物之间的关系,常常在纸上用点和线来画出各式各样的示意图 。
例 8.1:图 8-2是我国北京,上海,
重庆等十四个城市之间的铁路交通图,
这里用点表示城市,用点与点之间的线表示城市之间的铁路线 。 诸如此类还有城市中的市政管道图,民用航空线图等等 。
1.图的基本概念与基本定理
10
1.图的基本概念与基本定理太原重庆 武汉 南京徐州 连云港上海郑州石家庄 塘沽青岛济南天津北京图 8-2
11
例 8.2:有六支球队进行足球比赛,我们分别用点 v1… v6表示这六支球队,它们之间的比赛情况,
也可以用图反映出来,已知 v1队战胜 v2队,v2队战胜 v3队,v3队战胜
v5队,如此等等 。 这个胜负情况,
可以用图 8-3所示的有向图反映出来 。
1.图的基本概念与基本定理
12
1.图的基本概念与基本定理
v3
v1
v2 v4
v6
v5
图 8-3
图论中常用 点和点之间的线 所构成的图,反映实际生产和生活中的某些特定对象之间的特定关系 。 一般来说,通常 用点表示研究对象,用点与点之间的线表示研究对象之间的特定关系 。
在一般情况下,图中的相对位臵如何,
点与点之间线的长短曲直,对于反映研究对象之间的关系,显的并不重要 。
因此,图论中的图与几何图,工程图等本质上是不同的 。
1.图的基本概念与基本定理通常把点与点之间不带箭头的线叫做边,带箭头的线叫做 弧 。
如果一个图是由点和边所构成的,那么,称为为 无向图,记作 G =(V,E),其中 V表示图 G的点集合,E表示图 G的边集合 。 连接点 vi,vj?V的边记作 [vi,vj],或者
[vj,vi]。
如果一个图是由点和弧所构成的,
那么称为它为 有向图,记作 D =(V,A),其中 V 表示有向图 D的点集合,A表示有向图
D的弧集合 。 一条方向从 vi指向 vj的弧,记作 (vi,vj)。
例如,图 8-4是一个无向图 G=（ V,E）
其中 V = {v1,v2,v3,v4}
E = { [v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],
[v2,v4],[v3,v3] }
1.图的基本概念与基本定理
v3
v2v1
v4图 8-4
16
图 8-5是一个有向图 D=（ V,A）
其中 V = {v1,v2,v3,v4,v5,v6,v7}
A = {(v1,v2),(v1,v3),(v3,v2),(v3,v4),
(v2,v4),(v4,v5),(v4,v6),(v5,v3),
(v5,v4),(v5,v6),(v6,v7)}
1.图的基本概念与基本定理
v7v5v3
v4v2
v1 v
6
图 8-5
一些常用的名词：无向图 G 或 有向图 D
节点数 记作 P(G)或 P(D),简记作 P,
边数 或者 弧数 记作 q(G)或者 q(D),
简记作 q。
如果边 [vi,vj]?E,那么称 vi,vj是 边的端点,或者 vi,vj是 相邻 的 。
如果一个图 G中,一条边的两个端点是相同的,那么称为这条边是 环 。
1.图的基本概念与基本定理
1.图的基本概念与基本定理
如果两个端点之间有两个端点之间有两条以上的边,那么称为它们为 多重边 。
一个无环,无多重边的图为 简单图 。
一个无环,有多重边的图称为多重图 。
v3
v2v1
v4 图 8-4
环
以点 v为端点的边的个数称为点 v 的度,记作 d(v) 。 如 上 图 中 d(v1)=3,
d(v2)=4,d(v3)=4,d(v4 )=3。
度为零的点称为 弧立点,度为 1的点称为 悬挂点 。 悬挂点的边称为 悬挂边 。
度为奇数的点称为 奇点,度为偶数的点称为 偶点 。
1.图的基本概念与基本定理
20
端点的度 d(v)：点 v 作为边端点的个数；
奇点,d(v)=奇数；
偶点,d(v)=偶数；
悬挂点,d(v)=1；
悬挂边,与悬挂点连接的边；
孤立点,d(v)=0；
空图,E =?，无边图
1.图的基本概念与基本定理定理 8.1 所有顶点次数之和等于所有边数的 2倍。
定理 8.2 在任一图中，奇点的个数必为偶数。
1.图的基本概念与基本定理
22
图的连通性：
链,由两两相邻的点及其相关联的边构成的点边序列 ; 如,
v0,e1,v1,e2,v2,e3,v3,…,v n-1,en,vn ;
v0,vn分别为链的起点和终点；
简单链,链中所含的边均不相同；
初等链,链中所含的点均不相同,
也称通路；
1.图的基本概念与基本定理
23
回路,若 v0 ≠ vn 分称该链为开链，否则称为闭链或回路；
圈,除起点和终点外链中所含的点均不相同的闭链；
连通图,图中任意两点之间均至少有一条通路，否则称作不连通图。
1.图的基本概念与基本定理子图,设 G1=[ V1,E1 ],G2=[ V2,E2 ]
子图定义,如果 V2? V1,E2? E1 称 G2 是
G1 的子图；
真子图,如果 V2? V1,E2? E1 称 G2 是 G1
的真子图；
部分图 （支撑子图）,如果 V2 = V1,
E2? E1 称 G2 是 G1 的部分图；
导出子图,若 V2? V1,E2={[vi,vj]:vi,vj?V2},
称 G2 是 G1 中由 V2 导出 的导出子图。
1.图的基本概念与基本定理有向图：关联边有方向弧,有向图的边 a=(u,v),起点 u,终点 v;
路,若有从 u 到 v 不考虑方向的链,且各方向一致,则称之为从 u到 v的路；
初等路,各顶点都不相同的路；
初等回路,u = v 的初等路 ;
连通图,若不考虑方向是无向连通图 ;
强连通图,任两点有路 ;
1.图的基本概念与基本定理
30
2.树和最小支撑树一,树及其性质在各种各样的图中,有一类图是十分简单又非常具有应用价值的图,这就是 树 。
例 8.3：已知有六个城市,它们之间要架设电话线,要求任意两个城市均可以互相通话,并且电话线的总长度最短 。
2.树和最小支撑树如果用六个点 v1,…,v6代表这六个城市,在任意两个城市之间架设电话线,即在相应的两个点之间连一条边 。
这样,六个城市的一个电话网就作成一个图 。 由于任意两个城市之间均可以通话,这个图必须是连通图 。 并且,这个图必须是无圈的 。 否则,从圈上任意去掉一条边,剩下的图仍然是六个城市的一个电话网 。 图 8-8是一个不含圈的连通图,代表了一个电话线网 。
32
2.树和最小支撑树图 8-8
v6
v3
v4
v2
v5
v1
2.树和最小支撑树定义 8.1 无圈的连通图叫做树 。
性质：
定理 8.3 设图 G=(V,E)是一个树 P(G) ≥2,那么图 G中 至少有两 个悬挂点 。
定理 8.4 图 G=（ V,E） 是一个树的充要条件是 G不含 圈,并且 有且仅有 P-1条边 。
34
2.树和最小支撑树定理 8.5 图 G=（ V,E） 是一个树的充要条件是 G是 连通图,并且 有且仅有 P-1条边 。
定理 8.6 图 G是一个树的充分必要条件是 任意两个顶点之间有且仅有一条链 。
35
2.树和最小支撑树从以上定理,不难得出以下结论：
（ 1） 从一个树中任意去掉一条边,那么剩下的图不是连通图,亦即,在点集合相同的图中,树是含边数最少的连通图 。
（ 2） 在树中不相邻的两个点之间加上一条边,那么恰好得到一个圈 。
2.树和最小支撑树二,支撑树定义 8.2 设图 K=(V,E’)是图 G=(V,E)的一支撑子图,如果图 K=(V,E’)是一个树,
那么称 K是 G的一个支撑树 。
图 8.10b 是图 8-10a 的一个支撑树 。
v6
v5
v2
v3
v4
v1 v
6
v5
v2
v3
v4
v1
图 8-10a） b）
2.树和最小支撑树
显然,如果图 K=( V,E’ )是图 G=(V,E)的一个 支撑树,那么 K 的边数是 p(G)-1；
G中不属于支撑树 K的边构成 K的 余树,
其边数是 q(G)-p(G)+1。
定理 8.7 一个图 G有支撑树的充要条件是 G是连通图。
证明,必要性 显然；
充分性,设图 G是连通的，若 G不含圈，则
G是一个树，从而 G是自身的一个支撑树。
若 G含圈，则任取 G的一个圈，从该圈中任意去掉一条边，得到图 G的一支撑子图 G1。若 G1不含圈，则 G1是 G的一个支撑树。
若 G1仍然含圈，则任取 G1的一个圈，再从圈中任意去掉一条边，得到图 G的一支撑子图 G2。依此类推，可以得到图 G的一个支撑子图 GK，且不含圈，从而 GK是一个支撑树。
41
2.树和最小支撑树以上充分性的证明，提供了一个寻找连通图支撑树的方法叫做,破圈法,。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。
42
2.树和最小支撑树
例 8.4:用破圈法求出下图的一个支撑树。
V5V4
V2
V3
V1
e6e5
e4
e3
e2
e1 e7
e8
43
取一个圈 (v1,v2,v3,v1)，在一个圈中去掉边 e3 。在剩下的图中，再取一个圈（ v1,v2,v4,v3,v1），去掉边 e4。再从圈（ v3,v4 v5,v3）中去掉边 e6。再从圈 (v1,v2,v5,v4,v3,v1 ）中去掉边 e7，这样，剩下的图不含圈，于是得到一个支撑树，如图所示。
v2e
1
e2 e5
e8v1
v3
v4
44
2.树和最小支撑树三、最小支撑树问题定义 8.3 如果图 G =（ V，
E），对于 G中的每一条 [vi,vj]，
相应地有一个数 wij，那么称这样的图 G为 赋权图,wij称为边 [vi,vj]
的权。
这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的含义。例如长度，费用、流量等等。
2.树和最小支撑树定义 8.4 如果图 T =（ V,E’）
是图 G 的一个支撑树，那么称 E’上所有边的权之和为 支撑树 T 的权,
记作 S(T)。
如果图 G 的支撑树 T* 的权 S(T*)，
在 G 的所有支撑树 T 中的权最小，
即 S(T*) = minS(T)，那么称 T*是 G 的最小支撑树 。
46
2.树和最小支撑树常用的有 破圈法 和 生长法（避圈法） 两个方法：
（ 1） 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；
（ 1） 去掉该圈中权数最大的边；
反复重复 （ 1）（ 2） 两步，直到最短树。
47
2.树和最小支撑树例 8.5 某六个城市之间的道路网如图 8-13a所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。
2.树和最小支撑树
v6
v5
v2
v3
v4
图 8-13a
v1
6
2
7
5
3
5
4
4
v3
v2
v1
v4
v6
v5
5
1
31
4
2
图 8-13b
顺序,浅兰,黄,粉红,白
2.树和最小支撑树解,如图 8-13a，用破圈法求解最小支撑树。
（ 1） 圈 v1,v2,v3,v1,删圈中权最大边 [v1,v3]；
（ 2）圈 v3,v5,v2,v3,去掉边 [v2,v5]；
（ 3）圈 v3,v5,v4,v2,v3,去掉边 [v3,v5]；
（ 4）圈 v5,v6,v4,v5,这里有两条权最大的边
[v5,v6]和 [v4,v6]。任意删一条，如 [v5,v6]。
这时得到一个不含圈的图,即是最小支撑树。
如图 8-13b所示。
50
2.树和最小支撑树从网络图中依次寻找 权数较小的边,寻找过程中，节点不得重复，即 不得构成圈 。注意在找较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最短树或证明网络不存在最短树。
2.树和最小支撑树用,生长法,求解例 8.5
解,考虑赋权图 8-13a，任取一点，如
从 v1 取权较小的边（ v1,v2 ）；
从 v2 取 权较小的边（ v2,v3 ）；
从 v3 取 权较小的边（ v3,v4 ）；
同理依次取（ v4,v5），（ v4,v6 ） 。
这时得到了如图 8-13b所示的最小支撑树。
2.树和最小支撑树
v6
v5
v2
v3
v4
图 8-13a
v1
6
2
7
5
3
5
4
4
v3
v2
v1
v4
v6
v5
5
1
31
4
2
图 8-13b
顺序,黄,粉红,白,绿,浅兰
53
作业：
用破圈法和生长法两种方法求解
习题 — 1
54
3.最短路径问题一,引言最短路径问题是图论中十分重要的最优化问题之一,它作为一个经常被用到的基本工具,可以解决生产实际中的许多问题,
比如城市中的管道铺设,线路安排,工厂布局,设备更新等等 。
也可以用于解决其它的最优化问题 。
55
3.最短路径问题例 8.6,如图 8-14所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从 v1出发，经过这个交通网到达 v8，要寻求是总路程最短的线路。
图 8-14
v1
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
1
56
3.最短路径问题从 v1到 v8的路线是很多的 。
比如从 v1出发,经过 v2,v5到达 v8
或者从 v1出发,经过 v4,v6,v7到达 v8等等 。 但不同的路线,经过的总长度是不同的 。 例如,按照第一个线路,总长度是 6+1+6=13
单位,按照第二个路线,总长度是 1+10+2+4=17单位 。
一般意义下的最短路问题：
设赋权有向图 D =（ V,A）,对每个弧 a =（ vi,vj）,相应地有权 wij。 vs,vt是 D中的两个顶点,P是 D中从 vs到 vt的任意一条路,定义路的权是 P中所有弧权的和,记作 S(p)。
最短路问题就是求 S(P0)=minS(p)。 P0
叫做从 vs到 vs的 最短路 。 P0的权 S(P0)叫做从 vs到 vt的 距离,记作 d（ vs,vt） 。
由于 D是有向图,很明显 d（ vs,vt）
与 d（ vt,vs） 一般不相等 。
58
3.最短路径问题二,Dijkstra（ 狄克斯拉方法 ） 算法下面介绍在一个赋权有向图中寻求最短路的方法 —— Dijkstra算法,
它是在 1959年提出来的 。 目前公认,
在所有的权 wij ≥ 0时,这个算法是寻求最短路问题最好的算法 。 并且,
这个算法实际上也给出了 寻求从一个始定点 vs到任意一个点 vj的最短路 。
Dijkstra算法的基本思想从 vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数，
叫做一个点的 标号,分为两类：
P 标号,表示从 vs到该点的最短路权
T 标号,表示从 vs到该点最短路权的上界。
算法的每一步是去修改 T 标号，把某一个具有 T 标号的点改变为具有 P 标号的点，使图 D 中具有 P 标号的顶点多一个。
这样，至多经过 P -1步，就可求出从 vs到各点 vj的最短路。
说明,在例 8.6中
S=1。 因为 wij≥0,d (v1,v1)=0。 这时,
v1是具有 P标号的点 。
再看从 v1出发的三条弧 (v1,v2),(v1,v3)
和 (v1,v4)。 如果从 v1出发沿 (v1,v2)到达 v2，
这时的路程是 d (v1,v1) + w12= 6单位；
如果从 v1出发,沿 (v1,v3)到达 v3,则是
d (v1,v1) + w13 = 3单位；
同理,如果从 v1出发沿 (v1,v4)到达 v4，
是 d（ v1,v1） + w14 = 1单位 。
说明 （续）
因此,从 v1出发到达 v4的最短路必是 （ v1,v4）,d（ v1,v4） =1。 这是因为从 v1到达 v4的任一条路,假如不是
（ v1,v4）,则必先沿 （ v1,v2） 到达 v2，
或者沿 （ v1,v3） 到达 v3,而这时的路程已是 6或者 3单位 。 由于 wij ≥ 0,因此不论他如何再从 v2或者 v3到达 v4,所经过的总路程都不会比 1少,于是就有
d（ v1,v4） =1。 于是 V4变成具有 P标号的点 。
例 8.6说明：
从 v1出发的三条弧 (v1,v2),(v1,v3)和
(v1,v4)，
min{d(v1,v1)+w12,d(v1,v1)+w13,d(v1,v1)+w14}
= d（ v1,v4） =1。
P(V4)
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
P(V1)
1
再看从 v1和 v4指向其余点的弧：从 V1出发,分别沿 (v1,v2),(v1,v3 )到达 v2,v3,经过的路程是 6或者 3单位；从 v4出发沿 (v4,v6)到达 v6,经过的路程是 d(v1,v4)+w46=1+10=11
单位 。 而
min{d(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46}=
d（ v1,v1） +w13=3单位 。
根据同样的理由,可以断定,从 v1到达 v3的最短路是 （ v1,v3）,d（ v1,v3） =3。
这样,又使点 v3变为具有 P 标号的点,不断重复以上过程,就可以求出从 vs到达任一点 vj的最短路 。
例 8.6说明（续）：
再看从 v1和 v4指向其余点的弧,
min{d(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46}
=d（ v1,v1） +w13=3 。
P(V4)
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10P(V1) P(V3)
1
3.最短路径问题在下述的 Dijkstra算法中,以 P,T 分别表示某一个点的 P 标号,T 标号 。 Si表示在 第 i步时,具有 P 标号点的集合,为了在算出从 vs到各点的距离的同时,也找出从 vs到各点的最短路,于是,给每一个点 v一个 λ 值 。 当算法结束时,如果
λ(v) = m,则表示在从 vs到 v 的最短路上,
v 的 前一个点是 vm。 如果 λ (v)=M,则表示在图 D 中不含有从 vs 到达 v 的路 。
λ(v) =0,表示 v=vs。
Dijkstra算法的步骤如下：
开始 （ i=0）
令 S0={vs},P（ vs） =0,λ(vs)=0,对每一个 v ≠vs,令 T（ v） =+∞,λ(v)=M,令
k=s；
（ 1） 如果 Si=V,则算法结束,对每一个
v?Si,d（ vs,v） =P（ v） 。 否则转入 （ 2） ；
（ 2） 考察每一个使 (vk,vj)?A,且 vj?Si的点 vj,如果 T(vj)>P(vk)+wkj,则把 T(vj)改变为 P(vk)+wkj,把 λ(vj)改变为 k,否则转入
（ 3） ；
67
3.最短路径问题
（ 3） 令 T(vji)=min{T(vj)?vj?Si}，
如果 T(vji)<+∞，则把 vji的 T 标号改变为 P 标号 P(vji)=T(vji)，令
Si+1=Si∪ {vji},k=ji，把 i换成 i+1，
转入（ 1）；否则结束。
这时，对 v?Si,d(vs,v) = P(v)；
对 v?Si,d(vs,v) =T(v)。
3.最短路径问题用 Dijkstra算法求解例 8.6。 vs为起点,
开始,s =1,i=0; S0={v1},P(v1)=0,λ(v1)=0,
T(vi)=+∞,λ(vi)=M,i=2,3,… 9,k=1。
(2) (v1,v2)∈ A,v2?S0,P(v1)+w12<T(v2)，
故将 T(v2)改变为 P(v1)+w12=6,λ(v2)改变为
1。 同理,将 T(v3)改变为 P(v1)+w13=3,λ(v3)
改变为 1,将 T(v4)改变为 P(v1)+w14=1,λ(v4)
改变为 1。
69
3.最短路径问题
（ 3） 在所有的 T标号中,T(v4)=1最小,
于 是令 P(v4)=1,S1=S0∪ {v4}={v1,v4},
k=4。
i=1：
（ 2） 将 T(v6)改变为 P(v4)+w46=11，
λ(v6) 改变为 4。
（ 3） 在所有的 T标号中,T(v3)=3最小,
于是令 P(v3)=3,S2={v1,v4,v3},k=3。
i=2：
（ 2） (v3,v2)∈ A,v2?S2,T(v2)>w32+P(v3)，
将 T(v2)改变为 P(v3)+w32=5,λ(v2)改变为 3。
（ 3） 在所有的 T标号中,T(v2)=5最小,
于是令 P(v2)=5,S3={v1,v4,v3},k=2。
i=3：
（ 2） 将 T(v5)改变为 P(v2)+w25=6,λ(v5) 改变为 2。
（ 3） 在所有的 T标号中,T(v5)=6最小,
于是令 P(v5)=6,S4={v1,v4,v3},k=5。
3.最短路径问题
（ 2） 将 T(v6),T(v7),T(v8)分别改变为 10,
9,12,将 λ(v0),λ(v7),λ(v8)改变为 5。
（ 3） 在所有的 T标号中,T(v7)=9最小,于是令 P(v7)=9,S5={v1,v4,v3,v2,v5,v7},v=7。
i=5：
（ 2） （ v7,v8） ∈ A,v8?S5,但是
T(v8) < w78+P(v7),故 T(v8)不变 。
（ 3） 在所有的 T标号中,T(v6)=10最小,
于是,令 P(v6)=10,S6={v1,v4,v3,v2,v5,v7,v6}，
k=6。
3.最短路径问题i=6：
（ 2） 从 v6出发没有弧指向不属于 S6的点,
因此转入 （ 3） 。
（ 3） 在所有的 T标号中,T(v8)=12最小,
令 P(v8)=12,S7={v1,v4,v3,v2,v5,v7,v6,v8},
k=8。
i=7：
仅有 T标号的点为 v9,T（ v9） =+∞,算法结束 。
此时,把 P标号和 λ值标在图中,如图
8-15所示例题求解图示（ 1）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
T(V6)= +?
T(V7)= +(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=M
(V5)=M
T(V2)= 6 T(V5)= +?
T(V8)= +?
(V7)=M
(V2)=1
(V8)=M
T(V9)=+?
(V9)=M
T(V3)= 3
(V3)=1
1
i = 0 S1=S0∪ {v4}={v1,v4}
v1 v3
例题求解图示（ 2）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
T(V6)=11
T(V7)=+(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=4
(V5)=M
T(V2)=6 T(V5)=+?
T(V8)=+?
(V7)=M
(V2)=1
(V8)=M
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
i = 1 S2=S1∪ {v3}={v1,v4,v3}
v1 v3
例题求解图示（ 3）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
T(V6)=11
T(V7)=+(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=4
(V5)=M
P(V2)=5 T(V5)=+?
T(V8)=+?
(V7)=M
(V2)=3
(V8)=M
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
i = 2 S3=S2∪ {v2}={v1,v4,v3,v2}
v1 v3
例题求解图示（ 4）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
T(V6)=11
T(V7)=+(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=4
(V5)=2
P(V2)=5 P(V5)=6
T(V8)=+?
(V7)=M
(V2)=3
(V8)=M
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
i = 3 S4=S3∪ {v5}={v1,v4,v3,v2,v5}
v1 v3
例题求解图示（ 5）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
T(V6)=10
P(V7)=9?(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=5
(V5)=2
P(V2)=5 P(V5)=6
T(V8)=12
(V7)=5
(V2)=3
(V8)=5
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
i = 4 S5=S4∪ {v7}={v1,v4,v3,v2,v5,v7}
v1 v3
例题求解图示（ 6）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
P(V6)=10
P(V7)=9?(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=5
(V5)=2
P(V2)=5 P(V5)=6
T(V8)=12
(V7)=5
(V2)=3
(V8)=5
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
i = 5 S6=S5∪ {v6}={v1,v4,v3,v2,v5,v7,v6}
v1 v3
例题求解图示（ 7）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
P(V6)=10
P(V7)=9?(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=5
(V5)=2
P(V2)=5 P(V5)=6
P(V8)=12
(V7)=5
(V2)=3
(V8)=5
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
i = 6 S7 =S6∪ {v8}={v1,v4,v3,v2,v5,v7,v6,v8}
v1 v3
例题求解图示（ 8）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
P(V6)=10
P(V7)=9?(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=5
(V5)=2
P(V2)=5 P(V5)=6
P(V8)=12
(V7)=5
(V2)=3
(V8)=5
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
最短路,V1-(V4)V3-V2-V5-(V6,V7)V8
v1 v3
81
3.最短路径问题图 8-15中,从 v1到 v8的最短路：因为 λ(v8)=5,故最短路经过点 v5；又因为 λ(v5)=2,故最短路经过点 v2；依次类推,λ(v2)=3,λ(v3)=1于是,最短路经过点 v3,v1。 这样,从 v1到 v8的最短路是 （ v1,v3,v2,v5,v8） 。 同理,
可以求出从 v1到任一点 vi的最短路,
显然不存在从 v1到 v9的最短路 。
3.最短路径问题对于一个赋权 (无向 )图 G=(V,E)，
因为边 [vi,vj]可以看作 2条弧 （ vi,vj） 和
(vj,vi),并且具有相同的权 wij。 这样,在一个赋权 （ 无向 ） 图中,如果有所有的权 wij≥0,只要将 Dijkstra算法中的
,(2)看作每一个使 (vk,vj)?A,且 vj?Sj的点 vj”改变为,(2)看作每一个使 [vk,vj]?E，
且 vj?Sj的点 vj”而其他的条件不变,同样可以求出从 vs到各点的最短路 （ 对于无向图叫做最短链 ） 。
83
3.最短路径问题
习题,
将例 8-6中所示的赋权有向图的箭头去掉,然后求出无向图中从 vs到各点的最短路 。
84
作业：
P220— 2
略去证明证明 Dijkstra算法 。
只须证明?v∈ Si,P(v)是从 vs到 v
的最短路权,即 P(v)=d(vs.v)。
证,用数学归纳法 。 当 i=0时,结论显然成立 。 假设 i=n时,结论成立 。
看 i=n+1的情形,由于 Sn+1=Sn∪ {vjn},
所以只要证明 P(vjn)=d(vs,vj)。
根据算法,vjm是具有最小 T标号的点,即 Tn(vjn)=min{Tn(vj)},其中 vj?Sm.这里,用 Tn(ν)表示当 i=n时,执行步骤 （ 3）
时点 ν的 T标号 。 设 H是图 D中任意一条从
vs到 vjn的路 。
因为 vs∈ Sn,而 vjn?Sn,所以从 vs出发，
沿 H 必存在一条弧，其始点属于 Sn，而终点不属于 Sn。令（ vr,vl）是第一条这样的弧，于是 H =(vs…v r,vl…v jn),
s(H )=S((vs,vr))+wrl+S((vl…v jn))。
3.最短路径问题
由归纳假设,P(vr)是从 vs到 vr的最短路权,
于是,有 S(H)≥P(vr) + wrl+S((vl… vjn))。 根据算法中的 T标号修改规则,因为
vr∈ Sn,vl?Sn,故 P(vr) + wrl ≥Tn(vl),而
Tn(vl) ≥Tn(vjn),且 S((vl… vjn))≥0,所以 S(H)
≥ Tn(vjn)+S((vl,… vjn)) ≥ Tn(vjn)。
这样,就证明了 Tn(vjn)是从 vs到 vjn的最短权 。 根据算法,P(vjn)=Tn(vjn),于是就有
P(vjn)=d(vs,vjn)。
Dijkstra算法仅适合于所有的权 wij≥0的情形 。 如果当赋权有向图中存在有负权弧时,则该算法失效 。
例如图 8-16中,根据 Dijkstra算法,
可以得出从 v1到 v2最短路权是 2,但是这显然不对,因为从 v1 到 v2 的最短路是
（ v1,v3,v2）,权是 -1。
v1
v3
v22
2 -3
图 8-16
3.最短路径问题
Ford(福德 )算法,当赋权有向图存在负权弧时,求最短路的方法,
首先,设从任一点 vi 到任一点 vj 都有一条弧,如果在图 D 中,
（ vi,vj） 不属于 A,则添加弧 (vi,vj),
并且令 wij = +∞.
从 vs 到 vj 的最短路是从 vs 点出发,沿着这条路到某个点 vi,再沿弧 (vi,vj)到点 vj。
显然,从 vs到 vi的这条路必定是从 vs到 vi的最短路 。 否则从 vs到 vj
的这条路将不是最短路 。 于是,从
vs到 vj的距离 d(vs,vj)满足以下条件
d(vs,vj)=min{ d (vs,vi) + wij },
i
i=1,…,p,p = p(D)
3.最短路径问题
这个关系式的解 d(vs,v1)… d(vs,vp).可利用如下的 递推公式 求解
d(1)(vs,vj) = wsj,j =1,…,p,
d(t)(vs,vj) = min {d(t-1)(vs,vi)+ wij},t=2,3…i
当计算到第 k步时,对一切的 j =1,…,p,有
d(k)(vs,vj) = d(k-1)(vs,vj )
则 d(k)(vs,vj),j = 1,…,p,就是从 vs到各点 vj
的最短路径的权 。
92
设 C是赋权函数有向图 D中的一个回路 。 如果回路 C的权 S（ C） 是负数那么称 C是 D中的一个负回路 。
可以证明以下的结论：
（ 1） 如果赋权有向图 D不含有负回路,那么从 vs到任一点的最短路至多包含 P-2个中间点,并且必可取为初等路 。
此方法有如下结论
93
（ 2） 如果赋权有向图 D不含有负回路,那么上述递推算法至多经过 P-
1次迭代必收敛,可以求出从 vs到各个点的最短路权 。
（ 3） 如果上述算法经过 P-1次迭代,还存在在着某个 j,使得
d(p)(vs,vj)? d(p-1)(vs,vj),
那么 D中含有负回路 。 这时,不存在从 vs 到 vj 的路 （ 权无界 ） 。
94
3.最短路径问题例 8.7,在如图 8-17所示的赋权有向图中求从 v1到各点的最短路 。
解,利用上述递推公式,将求解结果列出如表 8-18所示 。
可以看出,当 t =4 时,有
d(t)(vs,vj)=d(t-1)(vs,vj) j =1,…,8
因此,表中的最后一列,就是从 v1到
v1,v2,…,v8的最短路权 。
95
3.最短路径问题
v8
v2
v4 v7
v5
v1 v3 v6
图 8-17
1
1
1
－ 1
－ 1
－ 1
－ 2
－ 3－ 3
－ 5
－ 52
2
3
6
7
8
终点起点
V1 V2 V3 V4 V5 V6 V7 V8 t=1 t=2 t=3 t=4
V1 0 -1 -2 3 0 0 0 0
V2 6 0 2 -1 -5 -5 -5
V3? -3 0 -5? 1 -2 -2 -2 -2
V4 8 0 2? 3 -7 -7 -7
V5? -1 0 1 -3 -3
V6 1 0 1 7? -1 -1 -1
V7 -1 0 5 -5 -5
V8 -3? -5 0 6 6
wij d(t)(vs,vj)
3.最短路径问题为了求出从 v1到各个点的最短路,
一般采用反向追踪的方法：如果已知
d(vs,vj),那 么 寻 求 一 个 点 vk,使得
d(vs,vk)+wkj=d(vs,vj),然后记录下 (vk,vj).在看 d(vs,vk),寻求一个点 vi,使得
d(vs,vi)+wik=d(vs,vk)… 依次类推,一直到达 vs为止 。 这样,从 vs到 vj的最短路是
（ vs,…,vi,vk,vj）,
98
在例中,由上表知,d(v1,v8)=6,
由于 d(v1,v6)+w68 = (-1) + 7 记录下 v6 ;
由于 d (v1,v3) + w36= d (v1,v6),j记录下 v3; 由于 d(v1,v1)+w13=d(v1,v3),
于是,从 v1到 v8的最短路是
(v1,v3,v6,v8)
99
作业：
用 Ford(福德 )算法求解
习题 --2
4,网络系统的最大流问题一 引言在许多实际的网络系统中都存在着流量和最大流问题 。 例如铁路运输系统中的车辆流,城市给排水系统的水流问题等等 。 而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题,它对于解决生产实际问题起着十分重要的作用 。
4,网络系统的最大流问题图 8-18
vt
v3
v2
v1
v4
vs
17
3
5
10
8
6
11
4
5
3
Cij
图 8-18是一个网络。弧旁边的权就是对应的容量（最大通过能力） 。 要求指定一个运输方案，
使得从 vs到 vt的货运量最大，这是寻求网络系统的最大流问题。
102
4.网络系统的最大流问题二,基本概念定义 8.5 设赋权有向图 D=(V,A),在
V中指定一个 发点 vs和一个 收点 vt,其他的点叫做中间点 。 对于 D中的每一个弧 (vi,vj)∈ A,都有一个权 cij 叫做 弧的容量 。 我们把这样的图 D 叫做一个网络系统,简称网络,记做 D =（ V，
A,C） 。
103
网络 D上的流指定义在弧集合 A上的一个函数 f = { f(vi,vj) } = { fij };
f(vi,vj)=fij叫做 弧在 (vi,vj)上的流量 。
105
4.网络系统的最大流问题网络系统上流的特点：
(1)发点的总流出量和收点的总流入量必相等；
(2)每一个中间点的流入量与流出量的代数和等于零；
(3)每一个弧上的流量不能超过它的最大通过能力 （ 即容量 ） 。
4.网络系统的最大流问题定义 8.6 网络上的一个流 f 叫做 可行流,
如果 f 满足以下条件：
（ 1 ） 容量条件,对于每一个弧
(vi,vj)∈ A,有 0? fij?cij ；
（ 2） 平衡条件,
对于发点 vs,有 ∑fsj -∑fjs= v( f )
对于收点 vt,有 ∑ftj -∑fjt =-v( f )
对于中间点,有 ∑fij -∑fji=0
其中发点的总流量 （ 或收点的总流量 ）
v( f )叫做这个 可行流的流量 。
107
4.网络系统的最大流问题
任意一个网络上的 可行流总是存在 的 。 例如零流 v ( f ) = 0,
就是满足以上条件的可行流 。
网络系统中 最大流问题 就是在给定的网络上寻求一个可行流
f,其流量 v ( f ) 达到最大值 。
108
饱和弧与零流弧
设流 f = { fij } 是网络 D上的一个可行流。我们把 D 中 fij = cij 的弧叫做 饱和弧,fij < cij 的弧叫做非饱和弧 ； fij > 0 的弧为 非零流弧,fij = 0 的弧叫做 零流弧 。
4.网络系统的最大流问题
设 μ是网络 D中连接发点 νs和收点 vt的一条链 。 定义链的方向是从 vs到 vt,于是链 μ上的弧被分为两类：一是弧的方向与链的方向相同,叫做 前向弧,前向弧的集合记做 μ+。 二是弧的方向与链的方向相反,叫做 后向弧,后向弧的集合记做 μ-。
在下图 （ 8-18与 8-19合并图） 中,(v4,v3)是饱和弧，其它弧均是非饱和弧、非零流弧。
如图在链（ vs,v1,v2,v3,v4,vt)中 μ={(v4,v3)}；
μ+={(vs,v1),(v1,v2),(v2,v3),(v4,vt)}。
v3
v2
v1
v4
vs
（ 17,2）
（ 3,3）
（ 5,2）
（ 10,5）
（ 8,3）
（ 6,3）
（ 11,6）
（ 4,1）
（ 5,1）
（ 3,2）
fij
vt
4.网络系统的最大流问题定义：如果链 μ满足以下条件：
1,在弧 (vi,vj)∈ μ+上,有 0 ≤ fij <
cij,即 μ+中的每一条弧是非饱和弧 。
2,在弧 (vi,vj)∈ μ-上,有 0< fij ≤
cij,即 μ-中的每一条弧是非零流弧 。
称链 μ为关于可行流 f 的一条 增广链 。
112
例如在上图中，
链 μ=（ vs,v1,v2,v3,v4,vt）就是一条增广链。
设图 D=(V,A,C ),点集 S,
T?V,S∩T=ф中 。 将起点在 S,终点在 T 的所有弧作成集合,记做
（ S,T） 。
113
4.网络系统的最大流问题定义 8.8 设一个网络 D=(V,A,C)。
如果点集 V被剖分为两个非空集合 V1
和 V1,发点 vs∈ V1,收点 vt∈ V1,那么将弧集 （ V1,V1） 叫做是 分离 vs和 vt的截集 。
定义 8.9 设一个截集 （ V1,V1）,将截集 （ V1,V1） 中所有的弧的容量的和叫做 截集的截量,记做 s(V1,V1),亦即 s(V1,V1) = ∑ cij。
(vi,vj)∈ (V1,V1)
114
4.网络系统的最大流问题显然：一个网络 D中,任何一个可行流 f 的流量 v( f )都小于或等于这个网络中任何一个截集 (V1,V1)的截量 。 并且,如果网络上的一个可行流 f *和网络中的一个截集 （ V1*,V1*）,
满足条件 v*(f * ) = c (V1*,V1* ),那么 f *
一定是 D上的最大流,而 （ V1*,V1*）
一定是 D的所有的截集中截量最小的一个 （ 即最小截集 ） 。
115
4.网络系统的最大流问题定理 8.8 网络中的一个可行流 f * 是最大流的充分必要条件是，不存在关于 f * 的增广链。
定理 8.9 在一个网络 D 中，
最大流的流量等于分离 vs和 vt的最小截集的截量。
说明：
若网络存在关于可行流 f 的增广链
令按增广链的定义，这里?> 0 。 取
ijijij
fm i n),fc(m i nm i n
。且是可行流，显然，
否则上在上在
)fv()f
~
v(f
~
,f
,f
,f
f
~
ij
ij
ij
ij
-
117
定理 8.8实际上提供了一个寻求网络系统最大流的方法：
如果网络 D 中有一个可行流 f，
只要判断网络是否存在关于可行流 f的增广链 。如果没有增广链，
那么 f一定是最大流。如有增广链，
那么可以按照前面说明，不断改进和增大可行流 f的流量，最终可以得到网络中的一个最大流。
三、标号法用给顶点标号的方法来定义 V1*。
在标号过程中,有标号的顶点是 V1*中的点,没有标号的点不是 V1*中的点 。
如果 vt 有了标号,则表示存在一条关于 f 的增广链 。 如果标号过程无法进行下去,并且 vt 未被标号,则表示不存在关于 f 增广链 。 这样,就得到了网络中的一个最大流和最小截集 。
4.网络系统的最大流问题
1,标号过程在标号过程中,网络中的点或者是 标号点 （ 分为已检查和未检查两种 ） 。 或者是 未标号点 。 每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的 。
以便找出增广链 。 第二个标号是为了用来确定增广链上的调整量 θ。
4.网络系统的最大流问题标号过程开始,先给 vs标号 (0,+∞)。
这时,vs是 标号未检查的点,其他都是未标号点 。 一般地,取一个标号未检查点 vi,对一切未标号点 vj：
1） 如果在弧 (vi,vj)上,fij < cij,那么给
vj标号 (vi,l(vj) ),其中 l(vj) = min[l(vi),cij-
fij]。 这时,vj 成为 标号未检查的点 。
4.网络系统的最大流问题
2） 如果在弧 (vj,vi)上,fij > 0,那么给
vj标号 (-vi,l(vj) ),其中 l(vj) = min [l(vi),
fij]。 这时,vj成为 标号未检查点 。
于是 vi成为标号已检查的点 。 重复以上步骤,如果所有的标号都已经检查过,
而标号过程无法进行下去,则标号法结束 。 这时的可行流就是最大流 。 但是,
如果 vt被标上号,表示得到一条增广链 μ，
转入下一步调整过程 。
122
2.调整过程首先按照 vt和其他的点的第一个标号,反向追踪,找出增广链 μ。 例如,
令 vt的第一个标号是 vk,则弧 （ vk,vt）
在 μ上 。 再看 vk的第一个标号,若是 vi，
则弧 (vi,vk)都在 μ上 。 依次类推,直到
vs为止 。 这时,所找出的弧就成为网络 D的一条增广链 μ。 取调整量 θ= l(vt),
即 vt的第二个标号,
4.网络系统的最大流问题
123
fij+θ,当 (vi,vj)∈ μ+
令 f ’ij= fij -θ,当 (vi,vj)∈ μ-
其他不变再去掉所有的标号,对新的可行流
f ’ = { f ’ij },重新进行标号过程,直到找到网络 D的最大流为止 。
4.网络系统的最大流问题
124
4.网络系统的最大流问题
V4
V1
V2
V3
Vs
（ 2,1）
（ 3,0）
（ 4,3）
（ 3,3）
（ 5,1）
（ 2,2）
（ 5,3）
（ 1,1）
（ 1,1）
(Cij,fij)
Vt
图 8-21
例 8.8,求图 8-21的网络最大流,弧旁的权数表示 （ cij,fij） 。 用标号法解解,1.标号过程 。
（ 1） 首先给 vs标号 （ 0,+∞）
（ 2） 看 vs,在弧 (vs,v2)上,fs2=cs3=3,不具备标号条件 。 在弧 (vs,v1)上,fs1=1<cs1=5,故给 v1标号 (vs,l(v1)),其中
l(v1)=min[l(vs),(cs1-fs1)]=min[+∞,5-1]=4.
4.网络系统的最大流问题
（ 3） 看 v1:在弧 （ v1,v3） 上,f13=c13=2,
不具备标号条件 。 在弧 (v2,v1)上,f21=1>0,
故给 v2标号 （ -v1,l(v2)）,其中
l(v2)=min[l(v1),f21]=min[4,1]=1.
（ 4 ） 看 v2,在弧 （ v2,v4 ） 上,
f24=3<c24=4,故给 v4标号 （ v2,l(v4)） 其中
l(v4)=min[l(v2),(c24-f24)]=min[1,1]=1.
在弧 （ v3,v2)上,f32 = 1 > 0,故给 v3标号 （ -v2,l(v3)),其中
l (v3)=min[l(v2),f32]=min[1,1]=1。
（ 5） 在 v3,v4中任意选一个,比如 v3,在弧 ( v3,vt )上,f3t = 1 < c3t = 2,
故给 vt 标号 (v3,l(vt)),其中
l(vt)=min[l(v3),(c3t-f3t)]=min[1,1]=1.
因为 vt被标上号,根据标号法,
转入调整过程 。
4.网络系统的最大流问题
2.调整过程从 vt开始,按照标号点的第一个标号,用反向追踪的方法,找出一条从 vs到 vt的增广链 μ，
如 图 8-22中双箭线所示 。 显然,
μ+={(vs,v1),(v3,vt)},μ-={(v2,v1),(v3,v2)}
取 θ=1,在 μ上调整 f,得到
fs1+θ=1+1=2 在 μ+上
f3t+θ=1+1=2 在 μ+上
f*= f21-θ=1-1=0 在 μ-上
f32-θ=1-1=0 在 μ-上其他的不变
4.网络系统的最大流问题
130
调整后的可行流 f*,如图 8.23
所示,再对这个可行流从新进行标号过程,寻找增广链 。
首先给 vs标号 （ 0,+∞）,看
vs,给 v1标号 （ vs,3） 。 看 v1,在弧
（ v1,v3） 上,f13=c13,弧 （ v2,v1）
上,f21=0,均不符合条件 。 因此标号过程无法进行下去,不存在从 vS到 vt的增广链,算法结束 。
4.网络系统的最大流问题
131
4.网络系统的最大流问题这时,网络中的可行流 f*即是最大流,最大流的流量
v ( f * ) = fs1 + fs2 = 5.
同时,也找出 D的最小截集
（ V1,V1）,其中 V1是标号的集合,V1是未标号的集合 。
4.网络系统的最大流问题
V4
V1
V2
V3
Vs
（ 2,2）
（ 3,0）
（ 4,3）
（ 3,3）
（ 5,2）
（ 2,2）
（ 5,3）
（ 1,0） Vt( 0,+∞)
(Vs,3)
图 8-23
(Cij,fij)
（ 1,0）
135
作业：
习题 — 3
136
在实际的网络系统中,当涉及到有关流的问题的时候,我们往往不仅仅考虑的是流量,还经常要考虑费用的问题 。 比如一个铁路系统的运输网络流,即要考虑网络流的货运量最大,
又要考虑总费用最小 。 最小费用最大流问题就是要解决这一类问题 。
5.网络系统的最小费用最大流问题设一个网络 D = (V1,A,C )，
对于每一个弧 (vi,vj)∈ A,给定一个单位流量的费用 bij ≥ 0,网络系统的最小费用最大流问题,是指要寻求一个最大流 f,并且流的总费用
b ( f ) = ∑ bij fij 达到最小 。
（ vi,vj） ∈ A
5.网络系统的最小费用最大流问题在一个网络 D 中,当沿可行流 f 的一条增广链 μ,以调整量 θ =1改进 f,
得到的新可行流 f ’ 的流量,有
v( f ’ ) = v( f ) + 1，
此时总费用 b( f ’ ) 比 b( f ) 增加了
b(f’)-b(f)=∑bij(f’ij-fij)-∑bij(fij-f’ij)= ∑bij-∑bij
μ+ μ- μ+ μ-
将 ∑bij-∑bij叫做这条 增广链的费用 。
5.网络系统的最小费用最大流问题
139
5.网络系统的最小费用最大流问题如果可行流在流量为 v(f)的所有可行流中的费用最小,并且是?关于 f
的所有增广链中的费用最小的增广链 。
那么沿增广链 μ调整可行流 f,得到的新可行流 f’,也是流量为 v(f’)的所有可行流中的最小费用流 。
依次类推,当 f’是最大流时,就是所要求的最小费用最大流 。
显然,零流 f ={0}是流量为 0的最小费用流 。 一般地,寻求最小费用流,从零流 f={0}开始 。 问题是：如果已知 f 是流量为 v ( f ) 的最小费用流,那么就要去寻找关于 f 的最小费用增广链 。
5.网络系统的最小费用最大流问题
141
重新构造一个赋权有向图 M( f )，
其顶点是原网络 D的顶点,而将 D中的每一条弧 (vi,vj)变成两个相反方向的弧
（ vi,vj） 和 (vj,vi),并且定义 M(f )中弧的权 wij为：
0
0
ij
ijij
ji
ijij
ijijij
ij
f,
f,b
w
cf,
cf,b
w
142
并且将权为 +∞的弧从 M(f)中略去 。 即当 0 < fij < cij 时,成为 2条方向相反,权绝对值相等的弧 。 否则不变 。
这样,在网络 D中寻找关于 f
的最小费用增广链就等于价于在
M(f)中寻求从 vs到 vt的最短路 。
5.网络系统的最小费用最大流问题
143
算法开始：取零流 f(0) ={0}.
一般地,如果在第 k-1步得到最小费用流 f(k-1),则构造图 M(f(K-1))。 在图
M(f(K-1))中,寻求从 vs到 vt的最短路：
（ 1） 如果不存在最短路,则 f(K-1)就是最小费用最大流 。
（ 2） 如果存在最短路,则在原网络 D中得到相对应的增广链 μ：
5.网络系统的最小费用最大流问题在 μ上对 f(K-1)进行调整,取调整量
θ=min{min((cij-f(k-1)ij),min(f(k-1)ij)}.
μ+ μ-
令 f(k-1)ij+θ,在 μ+上
f(k)ij = f(k-1)ij -θ,在 μ-上其他的不变 。
得到一个新的可行流 f(k),在对 f(k)重复以上的步骤,直到 D中找不到相对应的增广 链时为止 。
5.网络系统的最小费用最大流问题例略
145
例 8.9,求下图所示网络中的最小费用最大流,弧旁的权是 （ bij,cij）,
5.网络系统的最小费用最大流问题
(bij,Cij)
(1,8)
vt
v3v2
vs
v1
(3,10)
(2,4)
(6,2)
(1,7)
(4,10)
(2,5)
146
解,(1)取初始可行流为零流 f(0)={0}
构造赋权有向图 M(f(0)),求出从 vs到 vt的最短路 (vs,v2,v1,vt),如下图中双箭头所示 。
5.网络系统的最小费用最大流问题
(1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(1)(4)
(2)
M(f(0))
费用图 8-25a)
（ 2） 在原网络 D中,与这条最短路相对应的增广链为 μ=（ vs,v2,v1,vt） ;
（ 3） 在 μ上对 f(0)={0}进行调整,取 θ=5，
得到新可行流 f(1),如图 8.25b所示 。 按照以上的算法,依次类推,可以得到 f(1)，
f(2),f(3),f(4),流量分别为 5,7,10,11，
并且分别构造相对应的赋权有向图 M(f(1)),
M (f (2)),M (f(3)),M (f(4))。 由于在 M(f(4))中已经不存在从 vs到 vt的最短路,因此,可行流 f(4),v(f(1))=11是最小费用最大流 （ 以下的图 ） 。
148
5.网络系统的最小费用最大流问题
(5)
vt
v3v2
vs
v1
(0)
(0)
(0)
(5)
(0)
(5)
图 8-25b f(1),v(f(1))=5
流量
149
5.网络系统的最小费用最大流问题
(1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(1)
(4)
(-2)
M(f(1))图 8-25c
(-1)
(-1)
费用
150
5.网络系统的最小费用最大流问题
(5)
vt
v3v2
vs
v1
(0)
(0)
(7)
(2)
(5)
(0)
图 8-25d f(2),v(f(2))=7
流量
151
5.网络系统的最小费用最大流问题
(1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(-1)
(4)
(-2)(-1)
(-4)
M(f(2))图 8-25e
费用
152
5.网络系统的最小费用最大流问题
(8)
vt
v3v2
vs
v1
(3)
(3)
(0)
(7)
(2)
(5)
图 8-25f f(3),v(f(3))=10
流量
153
5.网络系统的最小费用最大流问题
(-1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(-1)
(4)
(-2)
(-4)
M(f(2))
图 8-25g
(-2)
(-3)
费用
154
5.网络系统的最小费用最大流问题
(8)
vt
v3v2
vs
v1
(4)
(4)
(0)
(7)
(3)
(4)
图 8-25h f(4),v(f(4))=11
流量
155
5.网络系统的最小费用最大流问题
(-1)
vt
v3v2
vs
v1
(3)
(-2)
(6)
(-1)
(4)
(2)
(-4)
M(f(4))图 8-25i
(-2)
(-3)
费用已无最短路，
故达到最优。
156
6.中国邮递员问题中国邮路问题：用图的语言来描述,就是给定一个连通图 G,在每条边上有一个非负的权,要寻求一个圈,经过 G的每条边 至少一次,并且圈的权数最小 。 由于这个问题是我国菅梅谷同志于 1962年首先提出来的,因此国际上常称它为中国邮递员问题 （ 中国邮路问题 ） 。
6.中国邮递员问题一,一笔画问题一笔画问题,也称为遍历问题 。
设有一个连通多重图 G,如果在 G中存在一条链,经过 G的每条边 一次且仅一次,那么这条链叫做 欧拉链 。 如在 G中存在一个简单圈,经过 G的每条边一次,那么这个圈叫做 欧拉圈 。 一个图如果有欧拉圈,那么这个图叫做 欧拉图 。 很明显,一个图 G如果能够一笔画出,那么这个图一定是欧拉图或者含有欧拉链 。
定理 8.10 一个连通多重图 G是欧拉图的充分必要条件是 G中无奇点。
证,必要性,显然 。
充分性,不妨设连通多重图 G至少有三点,对 G的边数 q用数学归纳法 。 因为
G是连通的,并且不含奇点,故 q≥3。
当 q=3时,显然 G是欧拉图 。
假设 q = n 时成立 。 q = n+1的情形：
由于 G是无奇点的连通图,并且 G的点数
p ≥ 3,因此存在三个点 μ,v,w,使得
[μ,v],[w,v]∈ E。
从 G中去掉边 [μ,v],[w,v],增加新的边 [μ,w],得到一个新的多重图 G1,G1有
q-1条边,且仍不含奇点,G1至多有两个分图 。
若 G1是连通的,则由归纳假设,G1
有欧拉圈 C1 。 把 C1 中的边 [w,μ] 换成
[μ,v],[w,v],即是 G中的欧拉圈 。 若 G1有两个分图 G1’,G1’’,令 v在 G1’中 。 由归纳假设,G1’,G1’’分别有欧拉圈 C1’,C1’’，
把 C1”中的边 [μ,w]换成 [μ,v],C1’及 [v,w]即是 G中的欧拉圈 。 证毕
6.中国邮递员问题推论 一个多重连通图 G有欧拉链的充分必要条件是 G有且仅有两个奇点 。
从这个定理的证明可以看出,识别一个连通图能否一笔画出的条件是它是否有奇点 。 若有奇点,就不能一笔画出 。 若没有奇点,就能够一笔画出,并回到原出发地 。
6.中国邮递员问题例如哥尼斯堡七桥问题,欧拉把它抽象成具有四个项点,并且都是奇点的图
8.26的形状 。 很明显,一个漫步者无论如何也不可能重复的走完七座桥,并最终回到原出发地 。
图 8-27。 仅有两个奇点,可以一笔画出 。
图 8-26
BA
D
C
图 8-27
v5
v6v4v2
v1 v3
162
6.中国邮递员问题二,图上作业法从一笔画问题的讨论可知,一个邮递员在他所负责投递的街道范围内,如果街道构成的图中没有奇点,那么他就可以从邮局出发,经过每条街道一次,且仅一次,并最终回到原出发地 。 但是,如果街道构成的图中有奇点,他就必然要在某些街道重复走几次 。
6.中国邮递员问题例如,在图 8-27表示的街道图中,v1表示邮局所在地,每条街道的长度是 1,邮递员可以按照以下的路线行走：
v1-v2-v4-v3-v2-v4-v6-v5-v4-v6-v5-v3-v1,
总长是 12。 也可以按照另一条路线走：
v1-v2-v3-v2-v4-v5-v6-v4-v3-v5-v3-v1,
总长是 11。
按照第 1 条路线走,在边 [v2,v4],
[v4,v6],[v6,v5]上各走两次,按照第 2条路线走,在边 [v3,v2],[v3,v5]上各走了两次 。
164
6.中国邮递员问题在连通图 G中,如果在边 [vi,vj]
上重复走几次,那么就在点 vi,vj之间增加了几条相应的边,每条边的权和原来的权相等,并把新增加的边叫做重复边 。 显然,这条路线构成新图中的欧拉圈 。 如图 8-28a,b
所示 。 并且,邮递员的两条行走路线总路程的差等于新增加重复边总权的差 。
165
6.中国邮递员问题图 8-28
v5
v6v4v2
v1 v3
a）
v5
v6v4v2
v1 v3
b）
166
6.中国邮递员问题中国邮递员问题也可以表示为：
在一个有奇点的连通图中 。
要求增加一些重复边,使得新的连通图不含有奇点,并且增加的重复边总权最小 。
我们把增加重复边后不含奇点的新的连通图叫做邮递路线,
而总权最小的邮递路线叫做 最优邮递路线 。
167
6.中国邮递员问题下面我们来介绍初始邮递路线的确定,改进,以及一个邮递路线是否是最优路线的判定标准的方法 — 图上作业法 。
168
6.中国邮递员问题
（ 一 ） 初始邮递路线的确定方法由于任何一个图中,奇点的个数为偶数,所以如果一个连通图有奇点,就可以把它们两两配成对,
而 每对奇点之间必有一条链 （ 图是连通的 ）,我们把这条链的所有边作为重复边追加到图中去,这样得到的新连通图必无奇点,这就给出了初始投递路线 。
169
6.中国邮递员问题例如,在图 8-29中,v1是邮局所在地,并有四个奇点 v2,v4,v6,v8,
将它们两两配对,比如 v2和 v4为一对,v6和 v8为一对 。
170
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8-29
2
5
5
9 4
4
3
4
6
4
4
3
v9
在连接 v2和 v4的链中任取一条,比如链 （ v2,v1,v8,v7,v6,v5,v4）,再加入重复边
[v2,v1],[v1,v8],[v8,v7],[v7,v6],[v6,v5],[v5,v4].
同样,任 取连 接 v6 和 v8 的一条链
(v8,v1,v2,v3,v4,v5,v6),再加入重复边
[v8,v1],[v1,v2],[v2,v3],[v3,v4],[v4,v5],[v5,v6].
于是,得到图 8.30。 这时没有奇点,故它是欧拉图 。 对于这条邮递路线,重复边的总长为,
2W12+W23+W34+2W45+2W56+W67+W78+2W18=51。
6.中国邮递员问题
172
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8-30
2
5
5
9 4
4
3
4
6
4
4
3
v9
173
（ 二 ） 改进邮递路线,使重复边的总长不断减少 。
从图 8-30 中可以看出,在边
[v1,v2]旁边有两条重复边,但是如果把他们都从图中去掉,所得到的连通图仍然无奇点,还是一个邮递路线,而总长度却有所减少 。 同理,
在边 [v1,v8],[v4,v5],[v5,v6]旁边的重复边也是一样的 。
6.中国邮递员问题
174
6.中国邮递员问题一般地,在邮递路线上,如果在边 [vi,vj]旁边有两条以上的重复边,
从中去掉偶数条,那么可以得到一个总长度较少的邮递路线 。
判定标准 1 在最优邮递路线上,图中的每一条边至多有一条重复边 。
175
按此判定标准,将图 8-30改为图 8-31,这时重复边的总权减少为
21。
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8-31
2
5
5
9 4
4
3
4
6
4
4
3
v9
176
不难看出,如果把图中某个圈上的重复边去掉,而给原来没有重复边的边上加上重复边,
图中仍然没有奇点 。 因此,如果在某个圈上重复边的总权大于这个圈总权的一半,按照以上所说的作一次调整,将会得到一个总权减少的邮递路线 。
6.中国邮递员问题
177
6.中国邮递员问题判定标准 2 在最优邮递路线上,
图中每一个圈的重复边的总权小于或者等于该圈总权的一半 。
如在图 8-31中,圈 （ v2,v3,v4,v9,v2）
的总权为 24,但圈上重复边的总权为
14,大于该圈总权的一半 。
178
因此作一次改进,在该圈上去掉重复边 [v2,v3],[v3,v4],加上重复边
[v2,v9],[v9,v4],如图 8-32所示 。 这时重复边的总权减少为 10。
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8-32
2
5
5
9 4
4
3
4
6
4
4
3
v9
179
6.中国邮递员问题图 8.32 中,圈 (v1,v2,v9,v6,v7,v8,v1)
中重复边总权为 13,而该圈的总权为 24,不满足判定标准 2。 再次经过改进后,得到图 8-33。 此时,该圈中重复边的总权为 11,小于该圈的总权 24。
180
检查图 8-33中的每一个圈,判定标准 1和 2均已满足 。 于是,图中的欧拉圈就是最优邮递路线 。
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8-33
2
5
5
9 4
4
3
4
6
4
4
3V
9
181
上例说明,一个最优邮递路线一定满足判定标准 1和判定标准 2。
反之,不难证明,一个邮递路线如果满足判定标准 1和判定标准 2,那么它一定是最优邮递路线 。
小结,两个判定标准是最优邮递路线判定的充分必要条件 。
6.中国邮递员问题
182
6.中国邮递员问题值得注意的是,这个方法主要困难在于检查判定标准 2。
它要求对于图中的每一个圈都检查一遍 。 当一个连通图所包含的圈数比较多时,将会大大提高运算的工作量,比如,田,
字型的图就有 13个圈 。
183
作业：
习题 — 4
2
第八章 图与网络分析图的基本概念与基本定理树和最小支撑树最短路问题网络系统最大流问题网络系统的最小费用最大流问题中国邮递员问题本章内容重点引 言图论应用非常广泛：
控制论,信息论,工程技术,交通运输,经济管理,电子计算机等领域；
科学研究,市场和社会生活中的许多问题,可以用图论的理论和方法来加以解决 。
例如,通信线路的架设,输油管道的铺设,铁路或者公路交通网络的合理布局 。
4
引 言将复杂的工程系统和管理问题用图的理论加以描述,可以解决许多工程项目和管理决策的优化问题 。
图论越来越受到工程技术人员和经营管理人员的重视 。
5
引 言
1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文,
解决了著名的哥尼斯堡七座桥问题 。
德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,河的两岸和岛屿之间有七座桥相互连接,
如图 8-1a所示 。
引 言
A B
图 8-1 a）
C
D
引 言当地的居民热衷于这样一个问题,一个漫步者如何能够走过这七座桥,并且每座桥只能走过一次,最终回到原出发地 。
尽管试验者很多,但是都没有成功 。
为了寻找答案,1736年欧拉将这个问题抽象成图 8-1b所示图形的一笔画问题 。
即能否从某一点开始不重复地一笔画出这个图形,最终回到原点 。 欧拉在他的论文中证明了这是不可能的,因为这个图形中每一个顶点都与奇数条边相连接,不可能将它一笔画出,这就是古典图论中的第一个著名问题 。
8
引 言图 8-1 b）
A
C
D
B
在实际的生产和生活中,人们为了反映事物之间的关系,常常在纸上用点和线来画出各式各样的示意图 。
例 8.1:图 8-2是我国北京,上海,
重庆等十四个城市之间的铁路交通图,
这里用点表示城市,用点与点之间的线表示城市之间的铁路线 。 诸如此类还有城市中的市政管道图,民用航空线图等等 。
1.图的基本概念与基本定理
10
1.图的基本概念与基本定理太原重庆 武汉 南京徐州 连云港上海郑州石家庄 塘沽青岛济南天津北京图 8-2
11
例 8.2:有六支球队进行足球比赛,我们分别用点 v1… v6表示这六支球队,它们之间的比赛情况,
也可以用图反映出来,已知 v1队战胜 v2队,v2队战胜 v3队,v3队战胜
v5队,如此等等 。 这个胜负情况,
可以用图 8-3所示的有向图反映出来 。
1.图的基本概念与基本定理
12
1.图的基本概念与基本定理
v3
v1
v2 v4
v6
v5
图 8-3
图论中常用 点和点之间的线 所构成的图,反映实际生产和生活中的某些特定对象之间的特定关系 。 一般来说,通常 用点表示研究对象,用点与点之间的线表示研究对象之间的特定关系 。
在一般情况下,图中的相对位臵如何,
点与点之间线的长短曲直,对于反映研究对象之间的关系,显的并不重要 。
因此,图论中的图与几何图,工程图等本质上是不同的 。
1.图的基本概念与基本定理通常把点与点之间不带箭头的线叫做边,带箭头的线叫做 弧 。
如果一个图是由点和边所构成的,那么,称为为 无向图,记作 G =(V,E),其中 V表示图 G的点集合,E表示图 G的边集合 。 连接点 vi,vj?V的边记作 [vi,vj],或者
[vj,vi]。
如果一个图是由点和弧所构成的,
那么称为它为 有向图,记作 D =(V,A),其中 V 表示有向图 D的点集合,A表示有向图
D的弧集合 。 一条方向从 vi指向 vj的弧,记作 (vi,vj)。
例如,图 8-4是一个无向图 G=（ V,E）
其中 V = {v1,v2,v3,v4}
E = { [v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],
[v2,v4],[v3,v3] }
1.图的基本概念与基本定理
v3
v2v1
v4图 8-4
16
图 8-5是一个有向图 D=（ V,A）
其中 V = {v1,v2,v3,v4,v5,v6,v7}
A = {(v1,v2),(v1,v3),(v3,v2),(v3,v4),
(v2,v4),(v4,v5),(v4,v6),(v5,v3),
(v5,v4),(v5,v6),(v6,v7)}
1.图的基本概念与基本定理
v7v5v3
v4v2
v1 v
6
图 8-5
一些常用的名词：无向图 G 或 有向图 D
节点数 记作 P(G)或 P(D),简记作 P,
边数 或者 弧数 记作 q(G)或者 q(D),
简记作 q。
如果边 [vi,vj]?E,那么称 vi,vj是 边的端点,或者 vi,vj是 相邻 的 。
如果一个图 G中,一条边的两个端点是相同的,那么称为这条边是 环 。
1.图的基本概念与基本定理
1.图的基本概念与基本定理
如果两个端点之间有两个端点之间有两条以上的边,那么称为它们为 多重边 。
一个无环,无多重边的图为 简单图 。
一个无环,有多重边的图称为多重图 。
v3
v2v1
v4 图 8-4
环
以点 v为端点的边的个数称为点 v 的度,记作 d(v) 。 如 上 图 中 d(v1)=3,
d(v2)=4,d(v3)=4,d(v4 )=3。
度为零的点称为 弧立点,度为 1的点称为 悬挂点 。 悬挂点的边称为 悬挂边 。
度为奇数的点称为 奇点,度为偶数的点称为 偶点 。
1.图的基本概念与基本定理
20
端点的度 d(v)：点 v 作为边端点的个数；
奇点,d(v)=奇数；
偶点,d(v)=偶数；
悬挂点,d(v)=1；
悬挂边,与悬挂点连接的边；
孤立点,d(v)=0；
空图,E =?，无边图
1.图的基本概念与基本定理定理 8.1 所有顶点次数之和等于所有边数的 2倍。
定理 8.2 在任一图中，奇点的个数必为偶数。
1.图的基本概念与基本定理
22
图的连通性：
链,由两两相邻的点及其相关联的边构成的点边序列 ; 如,
v0,e1,v1,e2,v2,e3,v3,…,v n-1,en,vn ;
v0,vn分别为链的起点和终点；
简单链,链中所含的边均不相同；
初等链,链中所含的点均不相同,
也称通路；
1.图的基本概念与基本定理
23
回路,若 v0 ≠ vn 分称该链为开链，否则称为闭链或回路；
圈,除起点和终点外链中所含的点均不相同的闭链；
连通图,图中任意两点之间均至少有一条通路，否则称作不连通图。
1.图的基本概念与基本定理子图,设 G1=[ V1,E1 ],G2=[ V2,E2 ]
子图定义,如果 V2? V1,E2? E1 称 G2 是
G1 的子图；
真子图,如果 V2? V1,E2? E1 称 G2 是 G1
的真子图；
部分图 （支撑子图）,如果 V2 = V1,
E2? E1 称 G2 是 G1 的部分图；
导出子图,若 V2? V1,E2={[vi,vj]:vi,vj?V2},
称 G2 是 G1 中由 V2 导出 的导出子图。
1.图的基本概念与基本定理有向图：关联边有方向弧,有向图的边 a=(u,v),起点 u,终点 v;
路,若有从 u 到 v 不考虑方向的链,且各方向一致,则称之为从 u到 v的路；
初等路,各顶点都不相同的路；
初等回路,u = v 的初等路 ;
连通图,若不考虑方向是无向连通图 ;
强连通图,任两点有路 ;
1.图的基本概念与基本定理
30
2.树和最小支撑树一,树及其性质在各种各样的图中,有一类图是十分简单又非常具有应用价值的图,这就是 树 。
例 8.3：已知有六个城市,它们之间要架设电话线,要求任意两个城市均可以互相通话,并且电话线的总长度最短 。
2.树和最小支撑树如果用六个点 v1,…,v6代表这六个城市,在任意两个城市之间架设电话线,即在相应的两个点之间连一条边 。
这样,六个城市的一个电话网就作成一个图 。 由于任意两个城市之间均可以通话,这个图必须是连通图 。 并且,这个图必须是无圈的 。 否则,从圈上任意去掉一条边,剩下的图仍然是六个城市的一个电话网 。 图 8-8是一个不含圈的连通图,代表了一个电话线网 。
32
2.树和最小支撑树图 8-8
v6
v3
v4
v2
v5
v1
2.树和最小支撑树定义 8.1 无圈的连通图叫做树 。
性质：
定理 8.3 设图 G=(V,E)是一个树 P(G) ≥2,那么图 G中 至少有两 个悬挂点 。
定理 8.4 图 G=（ V,E） 是一个树的充要条件是 G不含 圈,并且 有且仅有 P-1条边 。
34
2.树和最小支撑树定理 8.5 图 G=（ V,E） 是一个树的充要条件是 G是 连通图,并且 有且仅有 P-1条边 。
定理 8.6 图 G是一个树的充分必要条件是 任意两个顶点之间有且仅有一条链 。
35
2.树和最小支撑树从以上定理,不难得出以下结论：
（ 1） 从一个树中任意去掉一条边,那么剩下的图不是连通图,亦即,在点集合相同的图中,树是含边数最少的连通图 。
（ 2） 在树中不相邻的两个点之间加上一条边,那么恰好得到一个圈 。
2.树和最小支撑树二,支撑树定义 8.2 设图 K=(V,E’)是图 G=(V,E)的一支撑子图,如果图 K=(V,E’)是一个树,
那么称 K是 G的一个支撑树 。
图 8.10b 是图 8-10a 的一个支撑树 。
v6
v5
v2
v3
v4
v1 v
6
v5
v2
v3
v4
v1
图 8-10a） b）
2.树和最小支撑树
显然,如果图 K=( V,E’ )是图 G=(V,E)的一个 支撑树,那么 K 的边数是 p(G)-1；
G中不属于支撑树 K的边构成 K的 余树,
其边数是 q(G)-p(G)+1。
定理 8.7 一个图 G有支撑树的充要条件是 G是连通图。
证明,必要性 显然；
充分性,设图 G是连通的，若 G不含圈，则
G是一个树，从而 G是自身的一个支撑树。
若 G含圈，则任取 G的一个圈，从该圈中任意去掉一条边，得到图 G的一支撑子图 G1。若 G1不含圈，则 G1是 G的一个支撑树。
若 G1仍然含圈，则任取 G1的一个圈，再从圈中任意去掉一条边，得到图 G的一支撑子图 G2。依此类推，可以得到图 G的一个支撑子图 GK，且不含圈，从而 GK是一个支撑树。
41
2.树和最小支撑树以上充分性的证明，提供了一个寻找连通图支撑树的方法叫做,破圈法,。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。
42
2.树和最小支撑树
例 8.4:用破圈法求出下图的一个支撑树。
V5V4
V2
V3
V1
e6e5
e4
e3
e2
e1 e7
e8
43
取一个圈 (v1,v2,v3,v1)，在一个圈中去掉边 e3 。在剩下的图中，再取一个圈（ v1,v2,v4,v3,v1），去掉边 e4。再从圈（ v3,v4 v5,v3）中去掉边 e6。再从圈 (v1,v2,v5,v4,v3,v1 ）中去掉边 e7，这样，剩下的图不含圈，于是得到一个支撑树，如图所示。
v2e
1
e2 e5
e8v1
v3
v4
44
2.树和最小支撑树三、最小支撑树问题定义 8.3 如果图 G =（ V，
E），对于 G中的每一条 [vi,vj]，
相应地有一个数 wij，那么称这样的图 G为 赋权图,wij称为边 [vi,vj]
的权。
这里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的含义。例如长度，费用、流量等等。
2.树和最小支撑树定义 8.4 如果图 T =（ V,E’）
是图 G 的一个支撑树，那么称 E’上所有边的权之和为 支撑树 T 的权,
记作 S(T)。
如果图 G 的支撑树 T* 的权 S(T*)，
在 G 的所有支撑树 T 中的权最小，
即 S(T*) = minS(T)，那么称 T*是 G 的最小支撑树 。
46
2.树和最小支撑树常用的有 破圈法 和 生长法（避圈法） 两个方法：
（ 1） 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；
（ 1） 去掉该圈中权数最大的边；
反复重复 （ 1）（ 2） 两步，直到最短树。
47
2.树和最小支撑树例 8.5 某六个城市之间的道路网如图 8-13a所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。
2.树和最小支撑树
v6
v5
v2
v3
v4
图 8-13a
v1
6
2
7
5
3
5
4
4
v3
v2
v1
v4
v6
v5
5
1
31
4
2
图 8-13b
顺序,浅兰,黄,粉红,白
2.树和最小支撑树解,如图 8-13a，用破圈法求解最小支撑树。
（ 1） 圈 v1,v2,v3,v1,删圈中权最大边 [v1,v3]；
（ 2）圈 v3,v5,v2,v3,去掉边 [v2,v5]；
（ 3）圈 v3,v5,v4,v2,v3,去掉边 [v3,v5]；
（ 4）圈 v5,v6,v4,v5,这里有两条权最大的边
[v5,v6]和 [v4,v6]。任意删一条，如 [v5,v6]。
这时得到一个不含圈的图,即是最小支撑树。
如图 8-13b所示。
50
2.树和最小支撑树从网络图中依次寻找 权数较小的边,寻找过程中，节点不得重复，即 不得构成圈 。注意在找较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最短树或证明网络不存在最短树。
2.树和最小支撑树用,生长法,求解例 8.5
解,考虑赋权图 8-13a，任取一点，如
从 v1 取权较小的边（ v1,v2 ）；
从 v2 取 权较小的边（ v2,v3 ）；
从 v3 取 权较小的边（ v3,v4 ）；
同理依次取（ v4,v5），（ v4,v6 ） 。
这时得到了如图 8-13b所示的最小支撑树。
2.树和最小支撑树
v6
v5
v2
v3
v4
图 8-13a
v1
6
2
7
5
3
5
4
4
v3
v2
v1
v4
v6
v5
5
1
31
4
2
图 8-13b
顺序,黄,粉红,白,绿,浅兰
53
作业：
用破圈法和生长法两种方法求解
习题 — 1
54
3.最短路径问题一,引言最短路径问题是图论中十分重要的最优化问题之一,它作为一个经常被用到的基本工具,可以解决生产实际中的许多问题,
比如城市中的管道铺设,线路安排,工厂布局,设备更新等等 。
也可以用于解决其它的最优化问题 。
55
3.最短路径问题例 8.6,如图 8-14所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从 v1出发，经过这个交通网到达 v8，要寻求是总路程最短的线路。
图 8-14
v1
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
1
56
3.最短路径问题从 v1到 v8的路线是很多的 。
比如从 v1出发,经过 v2,v5到达 v8
或者从 v1出发,经过 v4,v6,v7到达 v8等等 。 但不同的路线,经过的总长度是不同的 。 例如,按照第一个线路,总长度是 6+1+6=13
单位,按照第二个路线,总长度是 1+10+2+4=17单位 。
一般意义下的最短路问题：
设赋权有向图 D =（ V,A）,对每个弧 a =（ vi,vj）,相应地有权 wij。 vs,vt是 D中的两个顶点,P是 D中从 vs到 vt的任意一条路,定义路的权是 P中所有弧权的和,记作 S(p)。
最短路问题就是求 S(P0)=minS(p)。 P0
叫做从 vs到 vs的 最短路 。 P0的权 S(P0)叫做从 vs到 vt的 距离,记作 d（ vs,vt） 。
由于 D是有向图,很明显 d（ vs,vt）
与 d（ vt,vs） 一般不相等 。
58
3.最短路径问题二,Dijkstra（ 狄克斯拉方法 ） 算法下面介绍在一个赋权有向图中寻求最短路的方法 —— Dijkstra算法,
它是在 1959年提出来的 。 目前公认,
在所有的权 wij ≥ 0时,这个算法是寻求最短路问题最好的算法 。 并且,
这个算法实际上也给出了 寻求从一个始定点 vs到任意一个点 vj的最短路 。
Dijkstra算法的基本思想从 vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数，
叫做一个点的 标号,分为两类：
P 标号,表示从 vs到该点的最短路权
T 标号,表示从 vs到该点最短路权的上界。
算法的每一步是去修改 T 标号，把某一个具有 T 标号的点改变为具有 P 标号的点，使图 D 中具有 P 标号的顶点多一个。
这样，至多经过 P -1步，就可求出从 vs到各点 vj的最短路。
说明,在例 8.6中
S=1。 因为 wij≥0,d (v1,v1)=0。 这时,
v1是具有 P标号的点 。
再看从 v1出发的三条弧 (v1,v2),(v1,v3)
和 (v1,v4)。 如果从 v1出发沿 (v1,v2)到达 v2，
这时的路程是 d (v1,v1) + w12= 6单位；
如果从 v1出发,沿 (v1,v3)到达 v3,则是
d (v1,v1) + w13 = 3单位；
同理,如果从 v1出发沿 (v1,v4)到达 v4，
是 d（ v1,v1） + w14 = 1单位 。
说明 （续）
因此,从 v1出发到达 v4的最短路必是 （ v1,v4）,d（ v1,v4） =1。 这是因为从 v1到达 v4的任一条路,假如不是
（ v1,v4）,则必先沿 （ v1,v2） 到达 v2，
或者沿 （ v1,v3） 到达 v3,而这时的路程已是 6或者 3单位 。 由于 wij ≥ 0,因此不论他如何再从 v2或者 v3到达 v4,所经过的总路程都不会比 1少,于是就有
d（ v1,v4） =1。 于是 V4变成具有 P标号的点 。
例 8.6说明：
从 v1出发的三条弧 (v1,v2),(v1,v3)和
(v1,v4)，
min{d(v1,v1)+w12,d(v1,v1)+w13,d(v1,v1)+w14}
= d（ v1,v4） =1。
P(V4)
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
P(V1)
1
再看从 v1和 v4指向其余点的弧：从 V1出发,分别沿 (v1,v2),(v1,v3 )到达 v2,v3,经过的路程是 6或者 3单位；从 v4出发沿 (v4,v6)到达 v6,经过的路程是 d(v1,v4)+w46=1+10=11
单位 。 而
min{d(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46}=
d（ v1,v1） +w13=3单位 。
根据同样的理由,可以断定,从 v1到达 v3的最短路是 （ v1,v3）,d（ v1,v3） =3。
这样,又使点 v3变为具有 P 标号的点,不断重复以上过程,就可以求出从 vs到达任一点 vj的最短路 。
例 8.6说明（续）：
再看从 v1和 v4指向其余点的弧,
min{d(v1,v1)+w12,d(v1,v1)+w13,d(v1,v4)+w46}
=d（ v1,v1） +w13=3 。
P(V4)
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10P(V1) P(V3)
1
3.最短路径问题在下述的 Dijkstra算法中,以 P,T 分别表示某一个点的 P 标号,T 标号 。 Si表示在 第 i步时,具有 P 标号点的集合,为了在算出从 vs到各点的距离的同时,也找出从 vs到各点的最短路,于是,给每一个点 v一个 λ 值 。 当算法结束时,如果
λ(v) = m,则表示在从 vs到 v 的最短路上,
v 的 前一个点是 vm。 如果 λ (v)=M,则表示在图 D 中不含有从 vs 到达 v 的路 。
λ(v) =0,表示 v=vs。
Dijkstra算法的步骤如下：
开始 （ i=0）
令 S0={vs},P（ vs） =0,λ(vs)=0,对每一个 v ≠vs,令 T（ v） =+∞,λ(v)=M,令
k=s；
（ 1） 如果 Si=V,则算法结束,对每一个
v?Si,d（ vs,v） =P（ v） 。 否则转入 （ 2） ；
（ 2） 考察每一个使 (vk,vj)?A,且 vj?Si的点 vj,如果 T(vj)>P(vk)+wkj,则把 T(vj)改变为 P(vk)+wkj,把 λ(vj)改变为 k,否则转入
（ 3） ；
67
3.最短路径问题
（ 3） 令 T(vji)=min{T(vj)?vj?Si}，
如果 T(vji)<+∞，则把 vji的 T 标号改变为 P 标号 P(vji)=T(vji)，令
Si+1=Si∪ {vji},k=ji，把 i换成 i+1，
转入（ 1）；否则结束。
这时，对 v?Si,d(vs,v) = P(v)；
对 v?Si,d(vs,v) =T(v)。
3.最短路径问题用 Dijkstra算法求解例 8.6。 vs为起点,
开始,s =1,i=0; S0={v1},P(v1)=0,λ(v1)=0,
T(vi)=+∞,λ(vi)=M,i=2,3,… 9,k=1。
(2) (v1,v2)∈ A,v2?S0,P(v1)+w12<T(v2)，
故将 T(v2)改变为 P(v1)+w12=6,λ(v2)改变为
1。 同理,将 T(v3)改变为 P(v1)+w13=3,λ(v3)
改变为 1,将 T(v4)改变为 P(v1)+w14=1,λ(v4)
改变为 1。
69
3.最短路径问题
（ 3） 在所有的 T标号中,T(v4)=1最小,
于 是令 P(v4)=1,S1=S0∪ {v4}={v1,v4},
k=4。
i=1：
（ 2） 将 T(v6)改变为 P(v4)+w46=11，
λ(v6) 改变为 4。
（ 3） 在所有的 T标号中,T(v3)=3最小,
于是令 P(v3)=3,S2={v1,v4,v3},k=3。
i=2：
（ 2） (v3,v2)∈ A,v2?S2,T(v2)>w32+P(v3)，
将 T(v2)改变为 P(v3)+w32=5,λ(v2)改变为 3。
（ 3） 在所有的 T标号中,T(v2)=5最小,
于是令 P(v2)=5,S3={v1,v4,v3},k=2。
i=3：
（ 2） 将 T(v5)改变为 P(v2)+w25=6,λ(v5) 改变为 2。
（ 3） 在所有的 T标号中,T(v5)=6最小,
于是令 P(v5)=6,S4={v1,v4,v3},k=5。
3.最短路径问题
（ 2） 将 T(v6),T(v7),T(v8)分别改变为 10,
9,12,将 λ(v0),λ(v7),λ(v8)改变为 5。
（ 3） 在所有的 T标号中,T(v7)=9最小,于是令 P(v7)=9,S5={v1,v4,v3,v2,v5,v7},v=7。
i=5：
（ 2） （ v7,v8） ∈ A,v8?S5,但是
T(v8) < w78+P(v7),故 T(v8)不变 。
（ 3） 在所有的 T标号中,T(v6)=10最小,
于是,令 P(v6)=10,S6={v1,v4,v3,v2,v5,v7,v6}，
k=6。
3.最短路径问题i=6：
（ 2） 从 v6出发没有弧指向不属于 S6的点,
因此转入 （ 3） 。
（ 3） 在所有的 T标号中,T(v8)=12最小,
令 P(v8)=12,S7={v1,v4,v3,v2,v5,v7,v6,v8},
k=8。
i=7：
仅有 T标号的点为 v9,T（ v9） =+∞,算法结束 。
此时,把 P标号和 λ值标在图中,如图
8-15所示例题求解图示（ 1）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
T(V6)= +?
T(V7)= +(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=M
(V5)=M
T(V2)= 6 T(V5)= +?
T(V8)= +?
(V7)=M
(V2)=1
(V8)=M
T(V9)=+?
(V9)=M
T(V3)= 3
(V3)=1
1
i = 0 S1=S0∪ {v4}={v1,v4}
v1 v3
例题求解图示（ 2）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
T(V6)=11
T(V7)=+(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=4
(V5)=M
T(V2)=6 T(V5)=+?
T(V8)=+?
(V7)=M
(V2)=1
(V8)=M
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
i = 1 S2=S1∪ {v3}={v1,v4,v3}
v1 v3
例题求解图示（ 3）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
T(V6)=11
T(V7)=+(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=4
(V5)=M
P(V2)=5 T(V5)=+?
T(V8)=+?
(V7)=M
(V2)=3
(V8)=M
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
i = 2 S3=S2∪ {v2}={v1,v4,v3,v2}
v1 v3
例题求解图示（ 4）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
T(V6)=11
T(V7)=+(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=4
(V5)=2
P(V2)=5 P(V5)=6
T(V8)=+?
(V7)=M
(V2)=3
(V8)=M
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
i = 3 S4=S3∪ {v5}={v1,v4,v3,v2,v5}
v1 v3
例题求解图示（ 5）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
T(V6)=10
P(V7)=9?(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=5
(V5)=2
P(V2)=5 P(V5)=6
T(V8)=12
(V7)=5
(V2)=3
(V8)=5
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
i = 4 S5=S4∪ {v7}={v1,v4,v3,v2,v5,v7}
v1 v3
例题求解图示（ 6）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
P(V6)=10
P(V7)=9?(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=5
(V5)=2
P(V2)=5 P(V5)=6
T(V8)=12
(V7)=5
(V2)=3
(V8)=5
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
i = 5 S6=S5∪ {v6}={v1,v4,v3,v2,v5,v7,v6}
v1 v3
例题求解图示（ 7）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
P(V6)=10
P(V7)=9?(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=5
(V5)=2
P(V2)=5 P(V5)=6
P(V8)=12
(V7)=5
(V2)=3
(V8)=5
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
i = 6 S7 =S6∪ {v8}={v1,v4,v3,v2,v5,v7,v6,v8}
v1 v3
例题求解图示（ 8）
v4
v2
v8
v7
v6
v5
v96
3 6
2
3
4
10 2
3
1
2
6
2
4 10
图 8-15
P(V6)=10
P(V7)=9?(V1)=0
P(V1)=0
P(V4)=1
(V4)=1?(V6)=5
(V5)=2
P(V2)=5 P(V5)=6
P(V8)=12
(V7)=5
(V2)=3
(V8)=5
T(V9)=+?
(V9)=M
P(V3)=3
(V3)=1
1
最短路,V1-(V4)V3-V2-V5-(V6,V7)V8
v1 v3
81
3.最短路径问题图 8-15中,从 v1到 v8的最短路：因为 λ(v8)=5,故最短路经过点 v5；又因为 λ(v5)=2,故最短路经过点 v2；依次类推,λ(v2)=3,λ(v3)=1于是,最短路经过点 v3,v1。 这样,从 v1到 v8的最短路是 （ v1,v3,v2,v5,v8） 。 同理,
可以求出从 v1到任一点 vi的最短路,
显然不存在从 v1到 v9的最短路 。
3.最短路径问题对于一个赋权 (无向 )图 G=(V,E)，
因为边 [vi,vj]可以看作 2条弧 （ vi,vj） 和
(vj,vi),并且具有相同的权 wij。 这样,在一个赋权 （ 无向 ） 图中,如果有所有的权 wij≥0,只要将 Dijkstra算法中的
,(2)看作每一个使 (vk,vj)?A,且 vj?Sj的点 vj”改变为,(2)看作每一个使 [vk,vj]?E，
且 vj?Sj的点 vj”而其他的条件不变,同样可以求出从 vs到各点的最短路 （ 对于无向图叫做最短链 ） 。
83
3.最短路径问题
习题,
将例 8-6中所示的赋权有向图的箭头去掉,然后求出无向图中从 vs到各点的最短路 。
84
作业：
P220— 2
略去证明证明 Dijkstra算法 。
只须证明?v∈ Si,P(v)是从 vs到 v
的最短路权,即 P(v)=d(vs.v)。
证,用数学归纳法 。 当 i=0时,结论显然成立 。 假设 i=n时,结论成立 。
看 i=n+1的情形,由于 Sn+1=Sn∪ {vjn},
所以只要证明 P(vjn)=d(vs,vj)。
根据算法,vjm是具有最小 T标号的点,即 Tn(vjn)=min{Tn(vj)},其中 vj?Sm.这里,用 Tn(ν)表示当 i=n时,执行步骤 （ 3）
时点 ν的 T标号 。 设 H是图 D中任意一条从
vs到 vjn的路 。
因为 vs∈ Sn,而 vjn?Sn,所以从 vs出发，
沿 H 必存在一条弧，其始点属于 Sn，而终点不属于 Sn。令（ vr,vl）是第一条这样的弧，于是 H =(vs…v r,vl…v jn),
s(H )=S((vs,vr))+wrl+S((vl…v jn))。
3.最短路径问题
由归纳假设,P(vr)是从 vs到 vr的最短路权,
于是,有 S(H)≥P(vr) + wrl+S((vl… vjn))。 根据算法中的 T标号修改规则,因为
vr∈ Sn,vl?Sn,故 P(vr) + wrl ≥Tn(vl),而
Tn(vl) ≥Tn(vjn),且 S((vl… vjn))≥0,所以 S(H)
≥ Tn(vjn)+S((vl,… vjn)) ≥ Tn(vjn)。
这样,就证明了 Tn(vjn)是从 vs到 vjn的最短权 。 根据算法,P(vjn)=Tn(vjn),于是就有
P(vjn)=d(vs,vjn)。
Dijkstra算法仅适合于所有的权 wij≥0的情形 。 如果当赋权有向图中存在有负权弧时,则该算法失效 。
例如图 8-16中,根据 Dijkstra算法,
可以得出从 v1到 v2最短路权是 2,但是这显然不对,因为从 v1 到 v2 的最短路是
（ v1,v3,v2）,权是 -1。
v1
v3
v22
2 -3
图 8-16
3.最短路径问题
Ford(福德 )算法,当赋权有向图存在负权弧时,求最短路的方法,
首先,设从任一点 vi 到任一点 vj 都有一条弧,如果在图 D 中,
（ vi,vj） 不属于 A,则添加弧 (vi,vj),
并且令 wij = +∞.
从 vs 到 vj 的最短路是从 vs 点出发,沿着这条路到某个点 vi,再沿弧 (vi,vj)到点 vj。
显然,从 vs到 vi的这条路必定是从 vs到 vi的最短路 。 否则从 vs到 vj
的这条路将不是最短路 。 于是,从
vs到 vj的距离 d(vs,vj)满足以下条件
d(vs,vj)=min{ d (vs,vi) + wij },
i
i=1,…,p,p = p(D)
3.最短路径问题
这个关系式的解 d(vs,v1)… d(vs,vp).可利用如下的 递推公式 求解
d(1)(vs,vj) = wsj,j =1,…,p,
d(t)(vs,vj) = min {d(t-1)(vs,vi)+ wij},t=2,3…i
当计算到第 k步时,对一切的 j =1,…,p,有
d(k)(vs,vj) = d(k-1)(vs,vj )
则 d(k)(vs,vj),j = 1,…,p,就是从 vs到各点 vj
的最短路径的权 。
92
设 C是赋权函数有向图 D中的一个回路 。 如果回路 C的权 S（ C） 是负数那么称 C是 D中的一个负回路 。
可以证明以下的结论：
（ 1） 如果赋权有向图 D不含有负回路,那么从 vs到任一点的最短路至多包含 P-2个中间点,并且必可取为初等路 。
此方法有如下结论
93
（ 2） 如果赋权有向图 D不含有负回路,那么上述递推算法至多经过 P-
1次迭代必收敛,可以求出从 vs到各个点的最短路权 。
（ 3） 如果上述算法经过 P-1次迭代,还存在在着某个 j,使得
d(p)(vs,vj)? d(p-1)(vs,vj),
那么 D中含有负回路 。 这时,不存在从 vs 到 vj 的路 （ 权无界 ） 。
94
3.最短路径问题例 8.7,在如图 8-17所示的赋权有向图中求从 v1到各点的最短路 。
解,利用上述递推公式,将求解结果列出如表 8-18所示 。
可以看出,当 t =4 时,有
d(t)(vs,vj)=d(t-1)(vs,vj) j =1,…,8
因此,表中的最后一列,就是从 v1到
v1,v2,…,v8的最短路权 。
95
3.最短路径问题
v8
v2
v4 v7
v5
v1 v3 v6
图 8-17
1
1
1
－ 1
－ 1
－ 1
－ 2
－ 3－ 3
－ 5
－ 52
2
3
6
7
8
终点起点
V1 V2 V3 V4 V5 V6 V7 V8 t=1 t=2 t=3 t=4
V1 0 -1 -2 3 0 0 0 0
V2 6 0 2 -1 -5 -5 -5
V3? -3 0 -5? 1 -2 -2 -2 -2
V4 8 0 2? 3 -7 -7 -7
V5? -1 0 1 -3 -3
V6 1 0 1 7? -1 -1 -1
V7 -1 0 5 -5 -5
V8 -3? -5 0 6 6
wij d(t)(vs,vj)
3.最短路径问题为了求出从 v1到各个点的最短路,
一般采用反向追踪的方法：如果已知
d(vs,vj),那 么 寻 求 一 个 点 vk,使得
d(vs,vk)+wkj=d(vs,vj),然后记录下 (vk,vj).在看 d(vs,vk),寻求一个点 vi,使得
d(vs,vi)+wik=d(vs,vk)… 依次类推,一直到达 vs为止 。 这样,从 vs到 vj的最短路是
（ vs,…,vi,vk,vj）,
98
在例中,由上表知,d(v1,v8)=6,
由于 d(v1,v6)+w68 = (-1) + 7 记录下 v6 ;
由于 d (v1,v3) + w36= d (v1,v6),j记录下 v3; 由于 d(v1,v1)+w13=d(v1,v3),
于是,从 v1到 v8的最短路是
(v1,v3,v6,v8)
99
作业：
用 Ford(福德 )算法求解
习题 --2
4,网络系统的最大流问题一 引言在许多实际的网络系统中都存在着流量和最大流问题 。 例如铁路运输系统中的车辆流,城市给排水系统的水流问题等等 。 而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题,它对于解决生产实际问题起着十分重要的作用 。
4,网络系统的最大流问题图 8-18
vt
v3
v2
v1
v4
vs
17
3
5
10
8
6
11
4
5
3
Cij
图 8-18是一个网络。弧旁边的权就是对应的容量（最大通过能力） 。 要求指定一个运输方案，
使得从 vs到 vt的货运量最大，这是寻求网络系统的最大流问题。
102
4.网络系统的最大流问题二,基本概念定义 8.5 设赋权有向图 D=(V,A),在
V中指定一个 发点 vs和一个 收点 vt,其他的点叫做中间点 。 对于 D中的每一个弧 (vi,vj)∈ A,都有一个权 cij 叫做 弧的容量 。 我们把这样的图 D 叫做一个网络系统,简称网络,记做 D =（ V，
A,C） 。
103
网络 D上的流指定义在弧集合 A上的一个函数 f = { f(vi,vj) } = { fij };
f(vi,vj)=fij叫做 弧在 (vi,vj)上的流量 。
105
4.网络系统的最大流问题网络系统上流的特点：
(1)发点的总流出量和收点的总流入量必相等；
(2)每一个中间点的流入量与流出量的代数和等于零；
(3)每一个弧上的流量不能超过它的最大通过能力 （ 即容量 ） 。
4.网络系统的最大流问题定义 8.6 网络上的一个流 f 叫做 可行流,
如果 f 满足以下条件：
（ 1 ） 容量条件,对于每一个弧
(vi,vj)∈ A,有 0? fij?cij ；
（ 2） 平衡条件,
对于发点 vs,有 ∑fsj -∑fjs= v( f )
对于收点 vt,有 ∑ftj -∑fjt =-v( f )
对于中间点,有 ∑fij -∑fji=0
其中发点的总流量 （ 或收点的总流量 ）
v( f )叫做这个 可行流的流量 。
107
4.网络系统的最大流问题
任意一个网络上的 可行流总是存在 的 。 例如零流 v ( f ) = 0,
就是满足以上条件的可行流 。
网络系统中 最大流问题 就是在给定的网络上寻求一个可行流
f,其流量 v ( f ) 达到最大值 。
108
饱和弧与零流弧
设流 f = { fij } 是网络 D上的一个可行流。我们把 D 中 fij = cij 的弧叫做 饱和弧,fij < cij 的弧叫做非饱和弧 ； fij > 0 的弧为 非零流弧,fij = 0 的弧叫做 零流弧 。
4.网络系统的最大流问题
设 μ是网络 D中连接发点 νs和收点 vt的一条链 。 定义链的方向是从 vs到 vt,于是链 μ上的弧被分为两类：一是弧的方向与链的方向相同,叫做 前向弧,前向弧的集合记做 μ+。 二是弧的方向与链的方向相反,叫做 后向弧,后向弧的集合记做 μ-。
在下图 （ 8-18与 8-19合并图） 中,(v4,v3)是饱和弧，其它弧均是非饱和弧、非零流弧。
如图在链（ vs,v1,v2,v3,v4,vt)中 μ={(v4,v3)}；
μ+={(vs,v1),(v1,v2),(v2,v3),(v4,vt)}。
v3
v2
v1
v4
vs
（ 17,2）
（ 3,3）
（ 5,2）
（ 10,5）
（ 8,3）
（ 6,3）
（ 11,6）
（ 4,1）
（ 5,1）
（ 3,2）
fij
vt
4.网络系统的最大流问题定义：如果链 μ满足以下条件：
1,在弧 (vi,vj)∈ μ+上,有 0 ≤ fij <
cij,即 μ+中的每一条弧是非饱和弧 。
2,在弧 (vi,vj)∈ μ-上,有 0< fij ≤
cij,即 μ-中的每一条弧是非零流弧 。
称链 μ为关于可行流 f 的一条 增广链 。
112
例如在上图中，
链 μ=（ vs,v1,v2,v3,v4,vt）就是一条增广链。
设图 D=(V,A,C ),点集 S,
T?V,S∩T=ф中 。 将起点在 S,终点在 T 的所有弧作成集合,记做
（ S,T） 。
113
4.网络系统的最大流问题定义 8.8 设一个网络 D=(V,A,C)。
如果点集 V被剖分为两个非空集合 V1
和 V1,发点 vs∈ V1,收点 vt∈ V1,那么将弧集 （ V1,V1） 叫做是 分离 vs和 vt的截集 。
定义 8.9 设一个截集 （ V1,V1）,将截集 （ V1,V1） 中所有的弧的容量的和叫做 截集的截量,记做 s(V1,V1),亦即 s(V1,V1) = ∑ cij。
(vi,vj)∈ (V1,V1)
114
4.网络系统的最大流问题显然：一个网络 D中,任何一个可行流 f 的流量 v( f )都小于或等于这个网络中任何一个截集 (V1,V1)的截量 。 并且,如果网络上的一个可行流 f *和网络中的一个截集 （ V1*,V1*）,
满足条件 v*(f * ) = c (V1*,V1* ),那么 f *
一定是 D上的最大流,而 （ V1*,V1*）
一定是 D的所有的截集中截量最小的一个 （ 即最小截集 ） 。
115
4.网络系统的最大流问题定理 8.8 网络中的一个可行流 f * 是最大流的充分必要条件是，不存在关于 f * 的增广链。
定理 8.9 在一个网络 D 中，
最大流的流量等于分离 vs和 vt的最小截集的截量。
说明：
若网络存在关于可行流 f 的增广链
令按增广链的定义，这里?> 0 。 取
ijijij
fm i n),fc(m i nm i n
。且是可行流，显然，
否则上在上在
)fv()f
~
v(f
~
,f
,f
,f
f
~
ij
ij
ij
ij
-
117
定理 8.8实际上提供了一个寻求网络系统最大流的方法：
如果网络 D 中有一个可行流 f，
只要判断网络是否存在关于可行流 f的增广链 。如果没有增广链，
那么 f一定是最大流。如有增广链，
那么可以按照前面说明，不断改进和增大可行流 f的流量，最终可以得到网络中的一个最大流。
三、标号法用给顶点标号的方法来定义 V1*。
在标号过程中,有标号的顶点是 V1*中的点,没有标号的点不是 V1*中的点 。
如果 vt 有了标号,则表示存在一条关于 f 的增广链 。 如果标号过程无法进行下去,并且 vt 未被标号,则表示不存在关于 f 增广链 。 这样,就得到了网络中的一个最大流和最小截集 。
4.网络系统的最大流问题
1,标号过程在标号过程中,网络中的点或者是 标号点 （ 分为已检查和未检查两种 ） 。 或者是 未标号点 。 每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的 。
以便找出增广链 。 第二个标号是为了用来确定增广链上的调整量 θ。
4.网络系统的最大流问题标号过程开始,先给 vs标号 (0,+∞)。
这时,vs是 标号未检查的点,其他都是未标号点 。 一般地,取一个标号未检查点 vi,对一切未标号点 vj：
1） 如果在弧 (vi,vj)上,fij < cij,那么给
vj标号 (vi,l(vj) ),其中 l(vj) = min[l(vi),cij-
fij]。 这时,vj 成为 标号未检查的点 。
4.网络系统的最大流问题
2） 如果在弧 (vj,vi)上,fij > 0,那么给
vj标号 (-vi,l(vj) ),其中 l(vj) = min [l(vi),
fij]。 这时,vj成为 标号未检查点 。
于是 vi成为标号已检查的点 。 重复以上步骤,如果所有的标号都已经检查过,
而标号过程无法进行下去,则标号法结束 。 这时的可行流就是最大流 。 但是,
如果 vt被标上号,表示得到一条增广链 μ，
转入下一步调整过程 。
122
2.调整过程首先按照 vt和其他的点的第一个标号,反向追踪,找出增广链 μ。 例如,
令 vt的第一个标号是 vk,则弧 （ vk,vt）
在 μ上 。 再看 vk的第一个标号,若是 vi，
则弧 (vi,vk)都在 μ上 。 依次类推,直到
vs为止 。 这时,所找出的弧就成为网络 D的一条增广链 μ。 取调整量 θ= l(vt),
即 vt的第二个标号,
4.网络系统的最大流问题
123
fij+θ,当 (vi,vj)∈ μ+
令 f ’ij= fij -θ,当 (vi,vj)∈ μ-
其他不变再去掉所有的标号,对新的可行流
f ’ = { f ’ij },重新进行标号过程,直到找到网络 D的最大流为止 。
4.网络系统的最大流问题
124
4.网络系统的最大流问题
V4
V1
V2
V3
Vs
（ 2,1）
（ 3,0）
（ 4,3）
（ 3,3）
（ 5,1）
（ 2,2）
（ 5,3）
（ 1,1）
（ 1,1）
(Cij,fij)
Vt
图 8-21
例 8.8,求图 8-21的网络最大流,弧旁的权数表示 （ cij,fij） 。 用标号法解解,1.标号过程 。
（ 1） 首先给 vs标号 （ 0,+∞）
（ 2） 看 vs,在弧 (vs,v2)上,fs2=cs3=3,不具备标号条件 。 在弧 (vs,v1)上,fs1=1<cs1=5,故给 v1标号 (vs,l(v1)),其中
l(v1)=min[l(vs),(cs1-fs1)]=min[+∞,5-1]=4.
4.网络系统的最大流问题
（ 3） 看 v1:在弧 （ v1,v3） 上,f13=c13=2,
不具备标号条件 。 在弧 (v2,v1)上,f21=1>0,
故给 v2标号 （ -v1,l(v2)）,其中
l(v2)=min[l(v1),f21]=min[4,1]=1.
（ 4 ） 看 v2,在弧 （ v2,v4 ） 上,
f24=3<c24=4,故给 v4标号 （ v2,l(v4)） 其中
l(v4)=min[l(v2),(c24-f24)]=min[1,1]=1.
在弧 （ v3,v2)上,f32 = 1 > 0,故给 v3标号 （ -v2,l(v3)),其中
l (v3)=min[l(v2),f32]=min[1,1]=1。
（ 5） 在 v3,v4中任意选一个,比如 v3,在弧 ( v3,vt )上,f3t = 1 < c3t = 2,
故给 vt 标号 (v3,l(vt)),其中
l(vt)=min[l(v3),(c3t-f3t)]=min[1,1]=1.
因为 vt被标上号,根据标号法,
转入调整过程 。
4.网络系统的最大流问题
2.调整过程从 vt开始,按照标号点的第一个标号,用反向追踪的方法,找出一条从 vs到 vt的增广链 μ，
如 图 8-22中双箭线所示 。 显然,
μ+={(vs,v1),(v3,vt)},μ-={(v2,v1),(v3,v2)}
取 θ=1,在 μ上调整 f,得到
fs1+θ=1+1=2 在 μ+上
f3t+θ=1+1=2 在 μ+上
f*= f21-θ=1-1=0 在 μ-上
f32-θ=1-1=0 在 μ-上其他的不变
4.网络系统的最大流问题
130
调整后的可行流 f*,如图 8.23
所示,再对这个可行流从新进行标号过程,寻找增广链 。
首先给 vs标号 （ 0,+∞）,看
vs,给 v1标号 （ vs,3） 。 看 v1,在弧
（ v1,v3） 上,f13=c13,弧 （ v2,v1）
上,f21=0,均不符合条件 。 因此标号过程无法进行下去,不存在从 vS到 vt的增广链,算法结束 。
4.网络系统的最大流问题
131
4.网络系统的最大流问题这时,网络中的可行流 f*即是最大流,最大流的流量
v ( f * ) = fs1 + fs2 = 5.
同时,也找出 D的最小截集
（ V1,V1）,其中 V1是标号的集合,V1是未标号的集合 。
4.网络系统的最大流问题
V4
V1
V2
V3
Vs
（ 2,2）
（ 3,0）
（ 4,3）
（ 3,3）
（ 5,2）
（ 2,2）
（ 5,3）
（ 1,0） Vt( 0,+∞)
(Vs,3)
图 8-23
(Cij,fij)
（ 1,0）
135
作业：
习题 — 3
136
在实际的网络系统中,当涉及到有关流的问题的时候,我们往往不仅仅考虑的是流量,还经常要考虑费用的问题 。 比如一个铁路系统的运输网络流,即要考虑网络流的货运量最大,
又要考虑总费用最小 。 最小费用最大流问题就是要解决这一类问题 。
5.网络系统的最小费用最大流问题设一个网络 D = (V1,A,C )，
对于每一个弧 (vi,vj)∈ A,给定一个单位流量的费用 bij ≥ 0,网络系统的最小费用最大流问题,是指要寻求一个最大流 f,并且流的总费用
b ( f ) = ∑ bij fij 达到最小 。
（ vi,vj） ∈ A
5.网络系统的最小费用最大流问题在一个网络 D 中,当沿可行流 f 的一条增广链 μ,以调整量 θ =1改进 f,
得到的新可行流 f ’ 的流量,有
v( f ’ ) = v( f ) + 1，
此时总费用 b( f ’ ) 比 b( f ) 增加了
b(f’)-b(f)=∑bij(f’ij-fij)-∑bij(fij-f’ij)= ∑bij-∑bij
μ+ μ- μ+ μ-
将 ∑bij-∑bij叫做这条 增广链的费用 。
5.网络系统的最小费用最大流问题
139
5.网络系统的最小费用最大流问题如果可行流在流量为 v(f)的所有可行流中的费用最小,并且是?关于 f
的所有增广链中的费用最小的增广链 。
那么沿增广链 μ调整可行流 f,得到的新可行流 f’,也是流量为 v(f’)的所有可行流中的最小费用流 。
依次类推,当 f’是最大流时,就是所要求的最小费用最大流 。
显然,零流 f ={0}是流量为 0的最小费用流 。 一般地,寻求最小费用流,从零流 f={0}开始 。 问题是：如果已知 f 是流量为 v ( f ) 的最小费用流,那么就要去寻找关于 f 的最小费用增广链 。
5.网络系统的最小费用最大流问题
141
重新构造一个赋权有向图 M( f )，
其顶点是原网络 D的顶点,而将 D中的每一条弧 (vi,vj)变成两个相反方向的弧
（ vi,vj） 和 (vj,vi),并且定义 M(f )中弧的权 wij为：
0
0
ij
ijij
ji
ijij
ijijij
ij
f,
f,b
w
cf,
cf,b
w
142
并且将权为 +∞的弧从 M(f)中略去 。 即当 0 < fij < cij 时,成为 2条方向相反,权绝对值相等的弧 。 否则不变 。
这样,在网络 D中寻找关于 f
的最小费用增广链就等于价于在
M(f)中寻求从 vs到 vt的最短路 。
5.网络系统的最小费用最大流问题
143
算法开始：取零流 f(0) ={0}.
一般地,如果在第 k-1步得到最小费用流 f(k-1),则构造图 M(f(K-1))。 在图
M(f(K-1))中,寻求从 vs到 vt的最短路：
（ 1） 如果不存在最短路,则 f(K-1)就是最小费用最大流 。
（ 2） 如果存在最短路,则在原网络 D中得到相对应的增广链 μ：
5.网络系统的最小费用最大流问题在 μ上对 f(K-1)进行调整,取调整量
θ=min{min((cij-f(k-1)ij),min(f(k-1)ij)}.
μ+ μ-
令 f(k-1)ij+θ,在 μ+上
f(k)ij = f(k-1)ij -θ,在 μ-上其他的不变 。
得到一个新的可行流 f(k),在对 f(k)重复以上的步骤,直到 D中找不到相对应的增广 链时为止 。
5.网络系统的最小费用最大流问题例略
145
例 8.9,求下图所示网络中的最小费用最大流,弧旁的权是 （ bij,cij）,
5.网络系统的最小费用最大流问题
(bij,Cij)
(1,8)
vt
v3v2
vs
v1
(3,10)
(2,4)
(6,2)
(1,7)
(4,10)
(2,5)
146
解,(1)取初始可行流为零流 f(0)={0}
构造赋权有向图 M(f(0)),求出从 vs到 vt的最短路 (vs,v2,v1,vt),如下图中双箭头所示 。
5.网络系统的最小费用最大流问题
(1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(1)(4)
(2)
M(f(0))
费用图 8-25a)
（ 2） 在原网络 D中,与这条最短路相对应的增广链为 μ=（ vs,v2,v1,vt） ;
（ 3） 在 μ上对 f(0)={0}进行调整,取 θ=5，
得到新可行流 f(1),如图 8.25b所示 。 按照以上的算法,依次类推,可以得到 f(1)，
f(2),f(3),f(4),流量分别为 5,7,10,11，
并且分别构造相对应的赋权有向图 M(f(1)),
M (f (2)),M (f(3)),M (f(4))。 由于在 M(f(4))中已经不存在从 vs到 vt的最短路,因此,可行流 f(4),v(f(1))=11是最小费用最大流 （ 以下的图 ） 。
148
5.网络系统的最小费用最大流问题
(5)
vt
v3v2
vs
v1
(0)
(0)
(0)
(5)
(0)
(5)
图 8-25b f(1),v(f(1))=5
流量
149
5.网络系统的最小费用最大流问题
(1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(1)
(4)
(-2)
M(f(1))图 8-25c
(-1)
(-1)
费用
150
5.网络系统的最小费用最大流问题
(5)
vt
v3v2
vs
v1
(0)
(0)
(7)
(2)
(5)
(0)
图 8-25d f(2),v(f(2))=7
流量
151
5.网络系统的最小费用最大流问题
(1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(-1)
(4)
(-2)(-1)
(-4)
M(f(2))图 8-25e
费用
152
5.网络系统的最小费用最大流问题
(8)
vt
v3v2
vs
v1
(3)
(3)
(0)
(7)
(2)
(5)
图 8-25f f(3),v(f(3))=10
流量
153
5.网络系统的最小费用最大流问题
(-1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(-1)
(4)
(-2)
(-4)
M(f(2))
图 8-25g
(-2)
(-3)
费用
154
5.网络系统的最小费用最大流问题
(8)
vt
v3v2
vs
v1
(4)
(4)
(0)
(7)
(3)
(4)
图 8-25h f(4),v(f(4))=11
流量
155
5.网络系统的最小费用最大流问题
(-1)
vt
v3v2
vs
v1
(3)
(-2)
(6)
(-1)
(4)
(2)
(-4)
M(f(4))图 8-25i
(-2)
(-3)
费用已无最短路，
故达到最优。
156
6.中国邮递员问题中国邮路问题：用图的语言来描述,就是给定一个连通图 G,在每条边上有一个非负的权,要寻求一个圈,经过 G的每条边 至少一次,并且圈的权数最小 。 由于这个问题是我国菅梅谷同志于 1962年首先提出来的,因此国际上常称它为中国邮递员问题 （ 中国邮路问题 ） 。
6.中国邮递员问题一,一笔画问题一笔画问题,也称为遍历问题 。
设有一个连通多重图 G,如果在 G中存在一条链,经过 G的每条边 一次且仅一次,那么这条链叫做 欧拉链 。 如在 G中存在一个简单圈,经过 G的每条边一次,那么这个圈叫做 欧拉圈 。 一个图如果有欧拉圈,那么这个图叫做 欧拉图 。 很明显,一个图 G如果能够一笔画出,那么这个图一定是欧拉图或者含有欧拉链 。
定理 8.10 一个连通多重图 G是欧拉图的充分必要条件是 G中无奇点。
证,必要性,显然 。
充分性,不妨设连通多重图 G至少有三点,对 G的边数 q用数学归纳法 。 因为
G是连通的,并且不含奇点,故 q≥3。
当 q=3时,显然 G是欧拉图 。
假设 q = n 时成立 。 q = n+1的情形：
由于 G是无奇点的连通图,并且 G的点数
p ≥ 3,因此存在三个点 μ,v,w,使得
[μ,v],[w,v]∈ E。
从 G中去掉边 [μ,v],[w,v],增加新的边 [μ,w],得到一个新的多重图 G1,G1有
q-1条边,且仍不含奇点,G1至多有两个分图 。
若 G1是连通的,则由归纳假设,G1
有欧拉圈 C1 。 把 C1 中的边 [w,μ] 换成
[μ,v],[w,v],即是 G中的欧拉圈 。 若 G1有两个分图 G1’,G1’’,令 v在 G1’中 。 由归纳假设,G1’,G1’’分别有欧拉圈 C1’,C1’’，
把 C1”中的边 [μ,w]换成 [μ,v],C1’及 [v,w]即是 G中的欧拉圈 。 证毕
6.中国邮递员问题推论 一个多重连通图 G有欧拉链的充分必要条件是 G有且仅有两个奇点 。
从这个定理的证明可以看出,识别一个连通图能否一笔画出的条件是它是否有奇点 。 若有奇点,就不能一笔画出 。 若没有奇点,就能够一笔画出,并回到原出发地 。
6.中国邮递员问题例如哥尼斯堡七桥问题,欧拉把它抽象成具有四个项点,并且都是奇点的图
8.26的形状 。 很明显,一个漫步者无论如何也不可能重复的走完七座桥,并最终回到原出发地 。
图 8-27。 仅有两个奇点,可以一笔画出 。
图 8-26
BA
D
C
图 8-27
v5
v6v4v2
v1 v3
162
6.中国邮递员问题二,图上作业法从一笔画问题的讨论可知,一个邮递员在他所负责投递的街道范围内,如果街道构成的图中没有奇点,那么他就可以从邮局出发,经过每条街道一次,且仅一次,并最终回到原出发地 。 但是,如果街道构成的图中有奇点,他就必然要在某些街道重复走几次 。
6.中国邮递员问题例如,在图 8-27表示的街道图中,v1表示邮局所在地,每条街道的长度是 1,邮递员可以按照以下的路线行走：
v1-v2-v4-v3-v2-v4-v6-v5-v4-v6-v5-v3-v1,
总长是 12。 也可以按照另一条路线走：
v1-v2-v3-v2-v4-v5-v6-v4-v3-v5-v3-v1,
总长是 11。
按照第 1 条路线走,在边 [v2,v4],
[v4,v6],[v6,v5]上各走两次,按照第 2条路线走,在边 [v3,v2],[v3,v5]上各走了两次 。
164
6.中国邮递员问题在连通图 G中,如果在边 [vi,vj]
上重复走几次,那么就在点 vi,vj之间增加了几条相应的边,每条边的权和原来的权相等,并把新增加的边叫做重复边 。 显然,这条路线构成新图中的欧拉圈 。 如图 8-28a,b
所示 。 并且,邮递员的两条行走路线总路程的差等于新增加重复边总权的差 。
165
6.中国邮递员问题图 8-28
v5
v6v4v2
v1 v3
a）
v5
v6v4v2
v1 v3
b）
166
6.中国邮递员问题中国邮递员问题也可以表示为：
在一个有奇点的连通图中 。
要求增加一些重复边,使得新的连通图不含有奇点,并且增加的重复边总权最小 。
我们把增加重复边后不含奇点的新的连通图叫做邮递路线,
而总权最小的邮递路线叫做 最优邮递路线 。
167
6.中国邮递员问题下面我们来介绍初始邮递路线的确定,改进,以及一个邮递路线是否是最优路线的判定标准的方法 — 图上作业法 。
168
6.中国邮递员问题
（ 一 ） 初始邮递路线的确定方法由于任何一个图中,奇点的个数为偶数,所以如果一个连通图有奇点,就可以把它们两两配成对,
而 每对奇点之间必有一条链 （ 图是连通的 ）,我们把这条链的所有边作为重复边追加到图中去,这样得到的新连通图必无奇点,这就给出了初始投递路线 。
169
6.中国邮递员问题例如,在图 8-29中,v1是邮局所在地,并有四个奇点 v2,v4,v6,v8,
将它们两两配对,比如 v2和 v4为一对,v6和 v8为一对 。
170
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8-29
2
5
5
9 4
4
3
4
6
4
4
3
v9
在连接 v2和 v4的链中任取一条,比如链 （ v2,v1,v8,v7,v6,v5,v4）,再加入重复边
[v2,v1],[v1,v8],[v8,v7],[v7,v6],[v6,v5],[v5,v4].
同样,任 取连 接 v6 和 v8 的一条链
(v8,v1,v2,v3,v4,v5,v6),再加入重复边
[v8,v1],[v1,v2],[v2,v3],[v3,v4],[v4,v5],[v5,v6].
于是,得到图 8.30。 这时没有奇点,故它是欧拉图 。 对于这条邮递路线,重复边的总长为,
2W12+W23+W34+2W45+2W56+W67+W78+2W18=51。
6.中国邮递员问题
172
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8-30
2
5
5
9 4
4
3
4
6
4
4
3
v9
173
（ 二 ） 改进邮递路线,使重复边的总长不断减少 。
从图 8-30 中可以看出,在边
[v1,v2]旁边有两条重复边,但是如果把他们都从图中去掉,所得到的连通图仍然无奇点,还是一个邮递路线,而总长度却有所减少 。 同理,
在边 [v1,v8],[v4,v5],[v5,v6]旁边的重复边也是一样的 。
6.中国邮递员问题
174
6.中国邮递员问题一般地,在邮递路线上,如果在边 [vi,vj]旁边有两条以上的重复边,
从中去掉偶数条,那么可以得到一个总长度较少的邮递路线 。
判定标准 1 在最优邮递路线上,图中的每一条边至多有一条重复边 。
175
按此判定标准,将图 8-30改为图 8-31,这时重复边的总权减少为
21。
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8-31
2
5
5
9 4
4
3
4
6
4
4
3
v9
176
不难看出,如果把图中某个圈上的重复边去掉,而给原来没有重复边的边上加上重复边,
图中仍然没有奇点 。 因此,如果在某个圈上重复边的总权大于这个圈总权的一半,按照以上所说的作一次调整,将会得到一个总权减少的邮递路线 。
6.中国邮递员问题
177
6.中国邮递员问题判定标准 2 在最优邮递路线上,
图中每一个圈的重复边的总权小于或者等于该圈总权的一半 。
如在图 8-31中,圈 （ v2,v3,v4,v9,v2）
的总权为 24,但圈上重复边的总权为
14,大于该圈总权的一半 。
178
因此作一次改进,在该圈上去掉重复边 [v2,v3],[v3,v4],加上重复边
[v2,v9],[v9,v4],如图 8-32所示 。 这时重复边的总权减少为 10。
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8-32
2
5
5
9 4
4
3
4
6
4
4
3
v9
179
6.中国邮递员问题图 8.32 中,圈 (v1,v2,v9,v6,v7,v8,v1)
中重复边总权为 13,而该圈的总权为 24,不满足判定标准 2。 再次经过改进后,得到图 8-33。 此时,该圈中重复边的总权为 11,小于该圈的总权 24。
180
检查图 8-33中的每一个圈,判定标准 1和 2均已满足 。 于是,图中的欧拉圈就是最优邮递路线 。
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8-33
2
5
5
9 4
4
3
4
6
4
4
3V
9
181
上例说明,一个最优邮递路线一定满足判定标准 1和判定标准 2。
反之,不难证明,一个邮递路线如果满足判定标准 1和判定标准 2,那么它一定是最优邮递路线 。
小结,两个判定标准是最优邮递路线判定的充分必要条件 。
6.中国邮递员问题
182
6.中国邮递员问题值得注意的是,这个方法主要困难在于检查判定标准 2。
它要求对于图中的每一个圈都检查一遍 。 当一个连通图所包含的圈数比较多时,将会大大提高运算的工作量,比如,田,
字型的图就有 13个圈 。
183
作业：
习题 — 4
