14
§4 最大流问题
一、网络流的基本概念 弧的容量 cij：即弧的权 弧的流量 fij：通过弧输送的物资数量 流与网络流量：将一定的物资数量从发点经网络 中的弧送至收点就形成一个流f;输送的物资数量 称为网络流量记作v(f)。 可行流 满足以下条件的流称为可行流： 1、 容量限制 0≤fij ≤cij
§3 最小生成树问题
最小生成树：网络中边的权之和最小的生成树。 • 求最小生成树的破圈法 破圈法计算步骤： ① 在网络图中寻找一个圈。若不存在圈，则已 经得到最小生成树，或网络中不存在生成树； ② 去掉该圈中权数最大的边； 反复重复 ① ② 两步，直到求出最小生成树。
A
2 S 4 C 5 2 B 1 4 3 4 D 1 E 7 5 T
5
§1 图与网络的基本概念
v2
e1
v1
e2
e3
e6 e7
v3
e4 e5
v5
e13 e14
e8 e9 e11 e12
e15 v6 e16 e17
v7 e18
v8
e19
v10
e10
v4
v9
e20
• 链：由两两相邻的点及其相关联的边构成的点边 序列；如： v1 , e1 , v2 , e4 , v5 , e7 , v3 , e9 , v7 , e18 , v9 ； 6 v1 , v9分别为链的起点和终点.
7 最小生成树=14 13
§4 最大流问题
我们可以为此例题建立线性规划数学模型： 设弧(vi,vj)上流量为fij，网络上的总的流量为F， 则有：
目标函数：max F = f12 f14 约束条件： f12 f23 f25 f14 f43 f46 f47 f23 f43 f35 f36 f25 f35 f57 f36 f46 f67 f57 f67 f47 f12 f14 fij cij , i 1, 2, , 6; j 1, 2, 7 fij 0, i 1, 2, , 6; j 1, 2, 7
第八章 图与网络模型
• 图与网最短路问络的基本概念 • 最小生成树问题
• 最大流问题 • 最小费用流问题
1
§1 图与网络的基本概念
图：由若干点以及点间联线构成。 点：表示某一具体事物 。 点间联线：表示事物之间某种特殊的关系。 边：不带箭头的点间联线。 弧(有向边)：带箭头的点间联线。 无向图——由点，边构成（P229） 有向图——由点，弧构成。（P230） 网络(赋权图)——图中每一条边(弧)[vi ,vj], 有一 常数wij与之对应, wij称为边[vi ,vj]上的权(常表示距 离，费用，时间，容量等)（P231） 2
§3 图与网络的基本概念
• 有向图：关联边有方向的图。 弧：有向图的边 a = ( u , v )，起点 u，终点 v； 路：若有从 u 到 w 的链，且各方向一致，则 称之为从 u 到 w 的路；
u
v
x
回路：起点与终点相同 的路.
y
w
7
§3 最小生成树问题
• 树：无圈连通图。记为 T＝T（V，E）. • 生成树：若一个图 G 的生成图 T 是树，则称 T 为生成 树.
8
§3 图与网络的基本概念
圈：除出起点和终点以外，链中所含的点均不相 同的闭链；如：v3 , e4 , v1 , e2 , v2 , e6 , v4 , e7 , v3 连通图：图中任意两点之间均至少有一条链相连， 否则称作非连通图。 9
§3 最小生成树问题
树的性质
■树中任意两个顶点之间只有唯一 的一条链。
• 依据树的特点（即无圈和连通）， 构造生成树的方法（破圈法）。
1、破圈法 ① 在图中寻找一个圈。 若不存在圈，则已经得 到生成树或该图不存在 生成树； ② 去掉该圈中一边； 反复重复 ① ② 两步，
直到求出生成树。
11
§3 最小生成树问题
构成生成树方法
依据树的特点（即无圈和连通），构造生成树的 方法（破圈法）。 1、破圈法 ① 在图中寻找一个圈。 若不存在圈，则已经得 到生成树或该图不存 在 生成树； ② 去掉该圈中一边； 反复重复 ① ② 两步， 12
1
4 2 1 3 5 2 3
5
■图中任意两个顶点之间有且仅有 一条链，则该图是一棵树。
■如果树的顶点个数为m，则边的 个数为m-1。 ■任何一个顶点个数为m，边数为 m-1的连通图是一棵树。 ■在树的任意两个不相邻的顶点之 间增加一条边，则形成唯一的圈。
1
4
2 3 5 4
10
§3 最小生成树问题
构成生成树方法
在网络中寻找使流量达到最大的可行流。
•定理 可行流f 是最大流的充要条件是网络中不 存在关于f 的增广链。
19
§4 最大流问题
求最大流的基本算法
（1）找出一条从发点到收点的增广链，如 果不存在这样的增广链，则已经求得最大 流。 （2）在已找出的增广链上求各弧的最小间 隙pf。 （3）在这条增广链上，增加每一条弧的顺 流流量p f ，同时减少这些弧的逆流流量p f， 20 返回步骤（1）。
15
2、每一个节点流量平衡。
§4 最大流问题
每一个节点流量平衡是指：
•中间点
流出量=流入量 , 即流出量-流入量=0
•发点
流出量-流入量= v(f) •收点 流出量-流入量= - v(f)
16
饱和弧、非饱和弧
1、如果 fij=cij，则 aij 称为饱和弧；
1 cij=5 2
(1,2)是饱和的
fij=5
1
cij=5
fij=5
2
（2，1）是不饱和的 间隙为12=f12=5
增广链
若链L上各弧的流满足：
1、0≤fij＜cij aij∈L+ （链上所有前向弧的集合 ）
2、0＜ fij≤cij aij∈L-
（链上所有后向弧的集合 ）
则L成为关于F的一条增广链。
§4 最大流问题
二、网络最大流的算法 • 网络最大流问题
2、如果 fij<cij ，则 aij 称为非饱和弧；
1 cij=5 fij=3 2 （1，2）是不饱和的 间隙为12=c12-f12=5-3=2
3、如果fij =0，弧从j到i的方向是饱和的（逆fij=0
饱和弧、非饱和弧
4、如果fij >0，弧从j到i的方向是不饱和的； （逆向）
4
V是顶点集合 E是边的集合
设 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 ∞ A 2 2 S v1 0 4 4 C ∞ 7 2 1 4 v3 B ∞ 5 4 4 3 8 ∞ D 1 7 E ∞ v6 5 14 T 13 ∞ 7 v7
5
v4
v5
由此而得两条从v1到v7的最短路R7* : {v1, v2, v3, v6, v7}与{v1, v2, v3, v5, v6, v7}
§2 最短路问题
Dijkstra算法
•求解的过程实际上是一种给点标号的过程。 标号（数，是给点记的一个数） •临时标号（T标号）——从发点到本节点的 最短距离的上界； •固定标号（P标号）——从发点到本节点的 最短距离。 某点T标号
发点P标号， 其余点T标 号 改为P标号
终点为 P标号 3
§2 最短路问题