第八章 图与网络分析

68
定义（可行流）
若对网络图D=(V,A.W) ，由vs到vt的一组 流f，若满足如下条件： （1）容量限制条件：0 fij Cij
（2）平衡条件：
对中间点vi，有输出量＝输入量
对发点和收点有
v
i
si
vj t 网络的总流量
j
69
则称f为Ｄ的一个可行流，简称流。
截量 C与流 f 的关系
72
定理：当且仅当Ｄ中不包含 f 增广链 时，Ｄ中的流 f 是最大流。
73
算法的基本思想：
1 从任一已知流(如零流)开始，递推 地构造一个其值不断增加的流的序列。 2 在每一个新流构成之后，如果Ｄ有f 的增广链，则f不是最大流。 3 可得基于P的修改流f，并作为递增流 序列的下一个流，如果不存在f的增广 良，则f 是最大流，停止，否则重复。
3
A
C
D
B
4
A
D C
B
5
例8-2：有7个人围桌而坐，如果 要求每次相邻的人都与以前完全 不同，试问不同的就座方案共有 多少种？
6
例8-3：哈密顿（Hamilton）回 路是十九世纪英国数学家哈密顿 提出，给出一个正12面体图形， 共有20个顶点表示20个城市，要 求从某个城市出发沿着棱线寻找 一条经过每个城市一次而且仅一 次，最后回到原处的周游世界线 路（并不要求经过每条边）。
57
v1
a
v0
v2
vn
截集a：v0v1，v0v2，v0vn
58
v1
b
v0
v2
vn
截集b：v1vn，v2vn，v0vn
59
v1
v0
v2
vn
c
截集c：v1vn，v1v2，v2v1，v0v2 ，v0vn
60
d
v1
v0
v2
vn
截集d：v0v1，v1v2，v2v1，v2vn，v0vn
61
定义（截集的容量）从S中各 顶点到S中各顶点全部容量之 和称为截集的容量（截量）， 用（S，S）表示。
65
定义（最小截量） 一个网络中，各种截集中容量 最小的称为最小截量，用min C(S,S)表示。
66
定义：
在赋权有向图D=(V,A.W) 中,W称为弧(vi,vj)上的权 数,在网络流中称W为通过 弧(vi,vj)的最大容量。简称 弧容量。
67
称入次为零的点为发（源）点， 记为vs。出次为零的点为收（汇） 点，记为vt。其余点为中间点。 在D中通过弧(vi,vj)的物运量称 为弧(vi,vj)的流量，所有弧上流 量的集合f={fij}称为D的一个流。
62
截集a:
Ca=C01+C02+C0n
截集b: Cb=C1n+C2n+C0n
截集c:
Cc=C1n+C12+ C02+ C0n
截集d: Cd=C01+C21+ C2n+ C0n
63
S
v0
v1
v2
vn
c
S 在截集c中边v2v1是反向的，
其容量视为零。
64
d
v1
S
v0
v2
vn
S
在截集d中边v1v2是反向的， 其容量视为零。
v5为悬挂点，
e7为悬挂边，
16
定理8-1：在一个图中，所有顶 点次的和等于边的两倍。 定理8-2：在任意一个图中，奇 顶点的个数必为偶数。 注意：一个图的形状并不唯一。 但它的三要素是不能变的。
17
定义：设G=（V，E，）和G1= （V1，E1，1）。 如果V1 V， E1 E则称G1为G 的子图；
v2
vn
49
v1
v0
v2
vn
50
v1
v0
v2
vn
V0——V1——V2——Vn
51
v1
v0
v2
vn
52
v1
v0
v2
vn
V0——V2——Vn
53
v1
v0
v2
vn54v1源自v0v2vn
55
v1
v0
v2
vn
V0——V2——V1——Vn
56
定义：（截集或割集） 如果N表示某网络中所有点的集合， 将N分成两个子集S与S，使得发点 v0在S内，收点vn在S内，则称（S， S）为分离发点与收点的截集。显 然，SS=N ，SS=，V0 S ， VnS

