运筹学课件制作,北京理工大学 吴祈宗等
2
第八章 图与网络分析图的基本概念与基本定理树和最小支撑树最短路问题网络系统最大流问题网络系统的最小费用最大流问题中国邮递员问题本章内容重点
3
引 言图论是应用非常广泛的运筹学分支,它已经广泛地应用于物理学控制论,信息论,
工程技术,交通运输,经济管理,电子计算机等各项领域 。 对于科学研究,市场和社会生活中的许多问题,可以同图论的理论和方法来加以解决 。 例如,各种通信线路的架设,
输油管道的铺设,铁路或者公路交通网络的合理布局等问题,都可以应用图论的方法,
简便,快捷地加以解决 。
4
引 言随着科学技术的进步,特别是电子计算机技术的发展,图论的理论获得了更进一步的发展,应用更加广泛 。 如果将复杂的工程系统和管理问题用图的理论加以描述,可以解决许多工程项目和管理决策的最优问题 。 因此,图论越来越受到工程技术人员和经营管理人员的重视 。
5
引 言
1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文,解决了著名的哥尼斯堡七座桥问题 。 德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,
河的两岸和岛屿之间有七座桥相互连接,如图 8.1a所示 。
引 言
A B
图 8.1 a
C
D
7
引 言当地的居民热衷于这样一个问题,一个漫步者如何能够走过这七座桥,并且每座桥只能走过一次,最终回到原出发地 。 尽管试验者很多,但是都没有成功 。
为了寻找答案,1736年欧拉将这个问题抽象成图 8.1b所示图形的一笔画问题 。 即能否从某一点开始不重复地一笔画出这个图形,最终回到原点 。 欧拉在他的论文中证明了这是不可能的,因为这个图形中每一个顶点都与奇数条边相连接,不可能将它一笔画出,这就是古典图论中的第一个著名问题 。
8
引 言图 8.1 b
A
C
D
B
9
在实际的生产和生活中,人们为了反映事物之间的关系,常常在纸上用点和线来画出各式各样的示意图 。
例 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
13
从以上的几个例子可以看出,我们用点和点之间的线所构成的图,反映实际生产和生活中的某些特定对象之间的特定关系 。 一般来说,通常用点表示研究对象用点与点之间的线表示研究对象之间的特定关系 。 由于在一般情况下,图中的相对位置如何,点与点之间线的长短曲直,对于反映研究对象之间的关系,显的并不重要,
因此,图论中的图与几何图,工程图等本质上是不同的 。
1.图的基本概念与基本定理
14
综上所述,图论中的图是由点和点与点之间的线所组成的 。 通常,我们把点与点之间不带箭头的线叫做 边,带箭头的线叫做 弧 。
如果一个图是由点和边所构成的,那么,
称为为 无向图,记作 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)。
1.图的基本概念与基本定理
15
例如,图 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),(v,v3),(v3,v2),
(v3,v4),(v2,v4),(v4,v5),
(v4,v6),(v,v3),(v5,v4),
(v5,v6),(v6,v7)}
1.图的基本概念与基本定理
v7v5v3
v4v2
v1 v
6
图 8.5
17
下面介绍一些常用的名词：
一个图 G或有向图 D中的 点数,记作 P(G)或
P(D),简记作 P,边数 或者 弧数,记作 q(G)或者
q(D),简记作 q。
如果边 [vi,vj]?E,那么称 vi,vj是 边的端点,
或者 vi,vj是 相邻 的 。 如果一个图 G中,一条边的两个端点是相同的,那么称为这条边是 环,如图 8.4中的边 [v,v3]是环 。 如果两个端点之间有两个端点之间有两条以上的边,那么称为它们为 多重边,如图 8.4中的边 [v1,v2],[v2,v1]。
一个无环,无多重边的图标为 简单图,一个无环,有多重边的图标图称为 多重图 。
1.图的基本概念与基本定理
18
以点 v为端点的边的个数称为点
v 的 度,记作 d(v),如图 8— 4 中
d(v1)=3,d(v2)=4,d(v3)=4,d(v4)=3。
度为零的点称为 弧立点,度为 1
的点称为 悬挂点 。 悬挂点的边称为悬挂边 。 度为奇数的点称为 奇点,
度为偶数的点称为 偶点 。
1.图的基本概念与基本定理
19
端点的度 d(v)：点 v 作为边端点的个数；
奇点,d(v)=奇数；
偶点,d(v)=偶数；
悬挂点,d(v)=1；
悬挂边,与悬挂点连接的边；
孤立点,d(v)=0；
空图,E =?，无边图
1.图的基本概念与基本定理定理 8.1 所有顶点次数之和等于所有边数的 2倍。
定理 8.2 在任一图中，奇点的个数必为偶数。
1.图的基本概念与基本定理
21
图的连通性：
链,由两两相邻的点及其相关联的边构成的点边序列 ;如,
v0,e1,v1,e2,v2,e3,v3,…,vn-1,
en,vn ;
v0,vn分别为链的起点和终点；
简单链,链中所含的边均不相同；
初等链,链中所含的点均不相同,也称通路；
1.图的基本概念与基本定理
22
圈,除起点和终点外链中所含的点均不相同的闭链；
回路,若 v0 ≠ v n 分称该链为开链，
否则称为闭链或回路；
连通图,图中任意两点之间均至少有一条通路，否则称作不连通图。
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.图的基本概念与基本定理
31
2.树和最小支撑树一,树及其性质在各种各样的图中,有一类图是十分简单又非常具有应用价值的图,这就是 树 。
例 8.3：已知有六个城市,它们之间 要架设电话线,要求任意两个城市均可以互相通话,并且电话线的总长度最短 。
32
2.树和最小支撑树如果用六个点 v1…v6代表这六个城市,
在任意两个城市之间架设电话线,即在相应的两个点之间连一条边 。 这样,六个城市的一个电话网就作成一个图 。 由于任意两个城市之间均可以通话,这个图必须是连通图 。
并且,这个图必须是无圈的 。 否则,从圈上任意去掉一条边,剩下的图仍然是六个城市的一个电话网 。 图 8.8是一个不含圈的连通图,代表了一个电话线网 。
33
2.树和最小支撑树图 8.8
v6
v3
v4
v2
v5
v1
34
2.树和最小支撑树
定义 8.1 一个 无圈的连通图叫做树 。
下面介绍树的一些重要性质：
定理 8.3 设图 G=（ V,E） 是一个树 P(G)
≥ 2,那么图 G中 至少有两个悬挂点 。
定理 8.4 图 G=（ V,E） 是一个树的充要条件是 G不含圈,并且 有且仅有 P-1条边 。
定理 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
37
2.树和最小支撑树
显然,如果图 K=( V,E’ )是图
G=(V,E)的一个支撑树,那么 K 的边数是 p(G)-1,G中不属于支撑树 K的边数是 q(G)-p(G)+1。
定理 8.7 一个图 G有支撑树的充要条件是 G是连通图。
38
2.树和最小支撑树证明,必要性显然；
充分性,设图 G是连通的，若 G不含圈，
则按照定义,G是一个树，从而 G是自身的一个支撑树。若 G含圈，则任取 G的一个圈，从该圈中任意去掉一条边，得到图 G的一支撑子图 G1。若 G1不含圈，则 G1是 G的一个支撑树。
若 G1仍然含圈，则任取 G1的一个圈，再从圈中任意去掉一条边，得到图 G的一支撑子图
G2。依此类推，可以得到图 G的一个支撑子图 GK，且不含圈，从而 GK是一个支撑树。
39
2.树和最小支撑树
定理 8.7充分性的证明，提供了一个寻找连通图支撑树的方法叫做,破圈法,。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。
例 8.4:用破圈法求出图 8-11的一个支撑树。
V5V4
V2
V3
V1
e6e5
e4
e3
e2
e1 e7
e8
40
2.树和最小支撑树取一个圈 (v1,v2,v3,v1)，在一个圈中去掉边 e3 。在剩下的图中，再取一个圈
（ v1,v2,v4,v3,v1），去掉边 e4 。再从圈
（ v3,v4 v5,v3）中去掉边 e6 。再从圈
(v1,v2,v5,v4,v3,v1 ）中去掉边 e7，
这样，剩下的图不含圈，于是得到一个支撑树，如图 8.12所示。
v2e
1
e2 e5
e8v1
v3
v4
41
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 的 最小支撑树 。
如前所述，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，一个问题的 解决可以归结为最小支撑树问题。
再如，城市间交通线的建造等，都可以归结为这一类问题。
43
2.树和最小支撑树常用的有 破圈法 和 生长法（避圈法）
两个方法：
① 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；
② 去掉该圈中权数最大的边；
反复重复 ① ② 两步，直到最短树。
44
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
46
2.树和最小支撑树解,这个问题的解决就是要求所示赋权图 8.13a中的最小支撑树。用破圈法求解。
任取一个圈，例如（ v1,v2,v3,v1 ），去掉这个圈中权最大的边 [v1,v3]。再取一个圈（ v3,v5,v2,v3），去掉边 [v2,v5]。再取一个圈（ v3,v5,v4,v2,v3），去掉边
[v3,v5]。再取一个圈（ v5,v6,v4,v5），这个圈中，有两条权最大的边 [v5,v6]和
[v4,v6]。任意去掉其中的一条，例如
[v5,v6]。这时得到一个不含圈的图，如图
8.13b所示，即是最小支撑树。
47
2.树和最小支撑树从网络图中依次寻找 权数较小的边,寻找过程中，节点不得重复，即 不得构成圈 。注意在找较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最短树或证明网络不存在最短树。
48
2.树和最小支撑树再用,生长法,求解例 8.5
解,考虑赋权图 8.13a，用生长法求解。任取一点，例如从 v1 取权较小的边（ v1,v2 ），
再从 v2 取 权较小的边（ v2,v3 ），
再从 v3 取 权较小的边（ v3,v4 ），
同理依次取（ v4,v5）,（ v4,v6 ）。
这时也得到了如图 8.13b所示的最小支撑树。
49
3.最短路径问题一,引言最短路径问题是图论中十分重要的最优化问题之一,它作为一个经常被用到的基本工具,可以解决生产实际中的许多问题,
比如城市中的管道铺设,线路安排,工厂布局,设备更新等等 。
也可以用于解决其它的最优化问题 。
50
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
51
3.最短路径问题
从 v1到 v8的路线是很多的 。 比如从 v1出发,经过 v2,v5到达 v8或者从 v1
出发,经过 v4,v6,v7到达 v8等等 。 但不同的路线,经过的总长度是不同的 。
例如,按照第一个线路,总长度是
6+1+6=13单位,按照第二个路线,总长度是 1+10+2+4=17单位 。
52
3.最短路径问题一般意义下的最短路问题,设一个赋权有向图 D =（ V,A）,对于每一个弧
a =（ vi,vj）,相应地有一个权 wij。
vs,vt是 D中的两个顶点,P是 D中从 vs到 vt
的任意一条路,定义路的权是 P 中所有弧的权的和,记作 S(p)。 最短路问题就是要在所有从 vs到 vt的路 P 中,寻找一个权最小的路 P0,亦即 S(P0)=minS(p)。 P0
叫做从 vs到 vs的 最短路 。 P0的权 S(P0)叫做从 vs到 vt的 距离,记作 d（ vs,vt） 。 由于
D是有向图,很明显 d（ vs,vt） 与 d（ vt，
vs） 一般不相等 。
53
3.最短路径问题二,Dijkstra算法下面介绍在一个赋权有向图中寻求最短路的方法 —— Dijkstra算法,它是在 1959年提出来的 。 目前公认,在所有的权 wij ≥ 0时,这个算法是寻求最短路问题最好的算法 。 并且,这个算法实际上也给出了寻求从一个始定点 vs到任意一个点 vj的最短路 。
54
3.最短路径问题
Dijkstra算法的基本思想 是从 vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数，叫做一个点的 标号 。它或者表示从 vs到该点的最短路权（叫做 P 标号 ），或者表示从 vs到该点最短路权的上界（叫做 T 标号 ）。
算法的每一步是去修改 T 标号，把某一个具有 T 标号的点改变为具有 P 标号的点，使图 D 中具有 P 标号的顶点多一个。
这样，至多经过 P -1步，就可求出从 vs
到各点 vj的最短路。
55
3.最短路径问题
以例 1为例说明这个基本思想 。 在例 1中,
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,v4） 到达 v4,是 d（ v1,v1） +w14=1
单位 。 因此,他从 v1出发到达 v4的最短路必是
（ v1,v4）,d（ v1,v4） =1。 这是因为从 v1到达 v4
的任一条路 P,假如不是 （ v1,v4）,则必先沿
（ v1,v2） 到达 v2,或者沿 （ v1,v3） 到达 v3,而这时的路程已是 6或者 3单位 。
56
例 1说明：
看从 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 10P(V1)
1
57
3.最短路径问题
由于所有的权 wij ≥ 0,因此,不论他如何再从 v2或者 v3到达 v4,所经过的总路程都不会比
1少,于是就有 d（ v1,v4） =1。 这样就使 V4变成具有 P标号的点 。 现在看从 v
1和 v4指向其余点的弧 。 如上所述,从 V
1出发,分别沿 （ v1,v2）,（ v
1,v3） 到达 v2,v3,经过的路程是 6或者 3单位 。 从 v
4出发沿 （ v4,v6） 到达 v6,经过的路程是 d （ v
1,v4 ） +w46=1+10=11 单位 。 而 min{d（ v
1,v1） +w12,d（ v1,v1） +w13,d（ v1,v4）+w
46}=d（ v1,v1） +w13=3单位 。 根据同样的理由,可以断定,从 V
1到达 V3的最短路是 （ v1,v3）,d（ v
1,v3） =3。 这样,又使点 v3变为具有 P 标号的点,不断重复以上过程,就可以求出从 v
s到达任一点 v
j的最短路 。
58
例 1说明：
再看从 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
59
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算法的步骤如下：
60
3.最短路径问题
开始 （ 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） 考察每一个使 （ vi,vj）?A,且 vj不属于 Si的点 vj,如果 T(vj)>P(vk)+wkj,
则把 T(vj)改变为 P(vk)+wkj,把 λ (vj)改变为 k,否则转入 （ 3） ；
61
3.最短路径问题
（ 3） 令 (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）。
62
3.最短路径问题
现在用 Dijkstra算法求例 1中从 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。
63
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：
64
3.最短路径问题
（ 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。
i=4:
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。
i=6：
3.最短路径问题
（ 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所示
67
3.最短路径问题
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
68
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的最短路 。
69
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到各点的最短路 （ 对于无向图叫做最短链 ） 。
作为习题,将例 8.6中所示的赋权有向图的箭头去掉,然后求出无向图中从 vs到各点的最短路 。
70
3.最短路径问题
下面证明 Dijkstra算法的正确性 。 只要证明每一个点 v∈ Si,P(ν )是从 vs到 v的最短路权,即
P(ν )=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的路 。
71
3.最短路径问题
因为 vs∈ Sn,而 vjn?Sn,所以从 vs出发,沿 H必存在一条弧,其始点属于 Sn,而终点不属于 Sn。
令 （ vr,vl ） 是 第 一 条 这 样 的 弧,于是
H=(vs…vr,vl…vjn),s(H)=S((vs,
vr))+wrl+S((vl…vjn))。 由归纳假设,P(vr)是从
vs 到 vr 的 最 短 路 权,于是,有 S （ H ）
>=P(vr)+wrl+S((vl…vjn)).根据算法中的 T标号修改 规 则,因为 vr∈ Sn,vl?Sn,故 P （ vr ）
+wrl>=Tn(vjn),且 S（（ vl…vjn）） >=所以 S（ H）
>=Tn(vjn)+S((vl,…vjn))>=Tn(vjn).这样,就证明了 Tn(vjn)是从 vs到 vjn的最短权 。 根据算法,
P(vjn)=Tn(vjn),于是就有 P(vjn)=d(vs,vjn).
72
3.最短路径问题
Dijkstra算法仅适合于所有的权
wij>=0的情形 。 如果当赋权有向图中存在有负权弧时,则该算法失效 。 例如图
8.16中,根据 Dijkstra算法,可以得出从 v1到 v2最短路权是 2,但是这显然不对,
因为从 v1到 v2的最短路是 （ v1,v3,v2）,权是 -1。
v1
v3
v22
2 -3
图 8.16
3.最短路径问题下面介绍当赋权有向图中,存在负权弧时,寻求最短路的方法,
首先,设从任一点 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的最短路径的权 。
75
设 C是赋权函数有向图 D中的一个回路 。 如果回路
C的权 S（ C） 是负数那么称 C是 D中的一个负回路 。
可以证明以下的结论：
1.如果赋权有向图 D不含有负回路,那么从 vs到任一点的最短路至多包含 P-2个中间点,并且必可取为初等路 。
2.如果赋权有向图 D不含有负回路,那么上述递推算法至多经过 P-1次迭代必收敛,可以求出从 vs到各个点的最短路权 。
3.如果上述算法经过 P-1次迭代,还存在在着某个 j,使得 d(p)(vs,vj)?d(p-1)(vs,vj),那么 D中含有负回路 。 这时,不存在从 vs到 vj的路 （ 权无界 ） 。
结论
76
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的最短路权 。
77
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)
79
3.最短路径问题
为了求出从 v1到各个点的最短路,一般采用反向追踪的方法：如果已知 d(vi,vj),那么寻求一个点 vk,使得 d(vs,vk)+wkj=d(vs,vj),然 后 记 录 下
(vk,vj),在看 d(vs,vk),寻求一个点 vi,使得
d(vs,vi)+wij=d(vs,vk)… 依次类推,一直到达为止 。
这样,从 vs到 vj的最短路是 （ vs,…vi,vk,vj）
在 本 例 中,有表 8.18 知,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)。
1.狄克斯拉方法适用于满足所有权系数大于等于 0（ lij≥0 ）
的网络最短路问题，能求出起点 v1 到所有其他点
vj 的最短距离；
2.海斯方法基本思想是在最短路线上任意两点间路线也是最短路线。利用 vi 到 vj 的一步距离求出 vi
到 vj 的两步距离再求出 vi 到 vj 的四步距离 …… 经有限次迭代可求出 vi 到 vj 的最短距离；
3.最短路径问题
3.福德方法适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离。
4,网络系统的最大流问题一 引言
在许多实际的网络系统中都存在着流量和最大流问题 。 例如铁路运输系统中的车辆流,城市给排水系统的水流问题等等 。 而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题,它对于解决生产实际问题起着十分重要的作用 。
82
4,网络系统的最大流问题图 8.19
vt
v3
v2
v1
v4
vs
17
3
5
10
8
6
11
4
5
3
Cij
图 8.19是一个网络。每一个弧旁边的权就是对应的容量
（最大通过能力） 。 要求指定一个运输方案，使得从 vs
到 vt的货运量最大，这是寻求网络系统的最大流问题 。
83
4.网络系统的最大流问题二 基本概念定义 8.5 设一个赋权有向图 D =（ V,A）,在
v中指定一个 发点 vs和一个 收点 vt,其他的点叫做中间点 。 对于 D中的每一个弧 （ vi,vj）
∈ A,都有一个权 cij 叫做 弧的容量 。 我们把这样的图 D 叫做一个 网络系统,简称网络,
记做 D =（ V,A,C） 。
网络 D上的流,是指定义在弧集合 A上的一个函数 f={f(vi,vj)}={fij} f(vi,vj)=fij叫做弧在 (vi,vj)上的流量 。
85
4.网络系统的最大流问题网络系统上 流 的特点：
(1)发点的总流出量和收点的总流入量必相等；
(2)每一个中间点的流入量与流出量的代数和等于零；
(3)每一个弧上的流量不能超过它的最大通过能力 （ 即容量 ） 。
86
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)叫做这个可行流的流量 。
87
4.网络系统的最大流问题
任意一个网络上的 可行流总是存在 的 。
例如零流 v(f)=0,就是满足以上条件的可行流 。
网络系统中 最大流问题 就是在给定的网络上寻求一个可行流 f,其流量 v(f)达到最大值 。
设流 f={fij}是网络 D上的一个可行流 。 我们把 D中 fij=cij的弧叫做 饱和弧,fij<cij
的弧叫做 非饱和弧,fij>0的弧为 非零流弧,fij=0的弧叫做 零流弧 。
4.网络系统的最大流问题
设 μ 是网络 D中连接发点 ν s和收点 vt的一条链 。 定义链的方向是从 vs到 vt,于是链 μ 上的弧被分为两类：一是弧的方向与链的方向相同,叫做 前向弧,前向弧的集合记做 μ +。 二是弧的方向与链的方向相反,叫做 后向弧,后向弧的集合记做 μ -。
89
在下图（图 8.19与 8.20合并图）中,(v4,v3)是饱和弧，
其他的弧是非饱和弧，并且都是非零流弧。
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
如图，在链 （ vs,v1,v2,v3,v4,vt)中，
μ +={(vs,v1),(v1,v2),(v2,v3),(v4,vt)},
μ -={(v4,v3)}.
vt
4.网络系统的最大流问题增广链,如果链 μ 满足以下条件：
1,在弧 （ vi,vj） ∈ μ +上,有 0<=fij<cij,
即 μ +中的每一条弧是非饱和弧 。
2,在弧 （ vi,vj） ∈ μ -上,有 0<fij<=cij,
即 μ -中的每一条弧是非零流弧 。
例如在图 8.20中,链 μ =（ vs,v1,v2,v3,v4,vt） 就是一条增广链 。
设图 D=(V,A,C),点集 S,T?V,S∩ T=ф 中 。 将起点在 S,终点在 T 的所有弧作成集合,记做 （ S,T） 。
91
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)
92
4.网络系统的最大流问题
下面的事实是显然的：一个网络 D中,
任何一个可行流 f的流量 v(f)都小于或等于这个网络中任何一个截集 (V1,V1)的截量 。 并且,如果网络上的一个可行流 f*
和网络中的一个截集 （ V1*,V1*）,满足条件 v*(f*)=c(V1*,V1*),那么 f*一定是 D上的最大流,而 （ V1*,V1*） 一定是 D的所有的截集中截量最小的一个 （ 即最小截集 ） 。
93
4.网络系统的最大流问题
定理 8.8网络中的一个可行流 f*是最大流的充分必要条件是，不存在关于 f*
的增广链。
定理 8.9在一个网络 D中，最大流的流量等于分离 vs和 vt的最小截集的截量。
定理 8.8实际上提供了一个寻求网络系统最大流的方法：如果网络 D中有一个可行流 f，只要判断网络是否存在关于可行流 f的增广链 。如果没有增广链，那么 f一定是最大流。如有增广链，
那么可以按照定理 8.9，不断改进和增大可行流 f
的流量，最终可以得到网络中的一个最大流。
94
4.网络系统的最大流问题
三,标号法
从网络中的一个可行流 f出发 （ 如果 D
中没有 f,可以令 f是零流 ）,运用标号法,
经过标号过程和调整过程,可以得到网络中的一个最大流 。
用给顶点标号的方法来定义 V1*.在标号过程中,有标号的顶点是 V1*中的点,没有标号的点不是 V1*中的点 。 如果 vt有了标号,
表示存在一条关于 f的增广链 。 如果标号过程无法进行下去,并且 vt未被标号,则表示不存在关于 f的增广链 。 这样,就得到了网络中的一个最大流和最小截集 。
4.网络系统的最大流问题
1,标号过程在标号过程中,网络中的点或者是 标号点
（ 分为已检查和未检查两种 ） 。 或者是 未标号点 。 每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的 。 以便找出增广链 。 第二个标号是为了用来确定增广链上的调整量 θ 。
标号过程开始,先给 vs标号 （ 0,+∞ ） 。 这时,vs是标号未检查的点,其他都是未标号点 。
一般地,取一个标号未检查点 vi,对一切未标号点 vj：
4.网络系统的最大流问题
1） 如果在弧 （ vi,vj） 上,fij<cij,那么给 vj标号 （ vi,l(vj)）,其中 l(vj)=min[l(vi),cij-fij].
这时,vj成为标号未检查的点 。
2） 如果在弧 （ vj,vi） 上,fij>0,那么给 vj标号
（ -vi,l(vj)）,其中 l(vj)=min[l(vi),cij-fij].
这时,vj成为标号未检查点 。
于是 vi成为标号已检查的点 。 重复以上步骤,
如果所有的标号都已经检查过,而标号过程无法进行下去,则标号法结束 。 这时的可行流就是最大流 。 但是,如果 vt被标上号,表示得到一条增广链 μ,转入下一步调整过程 。
97
2.调整过程首先按照 vt和其他的点的第一个标号,
反向追踪,找出增广链?。 例如,令 vt的第一个标号是 vk,则弧 （ vk,vt） 在 μ 上 。
再看 vk的第一个标号,若是 vi,则弧
(vi,vk)都在 μ 上 。 依次类推,直到 vs为止 。
这时,所找出的弧就成为网络 D的一条增广链 μ 。 取调整量 θ = l(vt),即 vt的第二个标号,
4.网络系统的最大流问题
98
fij+θ,当 (vi,vj)∈ μ +
令 f’ij= fij-θ,当 (vi,vj)∈ μ -
其他不变
再去掉所有的标号,对新的可行流
f’={f’ij},重新进行标号过程,直到找到网络 D的最大流为止 。
4.网络系统的最大流问题
99
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.
（ 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.网络系统的最大流问题
（ 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(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.网络系统的最大流问题
102
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.网络系统的最大流问题
104
调整后的可行流 f*,如图 8.23所示,再对这个可行流从新进行标号过程,寻找增广链 。
首先给 vs标号 （ 0,+∞ ）,看 vs,给 v1标号 （ vs,3） 。 看 v1,在弧 （ v1,v3） 上,f13=c13,
弧 （ v2,v1） 上,f21=0,均不符合条件 。 因此标号过程无法进行下去,不存在从 VS到 Vt的增广链,算法结束 。
这时,网络中的可行流 f*即是最大流,
最大流的流量 V(f*)=fs1+fs2=5.同时,也找出
D的最小截集 （ V1,V1）,其中 V1是标号的集合,
V1是未标号的集合 。
4.网络系统的最大流问题
4.网络系统的最大流问题
V4
V1
V2
V3
Vs
（ 2,1）
（ 3,0）
（ 4,3）
（ 3,3）
（ 5,2）
（ 2,2）
（ 5,3）
（ 1,0） Vt(0,+∞ )
(vs,3)
图 8.23
(Cij,fij)
（ 1,0）
106
在实际的网络系统中,当涉及到有关流的问题的时候,我们往往不仅仅考虑的是流量,还经常要考虑费用的问题 。 比如一个铁路系统的运输网络流,即要考虑网络流的货运量最大,又要考虑总费用最小 。 最小费用最大流问题就是要解决这一类问题 。
5.网络系统的最小费用最大流问题
107
设一个网络 D=（ V1,A,C）,
对于每一个弧 (vi,vj)∈ A,给定一个单位流量的费用 bij>=0,网络系统的最小费用最大流问题,是指要寻求一个最大流 f,并且流的总费用 b(f)=∑ bijfij达到最小 。
（ 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.网络系统的最小费用最大流问题
109
5.网络系统的最小费用最大流问题如果可行流在流量为 v(f)的所有可行流中的费用最小,并且是?关于 f的所有增广链中的费用最小的增广链 。 那么沿增广链 μ 调整可行流 f,得到的新可行流 f’,也是流量为 v(f’)的所有可行流中的最小费用流 。
依次类推,当 f’是最大流时,就是所要求的最小费用最大流 。
110
显然,零流 f={0}是流量为 0的最小费用流 。 一般地,寻求最小费用流,总可以从零流 f={0}开始 。 下面的问题是：如果已知 f是流量为 v(f)的最小费用流,那么就要去寻找关于 f的最小费用增广链 。
对此,重新构造一个赋权有向图 M(f)，
其顶点是原网络 D的顶点,而将 D中的每一条弧 (vi,vj)变成两个相反方向的弧 （ vi,vj）
和 (vj,vi),并且定义 M(f)中弧的权 wij为：
5.网络系统的最小费用最大流问题
111
bij,当 fij<cij
wij=
+∞,当 fij=cij
-bij,当 fij>0
wij=
+∞,当 fij=0
并且将权为 +∞ 的弧从 M(f)中略去 。
即当 0 < fij < cij 时,成为 2条方向相反,权绝对值相等的弧 。 否则不变 。
5.网络系统的最小费用最大流问题
112
这样,在网络 D中寻找关于 f的最小费用增广链就等于价于在 M(f)中寻求从 vs到 vt
的最短路 。
算法开始，取零流 f(0) ={0}.一般地，
如果在第 K-1步得到最小费用流 f(K-1),则构造图 M（ f(K-1)）。在图 M（ f(K-1)）中，寻求从 vs到 vt的最短路。如果存在最短路，则
f(K-1)就是最小费用最大流。如果存在最短路，则在原网络 D中得到相对应（一一对应）
的增广链 μ 0
5.网络系统的最小费用最大流问题
113
在增广链 μ 上对 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.网络系统的最小费用最大流问题例略
114
例 8.9:求图 8-24 所示网络中的最小费用最大流,弧旁的权是 （ bij,cij）,
5.网络系统的最小费用最大流问题
(bij,Cij)
(1,8)
vt
v3v2
v5
v1
(3,10)
(2,4)
(6,2)
(1,7)
(4,10)
(2,5)
115
解：
（ 1） 取初始可行流为零流 f(0)={0},构造赋权有向图 M(f(0)),求出从 vs到 vt的最短路
(vs,v2,v1,vt),如图 8.25a中双箭头所示 。
5.网络系统的最小费用最大流问题
(1)
Vt
V3V2
Vs
V1
(3)
(2)
(6)
(1)(4)
(2)
M(f(0))
116
（ 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)),(Mf(2)),(Mf(3)),(Mf(4))。
由于在 Mf(4)中已经不存在从 vs到 vt的最短路,因此,可行流 f(4),v(f(1))=11是最小费用最大流 。
5.网络系统的最小费用最大流问题
117
5.网络系统的最小费用最大流问题
(5)
vt
v3v2
vs
v1
(0)
(0)
(0)
(5)
(0)
(5)
图 8.25b
f(1),v(f(1))=5
118
5.网络系统的最小费用最大流问题
(1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(1)
(4)
(2,5)
M(f(1))
图 8.25c
(-1)
(-1)
119
5.网络系统的最小费用最大流问题
(5)
vt
v3v2
vs
v1
(0)
(0)
(7)
(2)
(5)
(0)
图 8.25d
f(2),v(f(2))=7
120
5.网络系统的最小费用最大流问题
(1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(-1)
(4)
(-2)(-1)
(-4)
M(f(2))
图 8.25e
121
5.网络系统的最小费用最大流问题
(8)
vt
v3v2
vs
v1
(3)
(3)
(0)
(7)
(2)
(5)
图 8.25f
f(3),v(f(3))=10
122
5.网络系统的最小费用最大流问题
(-1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(-1)
(4)
(-2)
(-4)
M(f(2))
图 8.25g
(-2)
(-3)
123
5.网络系统的最小费用最大流问题
(8)
vt
v3v2
vs
v1
(4)
(4)
(0)
(7)
(3)
(4)
图 8.25h
f(4),v(f(4))=11
124
5.网络系统的最小费用最大流问题
(-1)
vt
v3v2
vs
v1
(3)
(-2)
(6)
(-1)
(4)
(2)
(-4)
M(f(4))
图 8.25i
(-2)
(-3)
125
6.中国邮递员问题
本章开始提到的邮递员问题,用图的语言来描述,就是给定一个连通图 G,在每条边上有一个非负的权,
要寻求一个圈,经过 G的每条边 至少一次,并且圈的权数最小 。 由于这个问题是我国菅梅谷同志于 1962年首先提出来的,因此国际上长称它为中国邮递员问题 。
126
6.中国邮递员问题一,一笔画问题一笔画问题,也称为遍历问题,是很有实际意义的 。
设有一个连通多重图 G,如果在 G中存在一条链,经过 G的每条边 一次且仅一次,
那么这条链叫做 欧拉链 。 如在 G中存在一个简单圈,经过 G的每条边一次,那么这个圈叫做 欧拉圈 一个图如果有欧拉圈,
那么这个图叫做 欧拉图 。 很明显,一个图 G如果能够一笔画出,那么这个图一定是欧拉图或者含有欧拉链 。
127
6.中国邮递员问题
定理 8.10 一个连通多重图 G是欧拉图的充分必要条件是 G中无奇点 。
证,必要性,显然 。
充分性,不妨设,连通多重图 G至少有三点,对 G的边数 q用数学归纳法 。 因为 G是连通的,
并且不含奇点,故 q>=3。
当 q=3时,显然 G是欧拉图 。 假设 q=n时成立,
看 q=m+1的情形：由于 G是无奇点的连通图,并且
G的点数 p>=3,因此存在三个点 μ,v,w,使得 [μ,
v],[w,v]∈ E。 从 G中去掉边 [μ,v],[w,v],增加新的边 [μ,w],得到一个新的多重图 G1,G1有
q-1条边,且仍不含奇点,G1至多有两个分图 。
128
6.中国邮递员问题
若 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中的欧拉圈 。
推论 一个多重连通图 G有欧拉链的充分必要条件是 G有且仅有两个奇点 。
这个推论的证明留给读者作为习题 。
从这个定理的证明可以看出,识别一个连通图能否一笔画出的条件是它是否有奇点 。 若有奇点,就不能一笔画出 。 若没有奇点,就能够一笔画出,并回到原出发地 。
129
6.中国邮递员问题
比如前面提到的哥尼斯堡七桥问题,
欧拉把它抽象成具有四个项点,并且都是奇点的图 8.26的形状 。 很明显,一个漫步者无论如何也不可能重复的走完七座桥,并最终回到原出发地 。 图 8.27。
仅有两个奇点,可以一笔画出 。
图 8.26
BA
D
C
图 8.27
v5
v6v4v2
v1 v3
130
6.中国邮递员问题
二,图上作业法
从一笔画问题的讨论可知,一个邮递员在他所负责投递的街道范围内,如果街道构成的图中没有奇点,那么他就可以从邮局出发,经过每条街道一次,且仅一次,并最终回到原出发地 。 但是,如果街道构成的图中有奇点,他就必然要在某些街道重复走几次 。
例如,在图 8.27表示的街道图中,v1表示邮局所在地,每条街道的长度是 1,邮递员可以按照以下的路线行走：
131
6.中国邮递员问题
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]上各走 3两次,按照第 2条路线走,在边 [v3,v2],[v3,v5]上各走了两次 。
132
6.中国邮递员问题
在连通图 G中,如果在边 [vi,vj]
上重复走几次,那么就在点 vi,vj之间增加了几条相应的边,每条边的权和原来的权相等,并把新增加的边叫做重复边 。 显然,这条路线构成新图中的欧拉圈 。 如图 8.28a,b
所示 。 并且,邮递员的两条边走路线总路程的差等于新增加重复边总权的差 。
133
6.中国邮递员问题图 8.28
v5
v6v4v2
v1 v3
a
v5
v6v4v2
v1 v3
b
134
6.中国邮递员问题
中国邮递员问题也可以表示为：在一个有奇点的连通图中 。 要求增加一些重复边,使得新的连通图不含有奇点,并且增加的重复边总权最小 。
我们把增加重复边后不含奇点的新的连通图叫做邮递路线,而总权最小的邮递路线叫做 最优邮递路线 。
(下略 ) 下面我们来介绍初始邮递路线的确定,改进,以及一个邮递路线是否是最优路线的判定标准的方法
-----图上作业法 。
135
6.中国邮递员问题
（ 一 ） 初始邮递路线的确定方法
由于任何一个图中,奇点的个数为偶数,
所以如果一个连通图有奇点,就可以把它们两两配成对,而 每对奇点之间必有一条链 （ 图是连通的 ）,我们把这条链的所有边作为重复边追加到图中去,这样得到的新连通图必无奇点,
这就给出了初始投递路线 。
例如,在图 8.29中,v1是邮局所在地,并有四个奇点 v2,v4,v6,v8,将它们两两配对,比如 v2和 v4为一对,v6和 v8为一对 。
136
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8.29
2
5
5
9 4
4
3
4
6
4
4
3
v9
137
在连接 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
在连通图 8.30中,没有奇点,故它是欧拉图 。 对 于 这条 邮 递路 线,重复 边 的总 长为,2W12+W23+W34+2W45+2W56+W67+W78+2W18=51。
6.中国邮递员问题
138
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8.30
2
5
5
9 4
4
3
4
6
4
4
3
v9
139
（ 二 ） 改进邮递路线,使重复边的总长不断减少 。
从图 8.30中可以看出,在边 [v1,v2]旁边有两条重复边,但是如果把他们都从图中去掉,所得到的连通图仍然无奇点,还是一个邮递路线,而总 长 度 却 有 所 减 少 。 同理,在边
[v1,v8],[v4,v5],[v5,v6]旁边的重复边也是一样的 。
一般地,在邮递路线上,如果在边 [vi,vj]旁边有两条以上的重复边,从中去掉偶数条,那么可以得到一个总长度较少的邮递路线 。
6.中国邮递员问题
140
判定标准 1。 在最优邮递路线上,图中的每一条边 至多有一条重复边 。
按此判定标准,将图 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
141
不难看出,如果把图中某个圈上的重复边去掉,而给原来没有重复边的边上加上重复边,图中仍然没有奇点 。 因此,如果在某个圈上重复边的总权大于这个圈总权的一半,按照以上所说的作一次调整,
将会得到一个总权减少的邮递路线 。
判定标准 2。 在最优邮递路线上,图中每一个圈的重复边的总权小于或者等于该圈总权的一半 。
6.中国邮递员问题
142
比如在图 8.31 中,圈
（ v2,v3,v4,v9,v2） 的总权为 24,但圈上重复边的总权为 14,大于该圈总权的一半 。 因此作一次改进,在该圈上去掉重复边 [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
143
在图 8.32中,圈 (v1,v2,v9,v6,v7,v8,v1)
中重复边总权为 13,而该圈的总权为 24,不满足判定标准 2。 再次经过改进后,得到图
8.33。 此时,该圈中重复边的总权为 11,小于该圈的总权 24。
检查图 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
144
从这个例子可知,一个最优邮递路线一定满足判定标准 1和判定标准 2。 反之,不难证明,
一个邮递路线如果满足判定标准 1和判定标准 2，
那么它一定是最优邮递路线 。 也就是这两个判定标准是最优邮递路线判定的充分必要条件 。
值得注意的是,这个方法主要困难在于检查判定标准 2。 它要求对于图中的每一个圈都检查一遍 。 当一个连通图所包含的圈数比较多时,
将会大大提高运算的工作量,比如,田,字型的图就有 13个圈 。
到目前为止,关于中国邮递员问题,已经找到了更好的算法,由于篇幅所限,我们就不去介绍它了 。
6.中国邮递员问题
2
第八章 图与网络分析图的基本概念与基本定理树和最小支撑树最短路问题网络系统最大流问题网络系统的最小费用最大流问题中国邮递员问题本章内容重点
3
引 言图论是应用非常广泛的运筹学分支,它已经广泛地应用于物理学控制论,信息论,
工程技术,交通运输,经济管理,电子计算机等各项领域 。 对于科学研究,市场和社会生活中的许多问题,可以同图论的理论和方法来加以解决 。 例如,各种通信线路的架设,
输油管道的铺设,铁路或者公路交通网络的合理布局等问题,都可以应用图论的方法,
简便,快捷地加以解决 。
4
引 言随着科学技术的进步,特别是电子计算机技术的发展,图论的理论获得了更进一步的发展,应用更加广泛 。 如果将复杂的工程系统和管理问题用图的理论加以描述,可以解决许多工程项目和管理决策的最优问题 。 因此,图论越来越受到工程技术人员和经营管理人员的重视 。
5
引 言
1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文,解决了著名的哥尼斯堡七座桥问题 。 德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,
河的两岸和岛屿之间有七座桥相互连接,如图 8.1a所示 。
引 言
A B
图 8.1 a
C
D
7
引 言当地的居民热衷于这样一个问题,一个漫步者如何能够走过这七座桥,并且每座桥只能走过一次,最终回到原出发地 。 尽管试验者很多,但是都没有成功 。
为了寻找答案,1736年欧拉将这个问题抽象成图 8.1b所示图形的一笔画问题 。 即能否从某一点开始不重复地一笔画出这个图形,最终回到原点 。 欧拉在他的论文中证明了这是不可能的,因为这个图形中每一个顶点都与奇数条边相连接,不可能将它一笔画出,这就是古典图论中的第一个著名问题 。
8
引 言图 8.1 b
A
C
D
B
9
在实际的生产和生活中,人们为了反映事物之间的关系,常常在纸上用点和线来画出各式各样的示意图 。
例 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
13
从以上的几个例子可以看出,我们用点和点之间的线所构成的图,反映实际生产和生活中的某些特定对象之间的特定关系 。 一般来说,通常用点表示研究对象用点与点之间的线表示研究对象之间的特定关系 。 由于在一般情况下,图中的相对位置如何,点与点之间线的长短曲直,对于反映研究对象之间的关系,显的并不重要,
因此,图论中的图与几何图,工程图等本质上是不同的 。
1.图的基本概念与基本定理
14
综上所述,图论中的图是由点和点与点之间的线所组成的 。 通常,我们把点与点之间不带箭头的线叫做 边,带箭头的线叫做 弧 。
如果一个图是由点和边所构成的,那么,
称为为 无向图,记作 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)。
1.图的基本概念与基本定理
15
例如,图 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),(v,v3),(v3,v2),
(v3,v4),(v2,v4),(v4,v5),
(v4,v6),(v,v3),(v5,v4),
(v5,v6),(v6,v7)}
1.图的基本概念与基本定理
v7v5v3
v4v2
v1 v
6
图 8.5
17
下面介绍一些常用的名词：
一个图 G或有向图 D中的 点数,记作 P(G)或
P(D),简记作 P,边数 或者 弧数,记作 q(G)或者
q(D),简记作 q。
如果边 [vi,vj]?E,那么称 vi,vj是 边的端点,
或者 vi,vj是 相邻 的 。 如果一个图 G中,一条边的两个端点是相同的,那么称为这条边是 环,如图 8.4中的边 [v,v3]是环 。 如果两个端点之间有两个端点之间有两条以上的边,那么称为它们为 多重边,如图 8.4中的边 [v1,v2],[v2,v1]。
一个无环,无多重边的图标为 简单图,一个无环,有多重边的图标图称为 多重图 。
1.图的基本概念与基本定理
18
以点 v为端点的边的个数称为点
v 的 度,记作 d(v),如图 8— 4 中
d(v1)=3,d(v2)=4,d(v3)=4,d(v4)=3。
度为零的点称为 弧立点,度为 1
的点称为 悬挂点 。 悬挂点的边称为悬挂边 。 度为奇数的点称为 奇点,
度为偶数的点称为 偶点 。
1.图的基本概念与基本定理
19
端点的度 d(v)：点 v 作为边端点的个数；
奇点,d(v)=奇数；
偶点,d(v)=偶数；
悬挂点,d(v)=1；
悬挂边,与悬挂点连接的边；
孤立点,d(v)=0；
空图,E =?，无边图
1.图的基本概念与基本定理定理 8.1 所有顶点次数之和等于所有边数的 2倍。
定理 8.2 在任一图中，奇点的个数必为偶数。
1.图的基本概念与基本定理
21
图的连通性：
链,由两两相邻的点及其相关联的边构成的点边序列 ;如,
v0,e1,v1,e2,v2,e3,v3,…,vn-1,
en,vn ;
v0,vn分别为链的起点和终点；
简单链,链中所含的边均不相同；
初等链,链中所含的点均不相同,也称通路；
1.图的基本概念与基本定理
22
圈,除起点和终点外链中所含的点均不相同的闭链；
回路,若 v0 ≠ v n 分称该链为开链，
否则称为闭链或回路；
连通图,图中任意两点之间均至少有一条通路，否则称作不连通图。
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.图的基本概念与基本定理
31
2.树和最小支撑树一,树及其性质在各种各样的图中,有一类图是十分简单又非常具有应用价值的图,这就是 树 。
例 8.3：已知有六个城市,它们之间 要架设电话线,要求任意两个城市均可以互相通话,并且电话线的总长度最短 。
32
2.树和最小支撑树如果用六个点 v1…v6代表这六个城市,
在任意两个城市之间架设电话线,即在相应的两个点之间连一条边 。 这样,六个城市的一个电话网就作成一个图 。 由于任意两个城市之间均可以通话,这个图必须是连通图 。
并且,这个图必须是无圈的 。 否则,从圈上任意去掉一条边,剩下的图仍然是六个城市的一个电话网 。 图 8.8是一个不含圈的连通图,代表了一个电话线网 。
33
2.树和最小支撑树图 8.8
v6
v3
v4
v2
v5
v1
34
2.树和最小支撑树
定义 8.1 一个 无圈的连通图叫做树 。
下面介绍树的一些重要性质：
定理 8.3 设图 G=（ V,E） 是一个树 P(G)
≥ 2,那么图 G中 至少有两个悬挂点 。
定理 8.4 图 G=（ V,E） 是一个树的充要条件是 G不含圈,并且 有且仅有 P-1条边 。
定理 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
37
2.树和最小支撑树
显然,如果图 K=( V,E’ )是图
G=(V,E)的一个支撑树,那么 K 的边数是 p(G)-1,G中不属于支撑树 K的边数是 q(G)-p(G)+1。
定理 8.7 一个图 G有支撑树的充要条件是 G是连通图。
38
2.树和最小支撑树证明,必要性显然；
充分性,设图 G是连通的，若 G不含圈，
则按照定义,G是一个树，从而 G是自身的一个支撑树。若 G含圈，则任取 G的一个圈，从该圈中任意去掉一条边，得到图 G的一支撑子图 G1。若 G1不含圈，则 G1是 G的一个支撑树。
若 G1仍然含圈，则任取 G1的一个圈，再从圈中任意去掉一条边，得到图 G的一支撑子图
G2。依此类推，可以得到图 G的一个支撑子图 GK，且不含圈，从而 GK是一个支撑树。
39
2.树和最小支撑树
定理 8.7充分性的证明，提供了一个寻找连通图支撑树的方法叫做,破圈法,。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。
例 8.4:用破圈法求出图 8-11的一个支撑树。
V5V4
V2
V3
V1
e6e5
e4
e3
e2
e1 e7
e8
40
2.树和最小支撑树取一个圈 (v1,v2,v3,v1)，在一个圈中去掉边 e3 。在剩下的图中，再取一个圈
（ v1,v2,v4,v3,v1），去掉边 e4 。再从圈
（ v3,v4 v5,v3）中去掉边 e6 。再从圈
(v1,v2,v5,v4,v3,v1 ）中去掉边 e7，
这样，剩下的图不含圈，于是得到一个支撑树，如图 8.12所示。
v2e
1
e2 e5
e8v1
v3
v4
41
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 的 最小支撑树 。
如前所述，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，一个问题的 解决可以归结为最小支撑树问题。
再如，城市间交通线的建造等，都可以归结为这一类问题。
43
2.树和最小支撑树常用的有 破圈法 和 生长法（避圈法）
两个方法：
① 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；
② 去掉该圈中权数最大的边；
反复重复 ① ② 两步，直到最短树。
44
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
46
2.树和最小支撑树解,这个问题的解决就是要求所示赋权图 8.13a中的最小支撑树。用破圈法求解。
任取一个圈，例如（ v1,v2,v3,v1 ），去掉这个圈中权最大的边 [v1,v3]。再取一个圈（ v3,v5,v2,v3），去掉边 [v2,v5]。再取一个圈（ v3,v5,v4,v2,v3），去掉边
[v3,v5]。再取一个圈（ v5,v6,v4,v5），这个圈中，有两条权最大的边 [v5,v6]和
[v4,v6]。任意去掉其中的一条，例如
[v5,v6]。这时得到一个不含圈的图，如图
8.13b所示，即是最小支撑树。
47
2.树和最小支撑树从网络图中依次寻找 权数较小的边,寻找过程中，节点不得重复，即 不得构成圈 。注意在找较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最短树或证明网络不存在最短树。
48
2.树和最小支撑树再用,生长法,求解例 8.5
解,考虑赋权图 8.13a，用生长法求解。任取一点，例如从 v1 取权较小的边（ v1,v2 ），
再从 v2 取 权较小的边（ v2,v3 ），
再从 v3 取 权较小的边（ v3,v4 ），
同理依次取（ v4,v5）,（ v4,v6 ）。
这时也得到了如图 8.13b所示的最小支撑树。
49
3.最短路径问题一,引言最短路径问题是图论中十分重要的最优化问题之一,它作为一个经常被用到的基本工具,可以解决生产实际中的许多问题,
比如城市中的管道铺设,线路安排,工厂布局,设备更新等等 。
也可以用于解决其它的最优化问题 。
50
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
51
3.最短路径问题
从 v1到 v8的路线是很多的 。 比如从 v1出发,经过 v2,v5到达 v8或者从 v1
出发,经过 v4,v6,v7到达 v8等等 。 但不同的路线,经过的总长度是不同的 。
例如,按照第一个线路,总长度是
6+1+6=13单位,按照第二个路线,总长度是 1+10+2+4=17单位 。
52
3.最短路径问题一般意义下的最短路问题,设一个赋权有向图 D =（ V,A）,对于每一个弧
a =（ vi,vj）,相应地有一个权 wij。
vs,vt是 D中的两个顶点,P是 D中从 vs到 vt
的任意一条路,定义路的权是 P 中所有弧的权的和,记作 S(p)。 最短路问题就是要在所有从 vs到 vt的路 P 中,寻找一个权最小的路 P0,亦即 S(P0)=minS(p)。 P0
叫做从 vs到 vs的 最短路 。 P0的权 S(P0)叫做从 vs到 vt的 距离,记作 d（ vs,vt） 。 由于
D是有向图,很明显 d（ vs,vt） 与 d（ vt，
vs） 一般不相等 。
53
3.最短路径问题二,Dijkstra算法下面介绍在一个赋权有向图中寻求最短路的方法 —— Dijkstra算法,它是在 1959年提出来的 。 目前公认,在所有的权 wij ≥ 0时,这个算法是寻求最短路问题最好的算法 。 并且,这个算法实际上也给出了寻求从一个始定点 vs到任意一个点 vj的最短路 。
54
3.最短路径问题
Dijkstra算法的基本思想 是从 vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数，叫做一个点的 标号 。它或者表示从 vs到该点的最短路权（叫做 P 标号 ），或者表示从 vs到该点最短路权的上界（叫做 T 标号 ）。
算法的每一步是去修改 T 标号，把某一个具有 T 标号的点改变为具有 P 标号的点，使图 D 中具有 P 标号的顶点多一个。
这样，至多经过 P -1步，就可求出从 vs
到各点 vj的最短路。
55
3.最短路径问题
以例 1为例说明这个基本思想 。 在例 1中,
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,v4） 到达 v4,是 d（ v1,v1） +w14=1
单位 。 因此,他从 v1出发到达 v4的最短路必是
（ v1,v4）,d（ v1,v4） =1。 这是因为从 v1到达 v4
的任一条路 P,假如不是 （ v1,v4）,则必先沿
（ v1,v2） 到达 v2,或者沿 （ v1,v3） 到达 v3,而这时的路程已是 6或者 3单位 。
56
例 1说明：
看从 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 10P(V1)
1
57
3.最短路径问题
由于所有的权 wij ≥ 0,因此,不论他如何再从 v2或者 v3到达 v4,所经过的总路程都不会比
1少,于是就有 d（ v1,v4） =1。 这样就使 V4变成具有 P标号的点 。 现在看从 v
1和 v4指向其余点的弧 。 如上所述,从 V
1出发,分别沿 （ v1,v2）,（ v
1,v3） 到达 v2,v3,经过的路程是 6或者 3单位 。 从 v
4出发沿 （ v4,v6） 到达 v6,经过的路程是 d （ v
1,v4 ） +w46=1+10=11 单位 。 而 min{d（ v
1,v1） +w12,d（ v1,v1） +w13,d（ v1,v4）+w
46}=d（ v1,v1） +w13=3单位 。 根据同样的理由,可以断定,从 V
1到达 V3的最短路是 （ v1,v3）,d（ v
1,v3） =3。 这样,又使点 v3变为具有 P 标号的点,不断重复以上过程,就可以求出从 v
s到达任一点 v
j的最短路 。
58
例 1说明：
再看从 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
59
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算法的步骤如下：
60
3.最短路径问题
开始 （ 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） 考察每一个使 （ vi,vj）?A,且 vj不属于 Si的点 vj,如果 T(vj)>P(vk)+wkj,
则把 T(vj)改变为 P(vk)+wkj,把 λ (vj)改变为 k,否则转入 （ 3） ；
61
3.最短路径问题
（ 3） 令 (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）。
62
3.最短路径问题
现在用 Dijkstra算法求例 1中从 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。
63
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：
64
3.最短路径问题
（ 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。
i=4:
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。
i=6：
3.最短路径问题
（ 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所示
67
3.最短路径问题
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
68
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的最短路 。
69
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到各点的最短路 （ 对于无向图叫做最短链 ） 。
作为习题,将例 8.6中所示的赋权有向图的箭头去掉,然后求出无向图中从 vs到各点的最短路 。
70
3.最短路径问题
下面证明 Dijkstra算法的正确性 。 只要证明每一个点 v∈ Si,P(ν )是从 vs到 v的最短路权,即
P(ν )=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的路 。
71
3.最短路径问题
因为 vs∈ Sn,而 vjn?Sn,所以从 vs出发,沿 H必存在一条弧,其始点属于 Sn,而终点不属于 Sn。
令 （ vr,vl ） 是 第 一 条 这 样 的 弧,于是
H=(vs…vr,vl…vjn),s(H)=S((vs,
vr))+wrl+S((vl…vjn))。 由归纳假设,P(vr)是从
vs 到 vr 的 最 短 路 权,于是,有 S （ H ）
>=P(vr)+wrl+S((vl…vjn)).根据算法中的 T标号修改 规 则,因为 vr∈ Sn,vl?Sn,故 P （ vr ）
+wrl>=Tn(vjn),且 S（（ vl…vjn）） >=所以 S（ H）
>=Tn(vjn)+S((vl,…vjn))>=Tn(vjn).这样,就证明了 Tn(vjn)是从 vs到 vjn的最短权 。 根据算法,
P(vjn)=Tn(vjn),于是就有 P(vjn)=d(vs,vjn).
72
3.最短路径问题
Dijkstra算法仅适合于所有的权
wij>=0的情形 。 如果当赋权有向图中存在有负权弧时,则该算法失效 。 例如图
8.16中,根据 Dijkstra算法,可以得出从 v1到 v2最短路权是 2,但是这显然不对,
因为从 v1到 v2的最短路是 （ v1,v3,v2）,权是 -1。
v1
v3
v22
2 -3
图 8.16
3.最短路径问题下面介绍当赋权有向图中,存在负权弧时,寻求最短路的方法,
首先,设从任一点 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的最短路径的权 。
75
设 C是赋权函数有向图 D中的一个回路 。 如果回路
C的权 S（ C） 是负数那么称 C是 D中的一个负回路 。
可以证明以下的结论：
1.如果赋权有向图 D不含有负回路,那么从 vs到任一点的最短路至多包含 P-2个中间点,并且必可取为初等路 。
2.如果赋权有向图 D不含有负回路,那么上述递推算法至多经过 P-1次迭代必收敛,可以求出从 vs到各个点的最短路权 。
3.如果上述算法经过 P-1次迭代,还存在在着某个 j,使得 d(p)(vs,vj)?d(p-1)(vs,vj),那么 D中含有负回路 。 这时,不存在从 vs到 vj的路 （ 权无界 ） 。
结论
76
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的最短路权 。
77
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)
79
3.最短路径问题
为了求出从 v1到各个点的最短路,一般采用反向追踪的方法：如果已知 d(vi,vj),那么寻求一个点 vk,使得 d(vs,vk)+wkj=d(vs,vj),然 后 记 录 下
(vk,vj),在看 d(vs,vk),寻求一个点 vi,使得
d(vs,vi)+wij=d(vs,vk)… 依次类推,一直到达为止 。
这样,从 vs到 vj的最短路是 （ vs,…vi,vk,vj）
在 本 例 中,有表 8.18 知,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)。
1.狄克斯拉方法适用于满足所有权系数大于等于 0（ lij≥0 ）
的网络最短路问题，能求出起点 v1 到所有其他点
vj 的最短距离；
2.海斯方法基本思想是在最短路线上任意两点间路线也是最短路线。利用 vi 到 vj 的一步距离求出 vi
到 vj 的两步距离再求出 vi 到 vj 的四步距离 …… 经有限次迭代可求出 vi 到 vj 的最短距离；
3.最短路径问题
3.福德方法适用于有负权系数，但无负回路的有向或无向网络的最短路问题，能求出起点 v1 到所有其它点 vj 的最短距离。
4,网络系统的最大流问题一 引言
在许多实际的网络系统中都存在着流量和最大流问题 。 例如铁路运输系统中的车辆流,城市给排水系统的水流问题等等 。 而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题,它对于解决生产实际问题起着十分重要的作用 。
82
4,网络系统的最大流问题图 8.19
vt
v3
v2
v1
v4
vs
17
3
5
10
8
6
11
4
5
3
Cij
图 8.19是一个网络。每一个弧旁边的权就是对应的容量
（最大通过能力） 。 要求指定一个运输方案，使得从 vs
到 vt的货运量最大，这是寻求网络系统的最大流问题 。
83
4.网络系统的最大流问题二 基本概念定义 8.5 设一个赋权有向图 D =（ V,A）,在
v中指定一个 发点 vs和一个 收点 vt,其他的点叫做中间点 。 对于 D中的每一个弧 （ vi,vj）
∈ A,都有一个权 cij 叫做 弧的容量 。 我们把这样的图 D 叫做一个 网络系统,简称网络,
记做 D =（ V,A,C） 。
网络 D上的流,是指定义在弧集合 A上的一个函数 f={f(vi,vj)}={fij} f(vi,vj)=fij叫做弧在 (vi,vj)上的流量 。
85
4.网络系统的最大流问题网络系统上 流 的特点：
(1)发点的总流出量和收点的总流入量必相等；
(2)每一个中间点的流入量与流出量的代数和等于零；
(3)每一个弧上的流量不能超过它的最大通过能力 （ 即容量 ） 。
86
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)叫做这个可行流的流量 。
87
4.网络系统的最大流问题
任意一个网络上的 可行流总是存在 的 。
例如零流 v(f)=0,就是满足以上条件的可行流 。
网络系统中 最大流问题 就是在给定的网络上寻求一个可行流 f,其流量 v(f)达到最大值 。
设流 f={fij}是网络 D上的一个可行流 。 我们把 D中 fij=cij的弧叫做 饱和弧,fij<cij
的弧叫做 非饱和弧,fij>0的弧为 非零流弧,fij=0的弧叫做 零流弧 。
4.网络系统的最大流问题
设 μ 是网络 D中连接发点 ν s和收点 vt的一条链 。 定义链的方向是从 vs到 vt,于是链 μ 上的弧被分为两类：一是弧的方向与链的方向相同,叫做 前向弧,前向弧的集合记做 μ +。 二是弧的方向与链的方向相反,叫做 后向弧,后向弧的集合记做 μ -。
89
在下图（图 8.19与 8.20合并图）中,(v4,v3)是饱和弧，
其他的弧是非饱和弧，并且都是非零流弧。
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
如图，在链 （ vs,v1,v2,v3,v4,vt)中，
μ +={(vs,v1),(v1,v2),(v2,v3),(v4,vt)},
μ -={(v4,v3)}.
vt
4.网络系统的最大流问题增广链,如果链 μ 满足以下条件：
1,在弧 （ vi,vj） ∈ μ +上,有 0<=fij<cij,
即 μ +中的每一条弧是非饱和弧 。
2,在弧 （ vi,vj） ∈ μ -上,有 0<fij<=cij,
即 μ -中的每一条弧是非零流弧 。
例如在图 8.20中,链 μ =（ vs,v1,v2,v3,v4,vt） 就是一条增广链 。
设图 D=(V,A,C),点集 S,T?V,S∩ T=ф 中 。 将起点在 S,终点在 T 的所有弧作成集合,记做 （ S,T） 。
91
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)
92
4.网络系统的最大流问题
下面的事实是显然的：一个网络 D中,
任何一个可行流 f的流量 v(f)都小于或等于这个网络中任何一个截集 (V1,V1)的截量 。 并且,如果网络上的一个可行流 f*
和网络中的一个截集 （ V1*,V1*）,满足条件 v*(f*)=c(V1*,V1*),那么 f*一定是 D上的最大流,而 （ V1*,V1*） 一定是 D的所有的截集中截量最小的一个 （ 即最小截集 ） 。
93
4.网络系统的最大流问题
定理 8.8网络中的一个可行流 f*是最大流的充分必要条件是，不存在关于 f*
的增广链。
定理 8.9在一个网络 D中，最大流的流量等于分离 vs和 vt的最小截集的截量。
定理 8.8实际上提供了一个寻求网络系统最大流的方法：如果网络 D中有一个可行流 f，只要判断网络是否存在关于可行流 f的增广链 。如果没有增广链，那么 f一定是最大流。如有增广链，
那么可以按照定理 8.9，不断改进和增大可行流 f
的流量，最终可以得到网络中的一个最大流。
94
4.网络系统的最大流问题
三,标号法
从网络中的一个可行流 f出发 （ 如果 D
中没有 f,可以令 f是零流 ）,运用标号法,
经过标号过程和调整过程,可以得到网络中的一个最大流 。
用给顶点标号的方法来定义 V1*.在标号过程中,有标号的顶点是 V1*中的点,没有标号的点不是 V1*中的点 。 如果 vt有了标号,
表示存在一条关于 f的增广链 。 如果标号过程无法进行下去,并且 vt未被标号,则表示不存在关于 f的增广链 。 这样,就得到了网络中的一个最大流和最小截集 。
4.网络系统的最大流问题
1,标号过程在标号过程中,网络中的点或者是 标号点
（ 分为已检查和未检查两种 ） 。 或者是 未标号点 。 每个标号点的标号包含两部分：第一个标号表示这个标号是从那一点得到的 。 以便找出增广链 。 第二个标号是为了用来确定增广链上的调整量 θ 。
标号过程开始,先给 vs标号 （ 0,+∞ ） 。 这时,vs是标号未检查的点,其他都是未标号点 。
一般地,取一个标号未检查点 vi,对一切未标号点 vj：
4.网络系统的最大流问题
1） 如果在弧 （ vi,vj） 上,fij<cij,那么给 vj标号 （ vi,l(vj)）,其中 l(vj)=min[l(vi),cij-fij].
这时,vj成为标号未检查的点 。
2） 如果在弧 （ vj,vi） 上,fij>0,那么给 vj标号
（ -vi,l(vj)）,其中 l(vj)=min[l(vi),cij-fij].
这时,vj成为标号未检查点 。
于是 vi成为标号已检查的点 。 重复以上步骤,
如果所有的标号都已经检查过,而标号过程无法进行下去,则标号法结束 。 这时的可行流就是最大流 。 但是,如果 vt被标上号,表示得到一条增广链 μ,转入下一步调整过程 。
97
2.调整过程首先按照 vt和其他的点的第一个标号,
反向追踪,找出增广链?。 例如,令 vt的第一个标号是 vk,则弧 （ vk,vt） 在 μ 上 。
再看 vk的第一个标号,若是 vi,则弧
(vi,vk)都在 μ 上 。 依次类推,直到 vs为止 。
这时,所找出的弧就成为网络 D的一条增广链 μ 。 取调整量 θ = l(vt),即 vt的第二个标号,
4.网络系统的最大流问题
98
fij+θ,当 (vi,vj)∈ μ +
令 f’ij= fij-θ,当 (vi,vj)∈ μ -
其他不变
再去掉所有的标号,对新的可行流
f’={f’ij},重新进行标号过程,直到找到网络 D的最大流为止 。
4.网络系统的最大流问题
99
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.
（ 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.网络系统的最大流问题
（ 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(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.网络系统的最大流问题
102
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.网络系统的最大流问题
104
调整后的可行流 f*,如图 8.23所示,再对这个可行流从新进行标号过程,寻找增广链 。
首先给 vs标号 （ 0,+∞ ）,看 vs,给 v1标号 （ vs,3） 。 看 v1,在弧 （ v1,v3） 上,f13=c13,
弧 （ v2,v1） 上,f21=0,均不符合条件 。 因此标号过程无法进行下去,不存在从 VS到 Vt的增广链,算法结束 。
这时,网络中的可行流 f*即是最大流,
最大流的流量 V(f*)=fs1+fs2=5.同时,也找出
D的最小截集 （ V1,V1）,其中 V1是标号的集合,
V1是未标号的集合 。
4.网络系统的最大流问题
4.网络系统的最大流问题
V4
V1
V2
V3
Vs
（ 2,1）
（ 3,0）
（ 4,3）
（ 3,3）
（ 5,2）
（ 2,2）
（ 5,3）
（ 1,0） Vt(0,+∞ )
(vs,3)
图 8.23
(Cij,fij)
（ 1,0）
106
在实际的网络系统中,当涉及到有关流的问题的时候,我们往往不仅仅考虑的是流量,还经常要考虑费用的问题 。 比如一个铁路系统的运输网络流,即要考虑网络流的货运量最大,又要考虑总费用最小 。 最小费用最大流问题就是要解决这一类问题 。
5.网络系统的最小费用最大流问题
107
设一个网络 D=（ V1,A,C）,
对于每一个弧 (vi,vj)∈ A,给定一个单位流量的费用 bij>=0,网络系统的最小费用最大流问题,是指要寻求一个最大流 f,并且流的总费用 b(f)=∑ bijfij达到最小 。
（ 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.网络系统的最小费用最大流问题
109
5.网络系统的最小费用最大流问题如果可行流在流量为 v(f)的所有可行流中的费用最小,并且是?关于 f的所有增广链中的费用最小的增广链 。 那么沿增广链 μ 调整可行流 f,得到的新可行流 f’,也是流量为 v(f’)的所有可行流中的最小费用流 。
依次类推,当 f’是最大流时,就是所要求的最小费用最大流 。
110
显然,零流 f={0}是流量为 0的最小费用流 。 一般地,寻求最小费用流,总可以从零流 f={0}开始 。 下面的问题是：如果已知 f是流量为 v(f)的最小费用流,那么就要去寻找关于 f的最小费用增广链 。
对此,重新构造一个赋权有向图 M(f)，
其顶点是原网络 D的顶点,而将 D中的每一条弧 (vi,vj)变成两个相反方向的弧 （ vi,vj）
和 (vj,vi),并且定义 M(f)中弧的权 wij为：
5.网络系统的最小费用最大流问题
111
bij,当 fij<cij
wij=
+∞,当 fij=cij
-bij,当 fij>0
wij=
+∞,当 fij=0
并且将权为 +∞ 的弧从 M(f)中略去 。
即当 0 < fij < cij 时,成为 2条方向相反,权绝对值相等的弧 。 否则不变 。
5.网络系统的最小费用最大流问题
112
这样,在网络 D中寻找关于 f的最小费用增广链就等于价于在 M(f)中寻求从 vs到 vt
的最短路 。
算法开始，取零流 f(0) ={0}.一般地，
如果在第 K-1步得到最小费用流 f(K-1),则构造图 M（ f(K-1)）。在图 M（ f(K-1)）中，寻求从 vs到 vt的最短路。如果存在最短路，则
f(K-1)就是最小费用最大流。如果存在最短路，则在原网络 D中得到相对应（一一对应）
的增广链 μ 0
5.网络系统的最小费用最大流问题
113
在增广链 μ 上对 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.网络系统的最小费用最大流问题例略
114
例 8.9:求图 8-24 所示网络中的最小费用最大流,弧旁的权是 （ bij,cij）,
5.网络系统的最小费用最大流问题
(bij,Cij)
(1,8)
vt
v3v2
v5
v1
(3,10)
(2,4)
(6,2)
(1,7)
(4,10)
(2,5)
115
解：
（ 1） 取初始可行流为零流 f(0)={0},构造赋权有向图 M(f(0)),求出从 vs到 vt的最短路
(vs,v2,v1,vt),如图 8.25a中双箭头所示 。
5.网络系统的最小费用最大流问题
(1)
Vt
V3V2
Vs
V1
(3)
(2)
(6)
(1)(4)
(2)
M(f(0))
116
（ 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)),(Mf(2)),(Mf(3)),(Mf(4))。
由于在 Mf(4)中已经不存在从 vs到 vt的最短路,因此,可行流 f(4),v(f(1))=11是最小费用最大流 。
5.网络系统的最小费用最大流问题
117
5.网络系统的最小费用最大流问题
(5)
vt
v3v2
vs
v1
(0)
(0)
(0)
(5)
(0)
(5)
图 8.25b
f(1),v(f(1))=5
118
5.网络系统的最小费用最大流问题
(1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(1)
(4)
(2,5)
M(f(1))
图 8.25c
(-1)
(-1)
119
5.网络系统的最小费用最大流问题
(5)
vt
v3v2
vs
v1
(0)
(0)
(7)
(2)
(5)
(0)
图 8.25d
f(2),v(f(2))=7
120
5.网络系统的最小费用最大流问题
(1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(-1)
(4)
(-2)(-1)
(-4)
M(f(2))
图 8.25e
121
5.网络系统的最小费用最大流问题
(8)
vt
v3v2
vs
v1
(3)
(3)
(0)
(7)
(2)
(5)
图 8.25f
f(3),v(f(3))=10
122
5.网络系统的最小费用最大流问题
(-1)
vt
v3v2
vs
v1
(3)
(2)
(6)
(-1)
(4)
(-2)
(-4)
M(f(2))
图 8.25g
(-2)
(-3)
123
5.网络系统的最小费用最大流问题
(8)
vt
v3v2
vs
v1
(4)
(4)
(0)
(7)
(3)
(4)
图 8.25h
f(4),v(f(4))=11
124
5.网络系统的最小费用最大流问题
(-1)
vt
v3v2
vs
v1
(3)
(-2)
(6)
(-1)
(4)
(2)
(-4)
M(f(4))
图 8.25i
(-2)
(-3)
125
6.中国邮递员问题
本章开始提到的邮递员问题,用图的语言来描述,就是给定一个连通图 G,在每条边上有一个非负的权,
要寻求一个圈,经过 G的每条边 至少一次,并且圈的权数最小 。 由于这个问题是我国菅梅谷同志于 1962年首先提出来的,因此国际上长称它为中国邮递员问题 。
126
6.中国邮递员问题一,一笔画问题一笔画问题,也称为遍历问题,是很有实际意义的 。
设有一个连通多重图 G,如果在 G中存在一条链,经过 G的每条边 一次且仅一次,
那么这条链叫做 欧拉链 。 如在 G中存在一个简单圈,经过 G的每条边一次,那么这个圈叫做 欧拉圈 一个图如果有欧拉圈,
那么这个图叫做 欧拉图 。 很明显,一个图 G如果能够一笔画出,那么这个图一定是欧拉图或者含有欧拉链 。
127
6.中国邮递员问题
定理 8.10 一个连通多重图 G是欧拉图的充分必要条件是 G中无奇点 。
证,必要性,显然 。
充分性,不妨设,连通多重图 G至少有三点,对 G的边数 q用数学归纳法 。 因为 G是连通的,
并且不含奇点,故 q>=3。
当 q=3时,显然 G是欧拉图 。 假设 q=n时成立,
看 q=m+1的情形：由于 G是无奇点的连通图,并且
G的点数 p>=3,因此存在三个点 μ,v,w,使得 [μ,
v],[w,v]∈ E。 从 G中去掉边 [μ,v],[w,v],增加新的边 [μ,w],得到一个新的多重图 G1,G1有
q-1条边,且仍不含奇点,G1至多有两个分图 。
128
6.中国邮递员问题
若 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中的欧拉圈 。
推论 一个多重连通图 G有欧拉链的充分必要条件是 G有且仅有两个奇点 。
这个推论的证明留给读者作为习题 。
从这个定理的证明可以看出,识别一个连通图能否一笔画出的条件是它是否有奇点 。 若有奇点,就不能一笔画出 。 若没有奇点,就能够一笔画出,并回到原出发地 。
129
6.中国邮递员问题
比如前面提到的哥尼斯堡七桥问题,
欧拉把它抽象成具有四个项点,并且都是奇点的图 8.26的形状 。 很明显,一个漫步者无论如何也不可能重复的走完七座桥,并最终回到原出发地 。 图 8.27。
仅有两个奇点,可以一笔画出 。
图 8.26
BA
D
C
图 8.27
v5
v6v4v2
v1 v3
130
6.中国邮递员问题
二,图上作业法
从一笔画问题的讨论可知,一个邮递员在他所负责投递的街道范围内,如果街道构成的图中没有奇点,那么他就可以从邮局出发,经过每条街道一次,且仅一次,并最终回到原出发地 。 但是,如果街道构成的图中有奇点,他就必然要在某些街道重复走几次 。
例如,在图 8.27表示的街道图中,v1表示邮局所在地,每条街道的长度是 1,邮递员可以按照以下的路线行走：
131
6.中国邮递员问题
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]上各走 3两次,按照第 2条路线走,在边 [v3,v2],[v3,v5]上各走了两次 。
132
6.中国邮递员问题
在连通图 G中,如果在边 [vi,vj]
上重复走几次,那么就在点 vi,vj之间增加了几条相应的边,每条边的权和原来的权相等,并把新增加的边叫做重复边 。 显然,这条路线构成新图中的欧拉圈 。 如图 8.28a,b
所示 。 并且,邮递员的两条边走路线总路程的差等于新增加重复边总权的差 。
133
6.中国邮递员问题图 8.28
v5
v6v4v2
v1 v3
a
v5
v6v4v2
v1 v3
b
134
6.中国邮递员问题
中国邮递员问题也可以表示为：在一个有奇点的连通图中 。 要求增加一些重复边,使得新的连通图不含有奇点,并且增加的重复边总权最小 。
我们把增加重复边后不含奇点的新的连通图叫做邮递路线,而总权最小的邮递路线叫做 最优邮递路线 。
(下略 ) 下面我们来介绍初始邮递路线的确定,改进,以及一个邮递路线是否是最优路线的判定标准的方法
-----图上作业法 。
135
6.中国邮递员问题
（ 一 ） 初始邮递路线的确定方法
由于任何一个图中,奇点的个数为偶数,
所以如果一个连通图有奇点,就可以把它们两两配成对,而 每对奇点之间必有一条链 （ 图是连通的 ）,我们把这条链的所有边作为重复边追加到图中去,这样得到的新连通图必无奇点,
这就给出了初始投递路线 。
例如,在图 8.29中,v1是邮局所在地,并有四个奇点 v2,v4,v6,v8,将它们两两配对,比如 v2和 v4为一对,v6和 v8为一对 。
136
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8.29
2
5
5
9 4
4
3
4
6
4
4
3
v9
137
在连接 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
在连通图 8.30中,没有奇点,故它是欧拉图 。 对 于 这条 邮 递路 线,重复 边 的总 长为,2W12+W23+W34+2W45+2W56+W67+W78+2W18=51。
6.中国邮递员问题
138
6.中国邮递员问题
v7
v6
v3 v4 v5
v8v1
v2
图 8.30
2
5
5
9 4
4
3
4
6
4
4
3
v9
139
（ 二 ） 改进邮递路线,使重复边的总长不断减少 。
从图 8.30中可以看出,在边 [v1,v2]旁边有两条重复边,但是如果把他们都从图中去掉,所得到的连通图仍然无奇点,还是一个邮递路线,而总 长 度 却 有 所 减 少 。 同理,在边
[v1,v8],[v4,v5],[v5,v6]旁边的重复边也是一样的 。
一般地,在邮递路线上,如果在边 [vi,vj]旁边有两条以上的重复边,从中去掉偶数条,那么可以得到一个总长度较少的邮递路线 。
6.中国邮递员问题
140
判定标准 1。 在最优邮递路线上,图中的每一条边 至多有一条重复边 。
按此判定标准,将图 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
141
不难看出,如果把图中某个圈上的重复边去掉,而给原来没有重复边的边上加上重复边,图中仍然没有奇点 。 因此,如果在某个圈上重复边的总权大于这个圈总权的一半,按照以上所说的作一次调整,
将会得到一个总权减少的邮递路线 。
判定标准 2。 在最优邮递路线上,图中每一个圈的重复边的总权小于或者等于该圈总权的一半 。
6.中国邮递员问题
142
比如在图 8.31 中,圈
（ v2,v3,v4,v9,v2） 的总权为 24,但圈上重复边的总权为 14,大于该圈总权的一半 。 因此作一次改进,在该圈上去掉重复边 [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
143
在图 8.32中,圈 (v1,v2,v9,v6,v7,v8,v1)
中重复边总权为 13,而该圈的总权为 24,不满足判定标准 2。 再次经过改进后,得到图
8.33。 此时,该圈中重复边的总权为 11,小于该圈的总权 24。
检查图 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
144
从这个例子可知,一个最优邮递路线一定满足判定标准 1和判定标准 2。 反之,不难证明,
一个邮递路线如果满足判定标准 1和判定标准 2，
那么它一定是最优邮递路线 。 也就是这两个判定标准是最优邮递路线判定的充分必要条件 。
值得注意的是,这个方法主要困难在于检查判定标准 2。 它要求对于图中的每一个圈都检查一遍 。 当一个连通图所包含的圈数比较多时,
将会大大提高运算的工作量,比如,田,字型的图就有 13个圈 。
到目前为止,关于中国邮递员问题,已经找到了更好的算法,由于篇幅所限,我们就不去介绍它了 。
6.中国邮递员问题
