离散数学-newchap10

离散数学

离散数学第10 章 网 络 模 型

H LP-DM

离散数学

国外计算机科学教材序列

离散数学(第6版)Richard Johnsonbaugh 石纯一 等译电子工业出版社

H LP-DM

离散数学

主题网络模型 通过一个网络的最大流量问题 系统优化，资源分配和人员分配

H LP-DM

离散数学

10.1 网络模型b 3 码头a 码头 5 d 2 e b 2 4 2 c 4 炼油厂z 炼油厂

求出从码头到炼油厂的最大流量H LP-DM

离散数学

定义 10.1.1一个传输网络是一个满足下列条件的简 单加权有向图 一个源 一个汇 有向边(i,j)的权 Cij 是非负数，称为容 量

H LP-DM

离散数学

例10.1.2 网络模型b 3 源a 5 d 2 e b 2 4 2 c 4 汇z

一个网络的流量是对每边赋流量值，该值不超过 一个网络的流量是对每边赋流量值， 所在边的容量。 所在边的容量。H LP-DM

离散数学

定义10.1.3 定义G是一个传输网络， Cij是 (i,j)的容量 G的一个流量F 赋予 (i,j) 值Fij 满足 Fij ≤Cij

∑ Fij =∑ Fj Ii i

流入=流出 流量守恒

H LP-DM

离散数学

10.1.4b3,2

2,2 b 2,1

c 4,3 炼油厂z 炼油厂 4,2

码头a 码头5,3

d

2,2

e

Fad = 3 流入=流出 Fdc+Fde =3H LP-DM

离散数学

定理10.1.5 定理

∑ Fai =∑ Fi zi i

流出源的流量 =流入汇的流量

H LP-DM

离散数学

定义 10.1.6

∑ Fai =∑ Fi zi i

称作流量F的值。 F

H LP-DM

离散数学

10.1.7b3,2

2,2 b 2,1

c 4,3 炼油厂z 炼油厂 4,2

码头a 码头5,3

d 流量F的值= 5

2,2

e

求G的最大流量，即使F值最大。H LP-DM

离散数学

例 10.1.86

b 3 3

w1 w2 w33

4 2 c 4

A

d

B

H LP-DM

离散数学

超级源、 超级源、汇A∞

6∞ ∞

b 3

4 2 c

w1 w2 4 B

z∞

a∞

33

d

w3H LP-DM

离散数学

10.2 最大流量算法G : 传输网络 G的一个最大流量是具有最大值的流 量 可能存在多个 基本概念：从初始流量0开始 重复增 加H LP-DM

离散数学

通路p= (v0, v1, …, vn), v0=a, vn=z 是从a到z的一条通路 如果在p中边e是从 vi-1 指向 vi 则称 是 一致定向的 否则称是非一致定向的

H LP-DM

离散数学

v0 = a (source) vn = z (sink) Path P = (v0, v1,…, vn)

H LP-DM

离散数学

10.2.1

4,1 , 3,1 , 3,2 , 2,1 , 4, 4, 2 2,2 ,

H LP-DM

离散数学

4种情况 种情况4种情况

H LP-DM

离散数学

例10.2.2

3,1 ,

4,1 , 3,2 , 5,1 , 5,2 , 3,3 ,

3,2 ,

4,0 ,

H LP-DM

离散数学

定理10.2.3 定理设P是网络G中从 a 到 z 的通路， 其中容量为 C, 流量为 F, 满足： a) 对P中一致定向的边 (i,j), Fi,j < Ci,j b)对P中非一致定向的边 (i,j), 0 < Fi,j 令 Xi,j = Ci,j – Fi,j 如果(i,j)一致定向的边 = Fi,j 如果(i,j)是非一致定向的边

H LP-DM

离散数学

定理10.2.3 定理令 = mini {Xi,j} i,j= 1,...,n 定义 Fi,j*= Fi,j (i,j) 不在 P中 Fi,j + (i,j)是P中一致定向的边 Fi,j - (i,j)是P中非一致定向的边 则F* = {Fi,j*} 是一个流量比 F 增值 d 的流.H LP-DM