去掉所有的标号，再重新标号，重复第一步.
77
例
v2 (3,3)
(4,3) (1,1)
v4
(5,3)
vs
(5,1)
(1,1)
(3,0) (2,1)
vt
v1
(2,2)
v3
（wij，fij）
78
v5
29
9-2
最优树问题
树是一类极其简单而很有用的图。
定义（链）如果图中的某些点、边 可以排列成点和边的交错序列，则 称此为一条链。
定义（圈）如一条链中起点和终点 重合，则称此为一条圈。
30
定义（连通图）如果图中的任意 两点之间至少存在一条通路，则 称图为连通图，否则为不连通图。
定义（树）一个无圈的连通图称 为树。
74
算法：寻找增广链方法（标号法）
1.先给vs标号（０，＋∞)，此时vs 是已标号而未检查的点,其余的点 都是没有标号的点;一般取一个已 标号,但未检查的点vi,对一切所有 的未标号的点vj, (1).若在弧(vi,vj)上有fij<wij，则 给vj标号(vi,L(vj))，其中 L(vj)=min{wij-fij}
任一有向网络流，如果 f 是从发点到收点的流量，C(S,S) 是任一个截集，则 f C(S,S) 。
等号什么时候成立？
70
定理（最小截量 最大流） 任一有向网络流，从发点到 收点的最大流量Maxf等于最小截 量Min C(S,S) 。
即： Max f =
Min C(S,S)
71
定义：若 fij=Wij 称流对弧（vi,vj) 是饱和的，否则是不饱和的。 定义：一条从发点到收点的 f不饱 和通路称为f 的增广链。且对正向 弧有fij＜Wij，对反向弧有fij＞０．
18
v1 e5
v2 e1 e2
v3
e3
e6 e4 e7
v4
e8
v5
19
（a） 的子图 v1 e5 e1
v2
e3
v4
v5
20
如果G1=（V1，E1，1）是G= （V，E，）子图，并且V1= V， 则称G1为G的生成子图。
21
（a）的生 成子图
v1 e5
v2 e2
v3
e6
v4
e8
v5
22

37
g
d
f
a
38
定义（生成树）
如果图T是G的一个生成子图，而且T 又是一棵树，则称图T为一棵生成树。 一个子图与生成树的区别是：子图与 原图相比少弧又少点，生成树与原图 相比少弧不少点。
39
定理 图 G有生成树的充分必要条件为图是连 通图。 定义（最优树） 在赋权图G中，一棵生成树所有树柱上权 的和，称为生成树的权。具有最小权的生 成树，称为最优树（或最小树）。
76


2、调整改进： （1）按vt及其它点的第一个标号，反向跟 踪，即可得增广链μ. （2）在链上用Q=L(vt)进行调整，令
fi j Q, (vi ,v j ) μ 当 ' fi j ( fi j Q, (vi ,v j ) μ 当 fi j 当 (vi ,v j )μ ,
e3
e5
v4
v3
e4 e7 v5
e8
14
V= （ v1， v2，…... v6）
E= （ e1， e2，…... e8） （e1）= （v1， v2）
（e2）= （v1， v2）
（e7）= （v3， v5） （e8）= （v4， v4）
15
(e8)= (v4， v4),称为环； v6是孤立点，
31
树的性质：
1 在图中任意两点之间必有一条而且只有 一条通路。 2 在图中划去一条边，则图不连通。 3 在图中不相邻的两个顶点之间加一条 边，可得一个且仅得一个圈。 4 图中边数有n=p-1（p为顶点数）
32
例9-6
g e
d f
h
b
a c
33
e
d f
b
34
g
d
f
b
35
e
d
b
c
36
h
b
a c
9
8.1 图的基本概念
图论是专门研究图的理论的 一门数学分支，主要研究点和 线之间的 几何关系。
10
定义：（图）
设G=（V，E，）
其中：V= （ v1， v2，…... vm）
是m个顶点集合； E= （ e1， e2，…... en） 是n条边集合。 是描述边与顶点之间关系的函数
11
称G=（V，E，）为 一个图，如果它 满足： （1）V非空；
25
定义（链）如果图中的某些点、 边可以排列成点和边的交错序 列，则称此为一条链。
定义（圈）如一条链中起点和 终点重合，则称此为一条圈。
26
有向图 v1 e5 e6 e4 e7 v2 e1 e2 v3
e3
v4
e8
v5
27
v1
v2 e1
e3
e6
e7
v4
v5
28
圈 v1 v2 e1