《浅析最大最小定理在信息学竞赛中的应用》由会员分享，可在线阅读，更多相关《浅析最大最小定理在信息学竞赛中的应用（42页珍藏版）》请在金锄头文库上搜索。
1、芜湖一中 周冬 max_两极相通浅析最大最小定理在信息学竞赛中的应用引入 我们在信息学竞赛中经常会遇到一些涉 及一个最大化问题和一个最小化问题的 定理 怎样利用这些定理帮助我们解题呢？Knig定理最大流最小割定理Knig定理 主要内容 n在任何一个二部图G中，最大匹配数r(G)等 于最小覆盖数c(G)Knig定理 证明 n最大匹配数不超过最小覆盖数 n任取一个最小覆盖Q，一定可以构造出一个 与之大小相等的匹配Mr(G) c(G) r(G) = c(G) c(G) |Q| = |M| r (G) c(G) r(G)Knig定理 应用 n二部图最小覆盖和最大匹配的互相转 化 n例一 Muddy F
2、ields最大流最小割定理 近年来，网络流尤其是最大流问题越来 越多的出现在各类信息学竞赛当中 最大流最小割定理是整个最大流问题 的基础与核心，其主要内容是： 最大流的流量不超过最小割的容量 存在一个流x和一个割c，且x的流量等于c的 容量例二 Moving the Hay 一个牧场由R*C个格子组成 牧场内有N条干草运输通道，每条连接两 个水平或垂直相邻的方格，最大运输量 为Li (1,1)内有很多干草，Farmer John希 望将最多的干草运送到(R,C)内 求最大运输量例二 Moving the Hay 一个R=C=3的例子，最大运输量为7 数据规模：R,C 200(1,1)(1,2)
3、(1,3)(2,1)(2,2)(2,3)(3,2)(3,3)5,53,25,52,21,16,64,17,6(3,1)分析 直接求最大流 n以每个方格为点，每条通道为边，边的容量 就是它的最大运输量 n从(1,1)到(R,C)的最大运输量就是将这两个 方格对应的点分别作为流网络中的源和汇求 出的最大流量 效率？ n点数最大40000，边数最大80000！Time Limit Exceeded!分析 效率低下的原因 n没有利用题目的特点，直接套用经典算法 特点 n题目中给出的是一个平面图 n图中的一个点为源点s，另外一个点为汇点t ，且s和t都在图中的无界面的边界上分析452316f1f2f3f
4、4分析 效率低下的原因 n没有利用题目的特点，直接套用经典算法 特点 n题目中给出的是一个平面图 n图中的一个点为源点s，另外一个点为汇点t ，且s和t都在图中的无界面的边界上 n我们称这样的平面图为s-t平面图平面图的性质 平面图性质 （欧拉公式）如果一个连通的平面图有n个 点，m条边和f个面，那么f=m-n+2 每个平面图G都有一个与其对偶的平面图G* nG*中的每个点对应G中的一个面对偶图举例4523161*2*3*4*平面图的性质 平面图性质 （欧拉公式）如果一个连通的平面图有n个 点，m条边和f个面，那么f=m-n+2 每个平面图G都有一个与其对偶的平面图G* nG*中的每个点对应G
5、中的一个面 n对于G中的每条边e ne属于两个面f1、f2，加入边(f1*， f2*)对偶图举例4523161*2*3*4*平面图的性质 平面图性质 （欧拉公式）如果一个连通的平面图有n个 点，m条边和f个面，那么f=m-n+2 每个平面图G都有一个与其对偶的平面图G* nG*中的每个点对应G中的一个面 n对于G中的每条边e ne属于两个面f1、f2，加入边(f1*， f2*) ne只属于一个面f，加入回边(f*， f*)对偶图举例4523161*2*3*4*平面图与其对偶图的关系 平面图G与其对偶图G*之间存在怎样的 关系呢？ nG的面数等于G*的点数，G*的点数等于G 的面数，G与G*边数
6、相同 nG*中的环对应G中的割一一对应4523161*2*3*4*s-t平面图上最大流的快速求法 如何利用这些性质？ n直接求解 仍然困难 n利用最大流最小割定理转化模型根据平面图与其对偶图的关系，想办法求出最小 割利用最短路求最小割 对于一个s-t平面图，我们对其进行如下改造 ： n连接s和t，得到一个附加面 对于一个s-t平面图，我们对其进行如下改造 ： n求该图的对偶图G*，令附加面对应的点为s*，无 界面对应的点为t* 对于一个s-t平面图，我们对其进行如下改造 ： n删去s*和t*之间的边123456781*3*2*4*5*7*6*8*sts*t*利用最短路求最小割 一条从s*到t*
7、的路径，就对应了一个s-t 割！ 更进一步，如果我们令每条边的长度等 于它的容量，那么最小割的容量就等于 最短路的长度！ 分析一下时间复杂度 n新图中的点数和边数都是O(n)的 n使用二叉堆优化的Dijkstra算法求最短路， 时间复杂度为O(nlog2n)123456781*3*2*4*5*7*6*8*sts*t*利用最短路求最大流 我们可以利用最短路算法得到的距离标 号构造一个最大流 定理2.1 n可以在O(nlog2n)的时间内求出s-t平面图上 的最大流。小结 回顾 得到简单的最大流模型 利用最大流最小割定理进行模型转化 根据平面图的性质解决最小割问题 构造得到最大流最大最小定理 对比
8、以上两个定理 定义3.1 n最大最小定理是一类描述同一个对象上的 一个最大化问题的解和一个最小化问题的解 之间的关系的定理。最大最小定理 共同点 n考察的两个最优化问题互为对偶问题 n证明的过程 n最大化问题M的任何一个解m的值都不超过最小 化问题N的任何一个解n的值 n可以找到M的一个解p和N的一个解q，且它们的 值相等 np和q分别为各自问题的一个最优解 简洁的最优性证明总结Knig定理最大流最小割定理最大最小定理最大匹配最小覆盖最大流最小割模型转化最大最小完全矛盾互相转化注意总结、积累勇于探索参考文献 Introduction to Graph Theory, Second Editio
9、n by Douglas B. West Network Flows: Theory, Algorithms and Applications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin Introductory Combinatorics, Third Edition by Richard A. Brualdi 运筹学教程（第三版） 胡运权 郭耀煌谢谢大家，欢迎提问！更多的例子 二部图中 n最大独立集的大小等于最小边覆盖数 n顶点的最大度数等于最小边染色数 3正则图中n点联通度等于边联通度 如何构造最大流？ 我们用
10、d(j*)表示新图中s*到j*的最短路 的长度 n对于每条边(i*,j*)，d(j*)d(i*)+ci*j* G中的每条边(i,j)，设G*与其对应的边 为(i*,j*)，定义流量xij=d(j*)-d(i*) n反对称性：xij=-xji n容量限制：xij=d(j*)-d(i*)ci*j*如何构造最大流？ 对于G中的任何一个异于s和t的节点k， 定义割Q=k，V-k包含所有与k 相关的边。那么Q中的所有边对应到G* 就形成了一个环，称为W*。 显然 k的流入量等于流出量，即x满足流量平 衡如何构造最大流？ 设P*是G*中从s*到t*的一条最短路 n对于任意的(i*,j*) P*，都有d(j
11、*)- d(i*)=ci*j* P*中的边构成了原图中的一个s-t割Q。 根据上式和ci*j*=uij可得 n对于任意的(i,j)Q，都有xij=uij。 x的流量等于Q的容量 nx是最大流，Q是最小割复杂度问题 只考虑题目中给出的边 n需要通过宽搜得到所有的面，且需要处理面 与面之间的关系 n思维复杂度与编程复杂度均比较高 可以认为原来不存在的边容量为0n不影响答案 n面与面之间的关系清晰明了 n大大降低思维和编程复杂度最大最小定理和线性规划 线性规划 n定义:在满足一些线性等式或者不等式的条件 下，最优化一个线性函数 n标准形式： 整数线性规划最大最小定理和线性规划 对偶问题最大最小定理和
12、线性规划 基本性质 n弱对偶性 n如果x是原问题的可行解，y是其对偶问题的可行 解，则恒有c*x b*y n最优性 n如果x是原问题的可行解，y是其对偶问题的可行 解，且有c*x = b*y，则x和y是各自问题的最优 解 n强最优性（对偶定理） n如果原问题及其对偶问题均有可行解，则两者均有 最优解，且最优解的目标函数值相同最大最小定理和线性规划 二部图最大匹配 n每个变量x对应一条边 n对于每个顶点v，S(v)表示所有与v关联的边 的集合最大最小定理和线性规划 二部图最小覆盖 n每个变量y对应一个点最大最小定理和线性规划 弱对偶性： n最大匹配的大小不超过最小覆盖的大小 最优性： n如果一个匹配M和一个覆盖S的大小相等， 那么M就是最大匹配，S就是最小覆盖 强对偶性 n最大匹配等于最小覆盖弱对偶性的证明证明因为所以最优性的证明证明设x*是原问题的最优解，y*是其对偶问题的最优解因为又知所以
