Lecture11网络流的应用.PDF

Lecture 11 网络流的应用 张敬玮 2016-1-2 1 上节回顾 上一节我们讲到了网络流, 以及计算网络流的很多种算法, 包括最原始的 Ford-Furkerson, 后面的 Edmonds- Karp 算法, Dinitz 算法, 以及Tarjan 在 1983 年提出的Push-Relabel 算法. 其中有一个很关键的技巧就是缩放 (scaling). 2 本节提要 本节我们要讲网络流的应用. 因为网络流和线性规划是非常强有力的武器, 掌握了他们之后, 一大类的问题都 可以归结成这种技术. 在这里提醒大家一点, 建模的本领是我们的看家本领之一, 而建模的本事在以下几个地方 特别需要强调: 1. 线性规划, 还有我们后面要讲的半正定规划 2. 网络流, 也就是本节的主题 3. 问题的规约, 下节课我们将NP-hard 的时候将会提到 本节要将以下几个部分: • 扩展的最大流问题: 无向图上的最大流; 多源点、多汇点的流通问题; 每条边有流量下界的流通问题; 最小 费用流 Minimum Cost Flow; • 使用网络流和原始对偶技术解决实际问题: 1. 集合划分: 给我们一个集合, 让我们把集合分成两堆, 有可能可以建模成网络流, 常见的问题 有:ImageSegmentation, ProjectSelection, ProteinDomainParsing; 2. 在网络中寻找路径: 常见的有这些问题: FlightScheduling, Disjoint Paths, BaseballElimi- nation; 3. 拆分数字: BaseballElimination; 4. 构造匹配: BipartiteMatching, SurveyDesign; • 匹配的扩展: 这是计算机算法历史上十分重要的一个部分, 比如二分图匹配BipartiteMatching, 加权二 分图匹配 WeightedBipartiteMatching, 一般图匹配 GeneralGraphMatching, 加权一般图匹配 WeightedGeneralGraphMatching; • 网络流发展的简要历史. 1 3 网络流问题的扩展 网络流问题有以下几个扩展: 1. 无向图上的最大流 (MaximumFlow) 问题: 2. 多源点、多汇点的流通 (Circulation) 问题; 3. 每条边有流量下界的流通 (Circulation) 问题; 4. 最小费用流问题 (Minimum Cost Flow); 3.1 无向图上的最大流问题 问题的定义 一个无向图上的最大流问题可以形式化定义如下: 输入: 一个无向图G = V, E , 每条边 e 有容量 C (e) 0. 两个特殊的节点: 源点 s 和汇点 t; 输出: 对每条边 e, 指定一个流量值 f (e), 使得总的流量值 ∑ f (e) 最大. 流性质: 只有这里和之前讲的有向图上的最大流问题不同 1. 容量限制: 从u 到v 和从v 到u 的流量加起来不能超过(u, v) 上的容量, 即0 f (u, v)+ f (v, u) C (u, v), (u, v) E ; 2. 存储 (Conservation) 限制: f (v) = f (v), v V s, t. 一个例子 下面我们举一个例子: 图1: 有向图与无向图上的最大流 如图 1所示, 左边是上一节我们遇到的有向图上的最大流, 使用上一节的方法, 可以得到总流量是4. 而右边是 一个无向图, 比如s 到u, 可以看做是一个双向的铁路, 可以从u 往 s 运, 也可以从 s 往 u 运, 它们加起来不能 超过 4 吨. 这是一个很自然的改变, 我们也经常遇到. 这时在使用上一节讲到的那些算法就会出问题了, 如图 1右边的所示, 可以运6 吨. 也就是说我们上一节的算法不能直接使用, 需要做一些