浅析最大最小定理在信息学竞赛中的应用.ppt

更多的例子二部图中最大独立集的大小等于最小边覆盖数顶点的最大度数等于最小边染色数3正则图中点联通度等于边联通度……第30页，共42页，星期日，2025年，2月5日浅析最大最小定理在信息学竞赛中的应用第1页，共42页，星期日，2025年，2月5日引入我们在信息学竞赛中经常会遇到一些涉及一个最大化问题和一个最小化问题的定理怎样利用这些定理帮助我们解题呢？K?nig定理最大流—最小割定理第2页，共42页，星期日，2025年，2月5日K?nig定理主要内容在任何一个二部图G中，最大匹配数r(G)等于最小覆盖数c(G)第3页，共42页，星期日，2025年，2月5日K?nig定理证明最大匹配数不超过最小覆盖数任取一个最小覆盖Q，一定可以构造出一个与之大小相等的匹配Mr(G)≤c(G)r(G)=c(G)c(G)≤|Q|=|M|≤r(G)?c(G)≤r(G)第4页，共42页，星期日，2025年，2月5日K?nig定理应用二部图最小覆盖和最大匹配的互相转化[例一]MuddyFields第5页，共42页，星期日，2025年，2月5日最大流—最小割定理近年来，网络流尤其是最大流问题越来越多的出现在各类信息学竞赛当中最大流—最小割定理是整个最大流问题的基础与核心，其主要内容是：最大流的流量不超过最小割的容量存在一个流x和一个割c，且x的流量等于c的容量第6页，共42页，星期日，2025年，2月5日[例二]MovingtheHay一个牧场由R*C个格子组成牧场内有N条干草运输通道，每条连接两个水平或垂直相邻的方格，最大运输量为Li(1,1)内有很多干草，FarmerJohn希望将最多的干草运送到(R,C)内求最大运输量第7页，共42页，星期日，2025年，2月5日[例二]MovingtheHay一个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)第8页，共42页，星期日，2025年，2月5日分析直接求最大流以每个方格为点，每条通道为边，边的容量就是它的最大运输量从(1,1)到(R,C)的最大运输量就是将这两个方格对应的点分别作为流网络中的源和汇求出的最大流量效率？？？点数最大40000，边数最大80000！TimeLimitExceeded!!!第9页，共42页，星期日，2025年，2月5日分析效率低下的原因没有利用题目的特点，直接套用经典算法特点题目中给出的是一个平面图图中的一个点为源点s，另外一个点为汇点t，且s和t都在图中的无界面的边界上第10页，共42页，星期日，2025年，2月5日分析452316f1f2f3f4第11页，共42页，星期日，2025年，2月5日分析效率低下的原因没有利用题目的特点，直接套用经典算法特点题目中给出的是一个平面图图中的一个点为源点s，另外一个点为汇点t，且s和t都在图中的无界面的边界上我们称这样的平面图为s-t平面图第12页，共42页，星期日，2025年，2月5日平面图的性质平面图性质（欧拉公式）如果一个连通的平面图有n个点，m条边和f个面，那么f=m-n+2每个平面图G都有一个与其对偶的平面图G*G*中的每个点对应G中的一个面第13页，共42页，星期日，2025年，2月5日对偶图举例4523161*2*3*4*第14页，共42页，星期日，2025年，2月5日平面图的性质平面图性质（欧拉公式）如果一个连通的平面图有n个点，m条边和f个面，那么f=m-n+2每个平面图G都有一个与其对偶的平面图G*G*中的每个点对应G中的一个面对于G中的每条边ee属于两个面f1、f2，加入边(f1*，f2*)第15页，共42页，星期日，2025年，2月5日对偶图举例4523161*2*3*4*第16页，共42页，星期日，2025年，2月5日平面图的性质平面图性质（欧拉公式）如果一个连通的平面图有n个点，m条边和f个面，那么f=m-n+2每个平面图G都有一个与其对偶的平面图G*G*中的每个点对应G中的一个面对于G中的每条边ee属于两个面f1、f2，加入边(f1*，f2*)e只属于一个面f，加入回边(f*，