《国家集训队2007论文集7胡伯涛《最小割模型.pdf》由会员分享，可在线阅读，更多相关《国家集训队2007论文集7胡伯涛《最小割模型.pdf（45页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 第 1 页 共 45 页 最小割模型在信息学竞赛中的应用最小割模型在信息学竞赛中的应用 Applications of Minimum Cut Model in Informatics 胡伯涛胡伯涛 Amber ADN.cn 福州第一中学福州第一中学 Fuzhou No.1 Middle School hupo001atgmaildotcom ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 第 2 页 共 45 页 摘要摘要 本文对最小割模型的定义和性质，以及其相关扩展知识进
2、行了研究。其中着重对最小割模型在以下四个方面的应用展开研究：1.基于定义的直接应用；2.最大权闭合图；3.最大密度子图；4.二分图的最小点权覆盖集和最大点权独立集。展现与剖析了最小割模型应用的巧妙构图方法和独特思维方式，并对这一类应用的通用方法与技巧给予总结。关键字关键字 网络流，最大流，最小割，最大权闭合图，最大密度子图，二分图最小点权覆盖集，二分图最大点权独立集 Abstract The purpose of the thesis is to research the definition,properties,and correlated extended knowledge of mi
3、nimum cut model.The thesis sets focus on researching that is in four aspects:1.the application based on the minimum cut model;2.the maximum weight closure of a graph;3.the maximum density sub graph;4.the minimum weight vertex covering set and the maximum weight vertex independent set in the bipartit
4、e graph.It shows and analyzes the construction methods and thinking modes of the minimum cut model.Finally,it summarizes the methods and skills in the applications of the minimum cut model.Key Words Network Flow,Maximum Flow,Minimum Cut,Maximum Weight Closure of a Graph,Finding a Maximum Density Sub
5、 Graph,Minimum Weight Vertex Covering Set and Maximum Weight Vertex Independent Set,Bipartite Graph 目录目录 0.前言 Preface.4 1.预备知识 Preliminaries.4 1.1.网络与流 Network and Flow.4 1.2.残留网络与增广路径 Residual Network and Augmenting Path.5 1.3.最大流与最小割 Maximum Flow and Minimum Cut.6 1.4.最小割的算法 Algorithm for Minimum
6、Cut.8 1.5.最大流的算法 Algorithm for Maximum Flow.9 1.6.分数规划 Fractional Programming.10 2.基于定义的直接应用 Applications based on the Definition.13 2.1.引入 Introduction.13 2.2.应用 Application.13 2.2.1.网络战争 Network Wars.13 2.2.2.最优标号 Optimal Marks.14 3.最大权闭合图 Maximum Weight Closure of a Graph.16 ADN.cnLibraryThesis 最
7、小割模型在信息学竞赛中的应用 Amber 第 3 页 共 45 页 3.1.引入 Introduction.16 3.2.构造 Construction of Algorithm.17 3.3.证明 Proof.17 3.4.应用 Application.19 3.4.1.最大获利 Profit.19 4.最大密度子图 Finding a Maximum Density Subgraph.20 4.1.引入 Introduction.20 4.2.主算法 Main Algorithm.21 4.3.初步算法 Simple Algorithm.22 4.4.改进算法 Improved Algor
8、ithm.23 4.5.改进算法的证明 Proof of Improved Algorithm.25 4.6.向带边权图的推广 Generalization to Edge Weighted Graphs.27 4.7.向点边均带权的图的推广 Generalization to Both Node and Edge Weighted Graphs 27 4.8.应用 Application.29 4.8.1.生活的艰辛 Hard Life.29 4.8.2.最大获利 Profit.29 5.二分图的最小点权覆盖集与最大点权独立集 Minimum Weight Vertex Covering S
9、et and Maximum Weight Vertex Independent Set in a Bipartite Graph.30 5.1.引入 Introduction.30 5.2.二分图的最小点权覆盖集算法 Algorithm for MinWVCS in a Bipartite Graph.31 5.3.二分图的最大点权独立集算法 Algorithm for MaxWVIS in a Bipartite Graph.32 5.4.应用 Application.33 5.4.1.有向图破坏 Destroying the Graph.34 5.4.2.王者之剑 Exca.35 6.总
10、结 Summary.38 6.1.转化过程的模式 Transforming Pattern.38 6.2.割的性质 Property of Cut.39 6.3.技巧 Skills.39 7.感谢 Acknowledgments.40 8.附录 Appendix.40 8.1.涉及题目列表 Problem List.40 8.2.基本图论定义与术语 Basic Definition and Glossary in Graph Theory.41 8.2.1.图与网络 Graph and Network.41 8.2.2.图的术语 Glossary of Graph.41 8.3.怎样解题表 H
11、ow to Solve it.42 9.参考文献 References.44 ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 0.前言前言 Preface 最小割是最大流的对偶问题。但在实际建模过程中，它不如最大流来的直观，模型也往往隐蔽得很深，不容易找到构图方法。本文着重研究最小割模型的实际应用，展示了最小割模型应用的巧妙构图方法与独特思维方式，并对于这一类模型建立的通用方法与技巧给予总结。第 1 节，介绍一些基本的网络流与分数规划的知识，为后文的论述提供依据。特别是分数规划部分，对参考文献LiuH04上的 0-1 分数规划进行了拓展，拓展到一般的分数规划
12、形式。第 2 节，以 2 个较简单例题的分析，展示基于定义直接应用最小割的方法与技巧。第 3 节，介绍最大权闭合图模型，以及用最小割模型来解决的方法。关于构图的证明是本节重点。第 4 节，介绍最大密度子图模型。先将其转化为最大权闭合图模型解决，又重新提出了一个利用最小割模型解决的新方法，更好地解决了该问题。并向带点权的图和点边均带权的图进行了拓展，很好地解决了最大获利最大获利(profit)问题。本节是本文的亮点，也是研究的重点。本节是本文的亮点，也是研究的重点。第 5 节，介绍二分图的最小点权覆盖集与最大点权独立集，以及利用最小割模型解决的方法。构造比较简单，重点是两个例题的化归过程。第 6
13、 节，总结利用最小割模型解决问题的一些基本方法与思维过程。本文定位是重在思路的分析，总结利用最小割模型解决问题通用的思维方向，而不是纯粹的算法介绍，所以本文过半的篇幅用来描述思维转化的过程。具体的分析基本上是以波利亚的怎样解题表中所描述的步骤作为主线。在每个分析后，都会有简洁凝练的证明过程来总结分析的思维过程。对于那些急于得到结论的读者，直接阅读证明过程即可，但是请记住，分析过程才是本文重点分析过程才是本文重点。1.预备知识预备知识 Preliminaries 1.1.网络与流网络与流 Network and Flow,u vE(,)GV E=流网络流网络（flow network）（简称网络
14、）是一个有向图，其中每条边均有一非负容量，规定：若第 4 页 共 45 页(,)0c u v,u vE，则(,)0c u v=。网络中有两个特殊点：源与汇。流网络的流流（flow）是一个实值函数stGVVRf：，且满足下列三个性质：出自参考文献Pol57，数学教育家 G.Polya 的 How to solve it。详见附录 8.3 节，怎样解题表。ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 第 5 页 共 45 页(1)容量限制容量限制：对于，要求,u vV(,)(,)f u vc u v。(2)反对称性反对称性：对于，要求,u vV(,)(,)f
15、u vf v u=。(,)0v Vf u v=(3)流守恒性流守恒性：对于，要求,uVs t。称(,)f u v为从u到的流。流vf的值定义为：|(,)v Vff s v=(1.1)一个网络中的最大流最大流（maximum flow）就是指该网络中流值最大的流。为了方便起见，本文在函数的求和上，采用隐含求和记号隐含求和记号：其中任何一个自变量可以是一个点集，对该集合的所有元素作为自变量的情况求和。例如：(,)(,)u X v Yf X Yf u v=下面不加证明地给出一个简单的引理，它给出了关于流的一些恒等式，这对后文的推导和计算流的公式很重要。f(,)GV E=引理引理1.1（流的基本运算）
16、设是流网络中的一个流。那么下列等式成立：(1)对于XV，有(,)0f X X=,X YV(,)(,)f X Yf Y X=(2)对于，有XY=,X Y ZV，有)(,)(,)(,f XY Zf X Zf Y Z=+(3)对于，其中 1.2.残留网络与增广路径残留网络与增广路径 Residual Network and Augmenting Path 残留网络，增广路径与割这三个概念是构成重要的最大流最小割定理（定理 1.6）的基本概念，该定理巧妙运用网络的最小割来描述最大流的值。对于流网络，设流(,)GV E=f为中的流。残留网络残留网络(residual network)直观上讲是由还可以容
17、纳更多的流的边所组成。对于中的每条边GG,u vE，可以定义残留容量残留容量(residual capacity)表示在不超过容量限制的条件下，可以通过的额外的网络流量：(,)(,)(,)fcu vc u vf u v=(1.2)下面是残留网络的形式化定义：给定网络(,)GV E=f(,)ffGV E=与流，残留网络为，ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 其中边集 (,)|(,)0ffEu vVV cu v=fc事实上，残留网络也是一个流网络，容量由给出。下面的引理，给出了残留网络与原网络的关系，也为提出增广路径提供了前提。f(,)GV E=中的
18、一个流，f引理引理1.2（残留网络与原网络的关系）设是流网络是其残留网络第 6 页 共 45 页 fG的一个流，则ff+仍是网络的一个流。G 该定理的证明需从网络流定义的三个性质分别来证明，这里从略。增广路径增广路径(augmenting path)p为残留网络fG上源到汇t的一条简单路径。该路径的残留容量，为可以沿该路径增加的最多额外流量：s()min(,)|,ffcpcu vu vp=其值严格大于 0。pf引理引理1.3（增广路径可增广性）定义流为 (),(,)(),0fpfcpu vpfu vcpv upelse=给定网络与流(,)GV E=f，则pff+仍是网络的一个流。该定理的证明思
19、路仍是从网络流定义的三个性质出发，证明GpffG是残留网络上的一个流，再根据引理 1.2，便可得证。这里从略。1.3.最大流与最小割最大流与最小割 Maximum Flow and Minimum Cut 下面引入本文讨论的核心割。流网络的割割（cut）将点集划分为和（VSTVS=T(,)GV E=,S T）两个部分，使得源且汇。符号代表一个边集合sStT,|,u vu vE uS vT,S T。穿过割的净流净流（net flow）定义为,S T(,)f S T，割的容量容量（capacity）定义为，一般记为。一个网络的最小割最小割（minimum cut）也就是该网络中容量最小的割。,S
20、T(,)c S T,c S TADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber s5423t 图 1.1 最小割的例子 图 1.1 给出了一个最小割的例子，红线下的点组成，其他点组成T，则割S,1,2,3,4,5,6S T=,2,3,4,5T S=第 7 页 共 45 页，而割。注意，边2,34,5，的流值算在净流(,)f S T内（是个负值），但它们的容量并没有算在割,的容量内。S T(,)GV E=f,S T引理引理1.4（割与流的关系）在一个流网络中，设其任意一个流为，且为一个割。则通过割的净流为G(,)|f S Tf=。证明证明：(1.1)(3)(1.
21、1)(1)(1.1)(3)(,)(,)(,)(,)(,)(,)(,)|(,)0f S Tf S Vf S Sf S Vf s Vf Ss Vf s Vff Ss V=+=根据引理根据引理根据引理根据流守恒性，推论推论1.5（对偶问题的性质）在一个流网络(,)GV E=f中，设其任意一个流为，任意一个割为，必有,S T|,fc S T。证明证明：由引理 1.3 和容量限制，有|(,)(,)(,),u S v Tu S v Tff S Tf u vc u vc S T=推论 1.5 反映了网络的最大流必定不超过此网络最小割的容量。实际上，最小割问题是最大流的对偶问题对偶问题（duality），而对
22、偶问题都具有类似推论 1.5 的性质。定理定理1.6（最大流最小割定理）如果f是具有源和汇 的流网络st(,)GV E=中的一个流，则下列条件是等价的：(1)f是的一个最大流(2)残留网络GfG不包含增广路径 关于流与割的对偶关系，在参考文献AMO93中有详细介绍。ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 第 8 页 共 45 页(3)对的某个割,，有|GS T,fc S T=证明证明：(1)(2)：反证法。设f是的一个最大流，但残留网络GfG包含一条增广路径。由引理 1.3，流的和p仍为G的一个流，其值严格大于|pff+f|。这与条件矛盾。s(2)(
23、3)：残留网络fG不包含增广路径，即fG中不存在到 的路径。构造性的令：t,s vfSvVpG=，其中,s vfpG表示在fG中存在一条到的通路；且。则划分是一个割：，由于svTVS=,S TsSfG中不存在到 的路径，所以stSt。对于，有,uSvT (,)(,)f u vc u v=，否则,fu vE，就属于集合。由引理 1.4，vS|(,),ff S Tc S T=。(3)(1)：由推论 1.5 可知，对于所有割，都有,S T|,fc S T，因此条件|,fc S T=说明f是一个最大流。1.4.最小割的算法最小割的算法 Algorithm for Minimum Cut 由于最大流最小
24、割定理(定理 1.6)中，(1)与(3)等价，即最大流的流值等于最小割容量。并且在最大流最小割定理的(2)(3)部分的证明中，构造性地得到了一个一一对应的割。其中点集表示在,S TSfG中与连通的点集；sTVS=。所以在问题的实现上分两步，先求得最大流（在1.5 节有简要介绍）；再在得到最大流f后的残留网络fG中，从开始深度优先遍历（DFS），所有被遍历到的点，即构成点集注意，虽然最小割中的边都是满流边，但满流边不一定都是最小割中的边满流边不一定都是最小割中的边。在某些特殊图中，很多初学者容易犯错，认为不用 DFS，就可以直接得出割。下面举一个二分图的例子。sS。,S TADN.cnLibra
25、ryThesis 最小割模型在信息学竞赛中的应用 Amber s5413t21/?1/?1/13/32/31/11/11/?1/?(a)s5413t21/?1/?1/13/32/31/11/11/?1/?(b)图 1.2 求最小割的二分图例子 X图 1.2(a)给出了一个基于二分图构造的流网络。由于从部到Y部都是容量均为正无限的边，都不可能是最小割中的边，有人便会错误地认为与源或汇关联的满流边便组成了最小割（图 1.2(a)的红色边）。然而实际上，在该网络的残留网络中，结点 2 与 3 应该与源是连通的（图 1.2(b)的蓝色路径），所以最小割应该是图 1.2(b)中的红色边。s1.5.最大流
26、的算法最大流的算法 Algorithm for Maximum Flow 由于本文只研究最小割的应用，对为得到最小割而具体使用的最大流算法本身不进行深入的讨论。下面列出一些常用的适用于一般图一般图的最大流算法。有兴趣的读者可以在参考文献AMO93，CLRS01中找到相关的知识，此外，参考文献ZCW03中有对最大流算法历史的简要回顾。nV=mE=给出流网络。简记(,)GV E=，。设U为最大的边容量值。后文不再涉及具体的最大流复杂度，通常以，On或On代替。(MaxFlow()OG第 9 页 共 45 页(MaxFlow(,)(MaxFlow()m 算法名称 复杂度 概要 增广路方法 Augme
27、nting path method(Ford Fulkerson method)一般增广路算法 Labeling algorithm 在残留网络中，每次任意找一条增广路径增广。()O nmU 容量缩放增广路算法 Capacity scaling algorithm(log)O nmU在残留网络中，每次找一条有最大可增广容量和最大可增广容量和的增广路径增广，即残留网络中源到汇的最长路。最短增广路算法 Shortest augmenting path algorithm(Edmonds Karp algorithm)2()O nm 在残留网络中，每次找一条含结点数最少含结点数最少的增广路增广，即残
28、留网络中源到汇的BFS 路径。ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 第 10 页 共 45 页 2()O n m在 Edmonds Karp 的基础上改造。在每次BFS 找增广路时，记录每个点的距离标号。在距离标号的所构成的最短路图上，不断地 DFS 找增广路。即一次标号多次增广一次标号多次增广，以提高速度。连续最短增广路算法Successive shortest augmenting path algorithm(Dinic algorithm)预流推进方法 Preflow-push method 一般预流推进算法 维护一个预流预流，不断地对活跃
29、结点执行push操作或relabel操作来调整这个预流，直到不能操作。2()O n mGeneric preflow-push algorithm 先进先出预流推进算法 3()O n以先进先出队列先进先出队列维护活跃结点。FIFO preflow-push algorithm 最高标号预流推进算法 Highest-label preflow-push algorithm(Relabel-to-Front algorithm)2()O nm每次检查具有最高标号最高标号的活跃结点。增广路方法的复杂度是通过估计增广次数的上界得到的。对于实际应用中的网络，增广次数往往很少，所以使用范围还是很广的，实用
30、性强。预流推进方法看似比增广路方法在复杂度上快很多，然而实际上，预流推进方法的复杂度的上界是比较紧的。对于一些稀疏图，预流推进方法的实际效果往往不如增广路方法。1.6.分数规划分数规划 Fractional Programming 先给出分数规划分数规划（fractional programming）的一般形式：()Minimize()()()afSb=xxxx .,()0stSb xx 其中，解向量在解空间内，与都是连续的实值函数连续的实值函数。解决分数规划问题的一般方法是分析其对偶问题，但更加实用的方法是对其进行参数搜索参数搜索(parametric search)，即对答案进行猜测，再验
31、证该猜测值的最优性，将优化问题转化为判定性问题或其他的优化问题。由于分数规划模型的特殊性，使得能够构造另外一个由猜测值Sx()ax()bx作为自变量的相关问题，且该问题的解满足一定的单调性，或其他的可以减小参数搜索范围的性质，从而逼近逼近答案。假设为该规划的最优解，有：*()f=x 该连续最短增广路算法与求最小费用流的连续最短增广路算法同名。比如 Dinkelbach 算法，每次直接把上次子问题的解向量代入原问题的表达式，算出下一个迭代式的猜测值。详见参考文献Dink67，MSS92。ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber*()()()()()0()
32、(afbbaab=xxxxxxx )()g：由上面的形式构造一个新函数()min()()Sga=xxbx (1.3)()g本身的性质。这个新函数是一个非分式的规划。先来挖掘函数12()()gg第 11 页 共 45 页 性质1.7（单调性）()g是一个严格递减函数，即对于12=xxxxxxxxxx 最后一步表示，1()g上最小解代入1x2()g后，不一定还是最小解，甚至有更小解。有了单调性，就意味着可以采用二分搜索的方法逼近答案。但还不知道目标是什么，下面考察构造出的新函数与原目标函数的最优解关系。定理定理1.8（Dinkelbach定理）设*=()0g=为原规划的最优解，则当且仅当。证明证明
33、：(1)先证必要性：设为原规划的最优解，则。对于，都不会比优：*()0g=*()f=x*()0g=S x*x*()()()()0()()aaabbb=xxxxxx 然而可以取到这个下限。*x*()()()0()aabb=xxxx*=出自参考文献Dink67。ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber*()g第 12 页 共 45 页 故的最小值由确定，*x*()0g=。*()0g=(2)再证充分性：若存在一个解，使得x()f=x()0g=，则为原规划的最优解。反证法。反设存在一个解(f)=x()f=x更优的解。，它是比()()()()0abab=xxxx
34、 这时x应该使得()0g()0g=，这与矛盾。由性质 1.7 与定理 1.8，很容易得到下面的推论。推论推论1.9 设*为该规划的最优解，则 *()0()0()0ggg=b x 并且对解向量可能还有其他的组合限制。它的应用范围很广，经典例题是最优比率生成树最优比率生成树（the optimum ratio spanning tree）。x 0-1 分数规划的相关知识，在参考文献MSS92中有详细介绍。详见参考文献LiuH04，303-304 页。ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 2.基于定义的直接应用基于定义的直接应用 Applications
35、 based on the Definition 2.1.引入引入 Introduction 在这类基于最小割定义的直接应用中，最小割模型的建立往往比较简单，但常常又和一些新颖的知识融合在一起。这样一来便不能直接地套用模型，而是需要使用一些知识与技巧，逐步将问题化归到最小割模型，使其成为某些主算法的子过程。这类应用比较冗杂，使得本节并没有太多通用的理论性介绍，一些特别的知识与技巧在具体的题目分析中才能得以体现。2.2.应用应用 Application 2.2.1.网络战争网络战争 Network Wars 描述描述 Description 给出一个带权无向图，每条边e有一个权。求将点和点t分开
36、的一个边割集，使得该割集的平均边权最小，即最小化：sew(,)GV E=C|ee CwC(2.1)解答解答 Solution w(1,1,.,1)=c先尝试着用更一般的形式重新叙述本问题。设向量表示边的权值，令向量表示选边的代价，于是原问题等价为：Minimize()1eee Eee Ew xfx=w xxc x 其中，表示一个解向量，即对于每条边都有选与不选两种决策，并且选出的边集组成一个边割集。形式化地，若0,1ex xeC第 13 页 共 45 页 st1ex=，则；0ex=，则。联系已有的知识，这是一个 0-1 分数规划。在1.6 节eC中已经给出了这类规划的普遍转化方法：构造一个新函
37、数 题目来源：Zhejiang University Online Judge-Andrew Stankevichs Contest#8-2676 Network Wars ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber()min()g=xwcx 第 14 页 共 45 页 即对每条边，进行重赋权：eE eeeewwcw=()g。便是在这个重新赋权的图上，求一个最小容量的边割集。请注意一些细节：若st0ew，又由于目标函数是加和取最小的操作，则该边必然是在边割集内。对于剩下的所有的边，直接利用最小割模型求出0ew st割即可。设为原规划的最优解，由推论 1.
38、9 知：*()f=x*()0()0()0ggg=0)(,)c u v=v,Ns vE，容量为；增加连接原图每个负权点(,)vc s vw=(vw0)到汇t的有向边=132453657st?图 3.2 闭合图构图的例子 图 3.2 是将图 3.1 转化后的网络：从源向两个正权点 1,3 连边，从两个负权点 2,5 向汇连边。3.3.证明证明 Proof 定义：若一个stst割满足割中的每条边只都与源或汇 关联，称该割为简单割简单割（simple cut）。根据该定义，网络的简单割是不含原图的边集stNGE中的任何边的。引理引理3.1 在本问题的网络中，最小割是简单割。证明证明：网络中边分两类：与
39、源或汇关联的边，容量为有限值；不与源或汇关联的边，即原来边集NNE中的边，容量均为正无限。所有与源或汇关联的边组成的割集的容量是有限的，为所有点权的绝对值和。最小割容量也至多为该绝对值和。故最小割不可能取任何容量为正无限的边，即最小割是简单割。ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 第 18 页 共 45 页 T先规定一些符号。设简单割,将网络的点集划分为点集及其补集，满足，t。设闭合图为，它在V中的补集为NSNVS T1V()NTVS=sST1V或。记为中点权为正的点集，为中点权为负的点集。同样地，可以定义与，2V21()VVV=VV1V+1V2V
40、+V+V与。下面的工作就是将简单割与闭合图一一对应起来，以便利用最小割模型求解。引理引理3.2（可行性）网络的简单割与图的闭合图方案存在一个一一对应关系：S。证明证明：(1)闭合图对应简单割：即，2VNG1V,S T1 Vs=1 TVt=1 SVs=，求证为简单割。反证法。反设存在,S T1 vTtV=,u vE1 uSsV=，其中，使得,S T含不与源或汇关联的边。则闭合图有一个后继不在闭合图内，矛盾。(2)简单割对应闭合图：即证1V1 VSs=1uV 是闭合图。对于闭合图中，考察任意一条由引出的出边1 vTtV=u,u vEE，由于简单割不含,S T中的任何边，故，即，符合闭合图的定义。推
41、论推论3.3（对应关系的数量化）在引理 3.2 的一一对应关系下，有：1vV21,()vvv Vv Vc S Tww+=+(3.1)证明证明：割按照与源或汇的关联情况，可以分为 3 部分：2由于割是简单割，故,S T211,S Ts VVtV V=12,V V=,S T。又由于源只与正权点有边，故s22,s Vs V+=。同样的汇 只与负权点有边，故。综上，因此式(3.1)成立。t11,VtVt=21,S Ts VVt+=ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 定理定理3.4（最优性）当网络的取到最小割时，其对应的图G的闭合图将达到最大权。N证明证明
42、：按照定义，闭合图的权和为正权点的权的绝对值和减去负权点的权的绝对值和：第 19 页 共 45 页 v111()()vv Vv Vw Vww+=(3.2)将式(3.2)与推论 3.3 的式(3.1)相加，得到：1121121(),()()vvvv Vv Vv Vv Vvvv Vv Vvv Vw Vc S Twwwwwww+=+=+=v 整理得：1(),vv Vw Vwc S T+=(3.3)观察式(3.3)，目标是最大化，而正权点的总权和vv Vw+1()w V为定值，故最小化简单割的容量，便可得到最大的。根据引理 3.1，最小割为简单割。所以最小割是最小的简单割，故答案为网络的最小割所对应的
43、闭合图。算法复杂度便是求最小割的复杂度：。3.4.应用应用 Application 3.4.1.最大获利最大获利 Profit11 描述描述 Description ADN 公司得到了一共个可以作为通讯信号中转站的地址。由于这些地址的地理位置差异，在不同的地方建造通讯中转站所需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第 个通讯中转站需要成本1()w V,c S TN(MaxFlow()ONnipi。另外公司调查得出了所有期望中的用户群，一共个。第 个用户群的用户会使用中转站和中转站进行通讯，公司获益。ADN公司可以有选择地建立一些中转站（其成本之和为总成本），为一些用
44、户提供服务并获得收益（收益之和为总收益）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利=总收益 总成本）miaibici 11 题目来源：NOI 2006 Day 2 最大获利(Profit)ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 解答解答 Solution 第 20 页 共 45 页 im 首先分析题目中的决策因素。在满足了第i个用户群后，便可以得到收益，然而满足第个用户群需要有必要条件必要条件：建立中转站和中转站，同时要花去相应费用。留心这个所谓的必要条件，便可联想到闭合图的性质。分析后发现，本题就是最大权闭合图的一个特例。把它
45、抽象成这样一个有向图模型：每个用户群i作为一个结点分别向相应的中转站和中转站连有向边。事实上，这是一个二分图上的特例。求这个图的最大权闭合图，便可解决本题。复杂度为。iciaibiaib(MaxFlow(,)Onm n+而4.7 节给出的结果，可以使本题在仅O(MaxFlow(,)n nm+的时间内解决。这也是本文比较重要的突破之一。参见应用 4.8.2。4.最大密度子图最大密度子图 Finding a Maximum Density Subgraph 4.1.引入引入 Introduction EV定义一个无向图的密度密度(density)为该图的边数D(,)GV E=与该图的点数的比值|E
46、DV=。给出一个无向图，其具有最大密度的子图(,)GV E=(,)GVE=称为最大密度子图最大密度子图（maximum density subgraph），即最大化|EDV=。nV=mE=。简记，126345 图 4.1 最大密度子图的例子 举例，在图 4.1 中，给出了一幅个点的图，其中在虚线内的点与边组成最大密度子图，6ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 54。红边组成子图的边集，密度为4.2.主算法主算法 Main Algorithm 先尝试着更形式化地重新叙述本模型：Maximize()ee Evv VxDfx=x 第 21 页 共 45
47、 页 其中，表示对于每个点或每条边是否在子图,0,vex x 1(,)GVE=中，即，。并且对于1vvVx=eeEx=1(,)eu vE=，必有。,u vV1.6 节联系的分数规划，以上规划就是一个 0-1 分数规划的模型。根据分数规划一般步骤，应是进行二分查找答案，对于一个答案的猜测值g，构造一个新函数()max1eve Ev Vh gxg x=x 设为原规划的最优解，由推论 1.9 知：于是主算法便是对最优解的二分查找，每次查找得到一个猜测值*()Df=x*()0()0()0h ggDh ggDh ggD=*Dg，以求解来进行判定，从而缩小查找范围。设二分查找次数为，解决的复杂度为，则该算
48、法复杂度为：。先确定二分查找的范围。由于密度不超过()h gk()h gSolve()h g(Solve()O kh g1m1n，且不小于，便将它们作为二分查找的上下界。接下来，确定二分查找的精度。引理引理4.1 无向图中，任意两个具有不同密度的子图，它们的密度差不小于21nG1G2G。证明证明：不妨设的密度大于的密度。设的点数分别为，边数分别为，。则有：1G2G1G，2G1n，2n1m2m121221212121211mmm nm nnnn nn nn=ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber 以上引理给出了不同密度的子图的间距，容易有如下推论。推论
49、推论4.2 对于无向图G中，有一个密度为的子图，且在无向图G中不存在一个密度超过GD21Dn+的子图，则为最大密度子图。G 于是，根据推论 4.2，则二分查找的次数为()()4211loglog(log)1mnkOOnOnn=则总算法复杂度为：。(logSolve()Onh g第 22 页 共 45 页 问题便集中在如何求出，下面分别使用了两种方法来求解()h g()h g。4.3.初步算法初步算法 Simple Algorithm 假设已经给出了一个答案的猜测值，需求解：g()max1eve Ev Vh gxg x=x 更形象化的解释，便是选出一个的子图G(,)GVE=(,)eu vE=，并
50、且对于，必有，且最大化 ,u vVMaximize1|e Ev VgEg V=注意限制条件：对于，必有(,)eu vE=,u vV。就是说边的存在的前提前提或必要条件必要条件是与的存在。观察这个必要条件，具有第 3 节(,)u vuv论述的最大权闭合图的限制条件形式。可以把本模型中的边看成点，带上点权；把本模型中的点保留，带上点权；对于所有边，建立两条有向边eevg1,ev u,ev v(,)eu vE=，。此时，原图便转化为一个最大权闭合图的模型。更形式化地，由原图建立新图(,)DDDVE=(,)G V E：ADN.cnLibraryThesis 最小割模型在信息学竞赛中的应用 Amber|