《最大最小定理(平面图最小割 对偶图)周冬》由会员分享，可在线阅读，更多相关《最大最小定理(平面图最小割 对偶图)周冬（42页珍藏版）》请在金锄头文库上搜索。
1、雨极相通一一浅析最大最小定理在信息学竞赛芜湖一中周冬maX_h的应引八s我们在信息学竞赛中经常会遇到一些涉及一个最大化问题和一个最小化问题的定理。怎样利用这些定理帮助我们解题呢?K6nig宝理。主要内容目在任何一个二部图G中,最大匹配数o(G)等于最小覆盖数c(G)K6nig宝理s证明里最大匹配数不超过最小覆盖数里任取一个最小覆盖Q,一定可以构造出一个与之大小相等的匹配Mp(G)=c(G)G)=c(Gc(G)sIQ|=IM|sp(G)夕c(G)p(G)p(“K6nig宏里二部图最小覆盖和最大例一Muddy,Fields理匹配的互相转化最大流一最小割定理近年来,网络流尤其越多的出现在各类信息学竞
2、赛当中最大流一最小割定理是整个最大流问题是最大流问的基础与核心,其3主要内容是:1,最大流的荚量不超迈最小暨的容量2.存在一个流x和一个割c,容量题越来且x的流量等于c的休二MovingtheHays一个牧场由RA+XC个格子组成。牧场内有N条干草运输通道,每条连接两个水平或垂直相邻的方格,最大运输量为L(1,1)内有很多干草,FarmerJohn希望将最多的干草运送到(R,C)内。求最大运输量例二MovingtheHay*一个R=C=3的例子,最大运输量为7(L)(L2)(3)E5.5k|eppko3世】(3,1)(3,2)OO“OvzxC716s数据规模:R,C200分析s直接求最大流重以每个方格为点,每条通道为边,边的容量就是它的最大运输量国从1,1)到(R,C)的最大运输量就是将这两个方格对应的点分别作为流网络中的源和汇求出的最大流量。效率?9目点数最大40000,边数最大8B8QQ仪Wtevcm、se。)分析。效率低下的原臣里没有利用题目的特点,直接套用经典算法“特点重题目中给出的是一个平面图里图中的一个点为源点s口古外一个点为汇点t,且s和t都在图中的无界面的边界上
