算法合集之《浅析最大最小定理在信息学竞赛中的应用》课件

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