1、离散数学黄晓宇HuangS本讲内容n网络模型的基本概念n最大流算法n最大流最小割n匹配引例b c码头 a 炼油厂 zed5324242求出从码头到炼油厂的最大流量定义n 一个传输网络是一个满足下列条件的简单加权有向图1. 一个源2. 一个汇3. 有向边 (i,j)的权 Cij 是非负数，称为容量n 一个网络的流量是对每边赋流量值，该值不超过所在边的容量。定义（二）n G是一个传输网络， Cij是 (i,j)的容量。 G的一个流量 F 赋予 (i,j) 值 Fij，满足：n Fij Cijn 对非源点和收点 i和 j，有n 中间节点的流出流量 流入流量定义（三）n网络流量n起点 a的流出流量终点
2、 z的流入流量，这个流量称作流量 F的值n网络流中的核心问题：最大流量码头 a b c炼油厂 zed5,33,2 2,24,22,24,32,1超级源、汇w1b ABd36 4c43 23w2w32 w1b ABd36 4c43 23aw3w2z使用网络流表示问题P458：例 10.1.9P459：习题 1 7最大流算法n 传输网络 G的一个最大流量是具有最大值的流量，最大流可能存在多个；n 基本思想：从初始流量开始，反复增加，直至不能再增大。通路n p= (v0, v1, , vn)， v0=a， vn=z 是从 a到 z的一条通路；n 如果在 p中边 e是从 vi-1 指向 vi 则称是定向的，否则称是非定向的
