《冬令营论文演示文稿ppt培训课件》由会员分享，可在线阅读，更多相关《冬令营论文演示文稿ppt培训课件（42页珍藏版）》请在金锄头文库上搜索。
1、 两极相通 浅析最大最小定理在信息学竞赛中的应用建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材引入 我们在信息学竞赛中经常会遇到一些涉及 一个最大化问题和一个最小化问题的定理 怎样利用这些定理帮助我们解题呢？Knig定理最大流最小割定理建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材Knig定理 主要内容 n在任何一个二部图G中，最大匹配数r(G)等于 最小覆盖数c(G)建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基
2、本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材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 Fields建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商
3、业运营方案精益生产培训教材最大流最小割定理近年来，网络流尤其是最大流问题越来 越多的出现在各类信息学竞赛当中 最大流最小割定理是整个最大流问题 的基础与核心，其主要内容是： 1.最大流的流量不超过最小割的容量 2.存在一个流x和一个割c，且x的流量等于c的 容量建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材例二 Moving the Hay 一个牧场由R*C个格子组成 牧场内有N条干草运输通道，每条连接两个 水平或垂直相邻的方格，最大运输量为Li (1,1)内有很多干草，Farmer John希望将 最多的干草运
4、送到(R,C)内 求最大运输量建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材例二 Moving the Hay 一个R=C=3的例子，最大运输量为7 数据规模：R,C 200(1,1)(1,2)(1,3)(2,1)(2,2)(2,3)(3,2)(3,3)5,53,25,52,21,16,64,17,6(3,1)建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材分析 直接求最大流 n以每个方格为点，每条通道为边，边的容量就 是它的最大运输
5、量 n从(1,1)到(R,C)的最大运输量就是将这两个方 格对应的点分别作为流网络中的源和汇求出的 最大流量 效率？ n点数最大40000，边数最大80000！Time Limit Exceeded!建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材分析 效率低下的原因 n没有利用题目的特点，直接套用经典算法 特点 n题目中给出的是一个平面图 n图中的一个点为源点s，另外一个点为汇点t， 且s和t都在图中的无界面的边界上建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后
6、期商业运营方案精益生产培训教材分析452316f1f2f3f4建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材分析 效率低下的原因 n没有利用题目的特点，直接套用经典算法 特点 n题目中给出的是一个平面图 n图中的一个点为源点s，另外一个点为汇点t， 且s和t都在图中的无界面的边界上 n我们称这样的平面图为s-t平面图建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材平面图的性质平面图性质 1. （欧拉公式）如果一个连通的平面图有n 个点
7、，m条边和f个面，那么f=m-n+2 2. 每个平面图G都有一个与其对偶的平面图G* nG*中的每个点对应G中的一个面建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材对偶图举例4523161*2*3*4*建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材平面图的性质平面图性质 1. （欧拉公式）如果一个连通的平面图有n 个点，m条边和f个面，那么f=m-n+2 2. 每个平面图G都有一个与其对偶的平面图G* nG*中的每个点对应G中的一个
8、面 n 对于G中的每条边e ne属于两个面f1、f2，加入边(f1*， f2*)建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材对偶图举例4523161*2*3*4*建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材平面图的性质平面图性质 1. （欧拉公式）如果一个连通的平面图有n 个点，m条边和f个面，那么f=m-n+2 2. 每个平面图G都有一个与其对偶的平面图G* nG*中的每个点对应G中的一个面 n 对于G中的每条边e ne属于两
9、个面f1、f2，加入边(f1*， f2*) ne只属于一个面f，加入回边(f*， f*)建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材对偶图举例4523161*2*3*4*建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材 平面图与其对偶图的关系 平面图G与其对偶图G*之间存在怎样的关 系呢？ nG的面数等于G*的点数，G*的点数等于G的面 数，G与G*边数相同 nG*中的环对应G中的割一一对应4523161*2*3*4*建筑面积计算规
10、范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材s-t平面图上最大流的快速求法 如何利用这些性质？ n直接求解 仍然困难 n利用最大流最小割定理转化模型根据平面图与其对偶图的关系，想办法求出最小割建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材利用最短路求最小割 对于一个s-t平面图，我们对其进行如下改造： n连接s和t，得到一个附加面 对于一个s-t平面图，我们对其进行如下改造： n求该图的对偶图G*，令附加面对应的点为s*，无界面 对应的点为t*
11、 对于一个s-t平面图，我们对其进行如下改造： n删去s*和t*之间的边123456781*3*2*4*5*7*6*8*sts*t*建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材利用最短路求最小割 一条从s*到t*的路径，就对应了一个s-t割 ！ 更进一步，如果我们令每条边的长度等于它 的容量，那么最小割的容量就等于最短路的 长度！ 分析一下时间复杂度 n新图中的点数和边数都是O(n)的 n使用二叉堆优化的Dijkstra算法求最短路，时 间复杂度为O(nlog2n)123456781*3*2*4*5*7*6*8
12、*sts*t*建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材利用最短路求最大流 我们可以利用最短路算法得到的距离标号 构造一个最大流 定理2.1 n可以在O(nlog2n)的时间内求出s-t平面图上的 最大流。建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材小结 回顾 得到简单的最大流模型 利用最大流最小割定理进行模型转化 根据平面图的性质解决最小割问题 构造得到最大流建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本
13、理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材最大最小定理 对比以上两个定理 定义3.1 n最大最小定理是一类描述同一个对象上的一 个最大化问题的解和一个最小化问题的解之间 的关系的定理。建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材最大最小定理 共同点 n考察的两个最优化问题互为对偶问题 n证明的过程 n最大化问题M的任何一个解m的值都不超过最小化 问题N的任何一个解n的值 n可以找到M的一个解p和N的一个解q，且它们的值 相等 np和q分别为各自问题的一个最优解 简洁的最优性证明建筑面积计算规
14、范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材总结Knig定理最大流最小割定理最大最小定理最大匹配最小覆盖最大流最小割模型转化最大最小完全矛盾互相转化注意总结、积累勇于探索建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材参考文献I.Introduction to Graph Theory, Second Edition by Douglas B. West II. Network Flows: Theory, Algorithms and Appl
15、ications by Ravindra K. Ahuja, Thomas L. Magnanti, and James B. Orlin III. Introductory Combinatorics, Third Edition by Richard A. Brualdi IV. 运筹学教程（第三版） 胡运权 郭耀煌建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材谢谢大家，欢迎提问！建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材更
16、多的例子 二部图中 n最大独立集的大小等于最小边覆盖数 n顶点的最大度数等于最小边染色数 3正则图中n点联通度等于边联通度 建筑面积计算规范解决问题方法和途径客户服务培训手册教学讲义激励基本理论江山四季青商贸城策划招商及后期商业运营方案精益生产培训教材如何构造最大流？ 我们用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
