网络流最小割模型在信息学竞赛中的应用

[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber最小割模型在学竞赛中的应用ApplicationsofMinimumCutMinInformatics胡Amber[ADN.cn]福州第一中学FuzhouNo.1MiddleSchoolhupo001[at]gmail[dot]com第1页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber[摘要]本文对最小割模型的性质，以及其相关扩展知识进行了研究。其中着重对最小割模型在以下四个方面的应用展开研究：1.基于定义的直接应用；2.最大权闭合图；3.最大密度子图；4.二分图的最小点权覆盖集和最大点权集。展现与剖析了最小割模型应用的巧妙构图和独特思维方式，并对这一类应用的通用与技巧给予 总结 初级经济法重点总结下载党员个人总结TXt高中句型全总结.doc高中句型全总结.doc理论力学知识点总结pdf 。[关键字]网络流，最大流，最小割，最大权闭合图，最大密度子图，二分图最小点权覆盖集，二分图最大点权集[Abstract]Thepurposeofthethesisistoresearchthedefinition,properties,andcorrelatedextendedknowledgeofminimumcutm.Thethesissetsfocusonresearchingthatisinfouraspects:1.theapplicationbasedontheminimumcutm;2.theumweightclosureofagraph;3.theumdensitysubgraph;4.theminimumweightvertexcoveringsetandtheumweightvertexindependentsetinthebipartitegraph.Itshowsandanalyzestheconstructionmethodsandthinkingmodesoftheminimumcutm.Finally,itsummarizesthemethodsandskillsintheapplicationsoftheminimumcutm.[KeyWords]NetworkFlow,umFlow,MinimumCut,umWeightClosureofaGraph,FindingaumDensitySubGraph,MinimumWeightVertexCoveringSetandumWeightVertexIndependentSet,BipartiteGraph[目录]0.前言Preface................................................................................................................................41.预备知识Preliminaries...............................................................................................................41.1.网络与流NetworkandFlow...........................................................................................41.2.残留网络与增广路径ResidualNetworkandAugmentingPath....................................51.3.最大流与最小割umFlowandMinimumCut....................................................61.4.最小割的算法AlgorithmforMinimumCut...................................................................81.5.最大流的算法AlgorithmforumFlow................................................................91.6.分数规划FractionalProgram................................................................................102.基于定义的直接应用ApplicationsbasedontheDefinition....................................................132.1.引入Introduction...........................................................................................................132.2.应用Application............................................................................................................132.2.1.网络NetworkWars....................................................................................132.2.2.最优标号OptimalMarks..................................................................................143.最大权闭合图umWeightClosureofaGraph..............................................................16第2页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber3.1.引入Introduction...........................................................................................................163.2.构造ConstructionofAlgorithm....................................................................................173.3. 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 Proof......................................................................................................................173.4.应用Application............................................................................................................193.4.1.最大获利Profit..................................................................................................194.最大密度子图FindingaumDensitySubgraph............................................................204.1.引入Introduction...........................................................................................................204.2.主算法MainAlgorithm.................................................................................................214.3.初步算法SimpleAlgorithm..........................................................................................224.4.改进算法ImprovedAlgorithm......................................................................................234.5.改进算法的证明ProofofImprovedAlgorithm............................................................254.6.权图的推广GeneralizationtoEdgeWeightedGraphs.....................................274.7.均带权的图的推广GeneralizationtoBothNodeandEdgeWeightedGraphs274.8.应用Application............................................................................................................294.8.1.生活的艰辛HardLife.......................................................................................294.8.2.最大获利Profit..................................................................................................295.二分图的最小点权覆盖集与最大点权集MinimumWeightVertexCoveringSetandumWeightVertexIndependentSetinaBipartiteGraph.........................................................305.1.引入Introduction...........................................................................................................305.2.二分图的最小点权覆盖集算法AlgorithmforMinWVCSinaBipartiteGraph.........315.3.二分图的最大点权集算法AlgorithmforMaxWVISinaBipartiteGraph.........325.4.应用Application............................................................................................................335.4.1.有破坏DestroyingtheGraph....................................................................345.4.2.Exca...................................................................................................356.总结Summary...........................................................................................................................386.1.转化过程的模式TransforPattern.........................................................................386.2.割的性质PropertyofCut..............................................................................................396.3.技巧Skills.....................................................................................................................397.感谢Acknowledgments.............................................................................................................408.附录Appendix...........................................................................................................................408.1.涉及题目列表ProblemList..........................................................................................408.2.基本图论定义与术语BasicDefinitionandGlossaryinGraphTheory.......................418.2.1.图与网络GraphandNetwork...........................................................................418.2.2.图的术语GlossaryofGraph.............................................................................418.3.《怎样解题表》HowtoSolveit.................................................................................429.参考文献References.................................................................................................................44第3页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber0.前言Preface最小割是最大流的对偶问题。但在实际建模过程中，它不如最大流来的直观，模型也往往隐蔽得很深，不容易找到构图。本文着重研究最小割模型的实际应用，展示了最小割模型应用的巧妙构图与独特思维方式，并对于这一类模型建立的通用与技巧给予总结。第1节，一些基本的网络流与分数规划的知识，为后文的论述提供依据。特别是分数规划部分，对参考文献[LiuH04]上的0-1分数规划进行了拓展，拓展到的分数规划形式。第2节，以2个较简单例题的分析，展示基于定义直接应用最小割的与技巧。第3节，最大权闭合图模型，以及用最小割模型来解决的。关于构图的证明是本节重点。第4节，最大密度子图模型。先将其转化为最大权闭合图模型解决，又重新提出了一个利用最小割模型解决的新，更好地解决了该问题。并权的图和点带权的图进行了拓展，很好地解决了最大获利(profit)问题。本节是本文的亮点，也是研究的重点。第5节，二分图的最小点权覆盖集与最大点权集，以及利用最小割模型解决的。构造比较简单，重点是两个例题的化归过程。第6节，总结利用最小割模型解决问题的一些基本与思维过程。本文定位是重在思路的分析，总结利用最小割模型解决问题通用的思维方向，而不是纯粹的算法，所以本文过半的篇幅思维转化的过程。具体的分析基本上是以亚的《怎样解题表》①中所描述的步骤作为主线。在每个分析后，都会有简洁凝练的证明过程来总结分析的思维过程。对于那些急于得到结论的读者，直接阅读证明过程即可，但是请记住，分析过程才是本文重点。1.预备知识Preliminaries1.1.网络与流NetworkandFlow流网络（flownetwork）（网络）GVE=(,)是一个有，其中每条有一非负容量cuv(,)≥0，规定：若uv,∉E，则cuv(,)=0。网络中有两个特殊点：源s与汇t。流网络G的流（flow）是一个实值函数f：VV×→R，且满足下列三个性质：①出自参考文献[Pol57]，数学教育家G.Polya的Howtosolveit。详见附录8.3节，怎样解题表。第4页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber(1)容量限制：对于∀∈uv,V，要求f(,)uv≤cuv(,)。(2)称性：对于∀∈uv,V，要求f(,)uv=−f(,)vu。(3)流守恒性：对于∀∈uV−{,}st，要求∑fuv(,)=0。vV∈称f(,)uv为从u到v的流。流f的值定义为：||f=∑fsv(,)(1.1)vV∈一个网络中的最大流（umflow）就是指该网络中流值最大的流。为了方便起见，本文在函数的求和上，采用隐含求和记号：其中任何一个自变量可以是一个点集，对该集合的所有元素作为自变量的情况求和。例如：f(,)XY=∑∑fuv(,)uXvY∈∈下面不加证明地给出一个简单的引理，它给出了关于流的一些恒等式，这对后文的推导和计算流的公式很重要。引理1.1（流的基本运算）设f是流网络GVE=(,)中的一个流。那么下列等式成立：(1)对于∀⊆XV，有fXX(,)=0(2)对于∀⊆X,YV，有f(,)XY=−fYX(,)(3)对于∀⊆X,,YZV，其中XY∩=∅，有f(,)(,)(,XYZfXZfYZ∪=+)■1.2.残留网络与增广路径ResidualNetworkandAugmentingPath残留网络，增广路径与割这三个概念是重要的最大流最小割定理（定理1.6）的基本概念，该定理巧妙运用网络的最小割来描述最大流的值。对于流网络GVE=(,)，f为G中的流。残留网络(residualnetwork)直观上讲是由还可以容纳的流的组成。对于G中的每条边uv,∈E，可以定义残留容量(residualcapacity)表示在不超过容量限制的条件下，可以通过的额外的网络流量：cuvf(,)=cuv(,)−fuv(,)(1.2)下面是残留网络的形式化定义：给定网络GVE=(,)与流f，残留网络为GVEf=(,f)，第5页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber其中EuvVVcuvff=∈×>{(,)|(,)0}事实上，残留网络也是一个流网络，容量由cf给出。下面的引理，给出了残留网络与原网络的，也为提出增广路径提供了前提。引理1.2（残留网络与原网络的）设f是流网络GVE=(,)中的一个流，f'是其残留网络Gf的一个流，则f+f'仍是网络G的一个流。■该定理的证明需从网络流定义的三个性质分别来证明，这里从略。增广路径(augmentingpath)p为残留网络Gf上源s到汇t的一条简单路径。该路径的残留容量，为可以沿该路径增加的最多额外流量：cpff()=∈min{(,)|,cuvuvp}其值严格大于0。引理1.3（增广路径可增广性）定义流fp为⎧cpf()uvp,∈⎪fpf(,)uv=⎨−∈c(p)vu,p⎪⎩0else给定网络GVE=(,)与流f，则f+fp仍是网络G的一个流。■该定理的证明思路仍是从网络流定义的三个性质出发，证明fp是残留网络Gf上的一个流，再根据引理1.2，便可得证。这里从略。1.3.最大流与最小割umFlowandMinimumCut下面引入本文讨论的——割。流网络GVE=(,)的割（cut）[,ST]将点集V划分为S和T（TVS=−）两个部分，使得源sS∈且汇tT∈。符号[,ST]代表一个合{,uv|uv,∈Eu,∈∈Sv,T}。穿过割[,ST]的（netflow）定义为f(,ST)，割[,ST]的容量（capacity）定义为cST(,)，记为cST[,]。一个网络的最小割（minimumcut）也就是该网络中容量最小的割。第6页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber24st35图1.1最小割的例子图1.1给出了一个最小割的例子，红线下的点组成S，其他点组成T，则割[ST,]={1,2,3,4,5,6}，而割[TS,]={2,3,4,5}。注意，边2,3，4,5的流值算在f(,ST)内（是个负值），但它们的容量并没有算在割[,ST]的容量内。引理1.4（割与流的）在一个流网络GVE=(,)中，设其任意一个流为f，且[,ST]为G一个割。则通过割的为f(,ST)=|f|。证明：fST(,)=−fSV(,)fSS(,)根据引理(1.1)(3)=fSV(,)根据引理(1.1)(1)=+−fsV(,)fS({},)sV根据引理(1.1)(3)==fsV(,)|f|根据流守恒性，fS(−={},)sV0■推论1.5（对偶问题的性质）在一个流网络GVE=(,)中，设其任意一个流为f，任意一个割为[,ST]，必有||f≤cST[,]。证明：由引理1.3和容量限制，有||f==f(,)ST∑∑∑∑f(,)uv≤cuv(,)[,]=cSTuSvT∈∈uSvT∈∈■推论1.5反映了网络的最大流必定不超过此网络最小割的容量。实际上，最小割问题是最大流的对偶问题（duality）①，而对偶问题都具有类似推论1.5的性质。定理1.6（最大流最小割定理）如果f是具有源s和汇t的流网络GVE=(,)中的一个流，则下列条件是等价的：(1)f是G的一个最大流(2)残留网络Gf不包含增广路径①关于流与割的对偶，在参考文献[AMO93]中有详细。第7页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber(3)对G的某个割[,ST]，有||f=cST[,]证明：(1)⇒(2)：反证法。设f是G的一个最大流，但残留网络Gf包含一条增广路径p。由引理1.3，流的和f+fp仍为G的一个流，其值严格大于|f|。这与条件。(2)⇒(3)：残留网络Gf不包含增广路径，即Gf中不s到t的路径。构造性的令：SvVp=∈{}∃s,vf∈G，其中∃∈pGs,vf表示在Gf中一条s到v的通路；且TVS=−。则划分[,ST]是一个割：sS∈，由于Gf中不s到t的路径，所以tS∉。对于∀∈uSvT,∀∈，有f(,)uv=cuv(,)，否则∃∈uv,Ef，v就属于集合S。由引理1.4，||f==fST(,)[,cST]。(3)⇒(1)：由推论1.5可知，对于所有割[,ST]||[,f≤cST]，因此条件||[,]f=cST说明f是一个最大流。■1.4.最小割的算法AlgorithmforMinimumCut由于最大流最小割定理(定理1.6)中，(1)与(3)等价，即最大流的流值等于最小割容量。并且在最大流最小割定理的(2)⇒(3)部分的证明中，构造性地得到了一个一一对应的割[,ST]。其中点集S表示在Gf中与s连通的点集；TVS=−。所以在问题的实现上分两步，先求得最大流（在1.5节有简要）；再在得到最大流f后的残留网络Gf中，从s开始深度优先遍历（DFS），所有被遍历到的点，即点集S。注意，虽然最小割[,ST]中的是边，但边不一定都是最小割中的边。在某些特殊图中，很多初学者容易犯错，认为不用DFS，就可以直接得出割。下面举一个二分图的例子。第8页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber1/∞111/∞2/32/341/141/11/∞1/11/11/∞s2ts2t1/∞1/∞1/153/31/153/3331/∞1/∞(a)(b)图1.2求最小割的二分图例子图1.2(a)给出了一个基于二分图构造的流网络。由于从X部到Y部都是容量均为正无限的不可能是最小割中的人便会错误地认为与源或汇关联的组成了最小割（图1.2(a)的红色边）。实际上，在该网络的残留网络中，结点2与3应该与源s是连通的（图1.2(b)的蓝色路径），所以最小割应该是图1.2(b)中的红色边。1.5.最大流的算法AlgorithmforumFlow由于本文只研究最小割的应用，对为得到最小割而具体使用的最大流算法本身不进行深入的讨论。下面列出一些常用的适用于图的最大流算法。有的读者可以在参考文献[AMO93]，[CLRS01]中找到相关的知识，此外，参考文献[ZCW03]中有对最大流算法历史的简要回顾。给出流网络GVE=(,)。简记nV=，mE=。设U为最大的边容量值。后文不再涉及具体的最大流复杂度，通常以OG(MaxFlow())，On(MaxFlow(,m))或On(MaxFlow())代替。算法名称复杂度概要增广路Augmentingpathmethod(FordFulkersonmethod)增广路算法在残留网络中，每次任意找一条增广路径OnmU()Labelingalgorithm增广。在残留网络中，每次找一条有最大可增广容量缩放增广路算法Onm(log)U容量和的增广路径增广，即残留网络中源Capacityscalingalgorithm到汇的最长路。最短增广路算法在残留网络中，每次找一条含结点数最少ShortestaugmentingpathOnm()2的增广路增广，即残留网络中源到汇的algorithm(EdmondsKarpBFS路径。algorithm)第9页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber在EdmondsKarp的基础上改造。在每次连续最短增广路算法③BFS找增广路时，每个点的距离标SuccessiveshortestOnm()2号。在距离标号的所的最短路图上，augmentingpathalgorithm不断地DFS找增广路。即一次标号多次(Dinicalgorithm)增广，以提高速度。预流推进Preflow-pushmethod预流推进算法维护一个预流，不断地对活跃结点执行Genericpreflow-pushOnm()2push操作或relabel操作来调整这个预流，algorithm直到不能操作。先进先出预流推进算法On()3以先进先出队列维护活跃结点。FIFOpreflow-pushalgorithm最高标号预流推进算法Highest-labelpreflow-pushOn()2m每次检查具有最高标号的活跃结点。algorithm(Relabel-to-Frontalgorithm)增广路的复杂度是通过估计增广次数的上界得到的。对于实际应用中的网络，增广次数往往很少，所以使用范围还是很广的，实用性强。预流推进看似比增广路在复杂度上快很多，实际上，预流推进的复杂度的上界是比较紧的。对于一些稀疏图，预流推进的实际效果往往不如增广路。1.6.分数规划FractionalProgram先给出分数规划（fractionalprogram）的形式：Minimizeλ=f(st..∀xx∈>S,b()0其中，x在解空间S内，a()x与b()x都是连续的实值函数。解决分数规划问题的是分析其对偶问题，但更加实用的是对其进行参数搜索(parametricsearch)，即对进行猜测，再验证该猜测值的最优性，将优化问题转化为判定性问题或其他的优化问题。由于分数规划模型的特殊性，使得能够构造另外一个由猜测值λ作为自变量的相关问题，且该问题的解满足一定的单调性，或其他的可以减小参数搜索范围的性质④，从而逼近。假设λ**=f()x为该规划的最优解，有：③该连续最短增广路算法与求最小费用流的连续最短增广路算法同名。④比如Dinkelbach算法，每次直接把上次子问题的代入原问题的表，算出下一个迭代式的猜测值。详见参考文献[Dink67]，[MSS92]。第10页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber*)λ*f*)⇒⋅λ**ba()xx=()*⇒=0()abxx***−⋅λ()由上面的形式构造一个新函数g()λ：ga()λ=−⋅min((){xλb()x}(1.3)x∈S这个新函数是一个式的规划。先来挖掘函数g()λ本身的性质。性质1.7（单调性）g()λ是一个严格递减函数，即对于λ1<λ2，一定有gg()λ12>()λ。证明：设x1最小化了g()λ1。则gab(λλ11)=−⋅min((){xx()}x∈S=−⋅ab()xxλ()111>−⋅ab()xx12λ()1≥−⋅=min((){}abgxxλ22()(λ)x∈S最表示，g()λ1上最小解x1代入g()λ2后，不一定还是最小解，甚至有更小解。■有了单调性，就意味着可以采用二分搜索的逼近。但还不知道目标是什么，下面考察构造出的新函数与原目标函数的最优解。定理1.8（Dinkelbach定理⑤）设λ*为原规划的最优解，则g()λ=0当且仅当λ=λ*。证明：(1)先证必要性λλ=⇒*g()λ=0：设λ**=f()x为原规划的最优解，则g()0λ*=。对于∀∈xS，都比x*优：x*可以取到这个下限。aλ*bx*)0=b(⑤出自参考文献[Dink67]。第11页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber故g()λ*的最小值由x*确定，g()0λ*=。(2)再证充分性g()λ=⇒0λλ=*：若一个解x，使得g()λ=0，则λ=f()x为原规划的最优解。反证法。反设一个解λ'(=fx')，它是比λ=f()x更优的解。a(')xλλ'=λλ⎪*⎩g()λ>⇔<0λλ■由推论1.9，就可以对最优解λ*进行二分查找逼近。每次查找到一个猜测值λ，需计算g()λ的值，而g()λ是一个数规划，将原问题化简了，便可以 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 出其他有效的算法解决这个规划。算法复杂度是二分迭代次数与每次解决g()λ的复杂度的积。以上分析是最小化目标函数的分数规划，实际上对于最大化目标函数也一样适用。分数规划的一个特例是0-1分数规划(0-1fractionalprogram)⑥，就是其x满足∀∈xi{0,1}（这就是所谓的0-1）。形式化定义如下：Minimizeλf(x∈{0,1}n)iiist..bx⋅>0并且对x可能还有其他的组合限制。它的应用范围很广，经典例题是最优比率生成树（theoptimumratiospanningtree）⑦。⑥0-1分数规划的相关知识，在参考文献[MSS92]中有详细。⑦详见参考文献[LiuH04]，303-304页。第12页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber2.基于定义的直接应用ApplicationsbasedontheDefinition2.1.引入Introduction在这类基于最小割定义的直接应用中，最小割模型的建立往往比较简单，但常常又和一些新颖的知识融合在一起。这样一来便不能直接地套用模型，而是需要使用一些知识与技巧，逐步将问题化归到最小割模型，使其成为某些主算法的子过程。这类应用比较冗杂，使并没有太多通用的理论性，一些特别的知识与技巧在具体的题目分析中才能得以体现。2.2.应用Application2.2.1.网络NetworkWars⑧描述Description给出一个带GVE=(,)，每条边e有一个权we。求将点s和点t的一个边割集C，使得该割集的平均最小，即最小化：∑weeC∈(2.1)||C解答Solution先尝试着用更的形式重新叙述本问题。设向量w表示边的，令向量c=(1,1,...,1)表示选边的代价，问题等价为：wx∑eewx⋅Minimizeλ==f(x)eE∈=∑1⋅xecx⋅eE∈其中，x表示一个，xe∈{0,1}，即对于每条有选与不选两种决策，并且选出的组成一个st−边割集。形式化地，若xe=1，则eC∈；xe=0，则eC∉。已有的知识，这是一个0-1分数规划。在1.6节中已经给出了这类规划的普遍转化方法：构造一个新函数⑧题目来源：OnlineJudge-AndrewStankevich'sContest#8-2676NetworkWars第13页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amberg()λλ=min({wcx−⋅)}x即对每条边∀∈eE，进行重赋权：wwee'=−⋅λcwee=−λ。g()λ便是在这个重新赋权的图上，求一个最小容量的st−边割集。请注意一些细节：若we'0<，又由于目标函数是加和取最小的操作，则该边必然是在边割集内。对于剩下的所有we'0≥的边，直接利用最小割模型求出st−割即可。设λ**=f()x为原规划的最优解，由推论1.9知：⎧g()λ=0⇔=λλ*⎪*⎨g()λ<0⇔>λλ⎪*⎩g()λ>⇔<0λλ于是主算法便是对最优解λ*的二分查找，每次查找用最小割模型求g()λ来判定，进而缩小查找范围，直到满足精度要求。设二分查找次数为k。则该算法复杂度为：Ok(MaxFlow()⋅N)。2.2.2.最优标号OptimalMarks⑨描述Description给出一个无GVE=(,)，每个点v以一个有界非负整数作为标号lv，每条边euv=(,)的权we定义为该边的两个端点的标号的异或值，即wleu=xorlv。现已知其中部分点的标号，求使得该图的总和最小的标号赋值。即最小化：(2.2)∑∑wleu=(xorlv)eE∈∈(,)uvE解答Solution先规范化问题，不妨设所有点一定和已知标号的点连通。否则，令那些不与已知标号点连通的点的标号为0，这些点间的也不必计入目标函数（都为0）。在问题的优化式子中，发现操作xor不好处理，难以转化为一些基本运算。自然地，先考∞察操作的定义：i，其中，分别表示，的二进制表达xorabxor=⋅∑2(aiixorb)aibiabi=0式第i位的值。由于xor是按二进制位运算的，所以各个二进制位间是互不影响的。而优化目⑨题目来源：SphereOnlineJudge-839OptimalMarks作者：GuoHuayang第14页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber标的式子是一个和式，可以将每位的公共系数提出来，按位加和：∞∞ii∑∑∑∑∑()lluxorv=⋅2()llui,,xorvi=⋅2()llui,,xorvi(,)uv∈∈E(,)uvEi=0i=0(,)uv∈E于是，主算法就是依次处理各个二进制位，而将子问题化归为：∑∑wleu=(xorlv)eE∈∈(,)uvE该优化式子不变，但是限制条件加强了：对于∀uV∈，lu∈{0,1}。即对于每个点，都只有两种取值，可以看要将点集划分成两类。在这种思想的指导下，重新考察操作xor的意义：对于边的两个端点，若它们同类则无值；若它们异类则有值1。分析到这步，整理一下关于本题的一些已知：点分两类；异类间的计入目标函数；优化目标是最小化。此时，似乎产生了一个需要进行合理类比的念头——是否某个已知模型具备与本题相似的性质？对，那就是最小割模型，它将点集分为两类——S和T；割的容量是S和T间的边容量和；优化目标也是最小化。下面将以上的灵感，形式化地表达如下：将原问题转化为网络NVE=(,NN)的最小割问题。在原图点集的基础上增加源s和汇t；将原图每条无(,)uv∈E替换为两条容量分别为cuv(,)=1，cvu(,)=1的有uv,，vu,∈EN；连接源s到原图每个已经具有标号0的点v(0lv=)，即增加有sv,∈EN，由于该边不应计入目标函数，令容量为csv(,)=∞；连接原图每个已经具有标号1的点v(1lv=)到汇t，即增加有vt,∈EN，同样地，令容量为cvt(,)=∞。更形式化地，有：VVstN=∪{,}EuvuvEsvvVlvtvVlNv={},|(,)∈∪∪{},|∈=,0{},|∈=,v1⎧cuv(,)=∈1(,)uvE⎪⎨csv(,)=∞lv=0⎪⎩cvt(,)=∞lv=1定理2.1（最优性）以上描述的流网络N的最小割[,ST]容量是原问题的最优解。■设最大的标号为U，则该算法的复杂度为OU(log()⋅MaxFlow(N))。第15页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber3.最大权闭合图umWeightClosureofaGraph3.1.引入Introduction定义一个有GVE=(,)的闭合图（closure）⑩是该有的一个点集，且该点集的所有出还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。更形式化地说，闭合图是这样的一个点集VV'∈，满足对于∀uV∈'引出的∀uv,∈E，必有vV∈'成立。还有一种等价定义为：满足对于∀∈uv,E，若有uV∈'成立，必有vV∈'成立，在数上这是一个“蕴含(imply)”的运算。按照上面的定义，闭合图是超过通块的。给每个点v分配一个点权wv（任意实数，可正可负）。最大权闭合图（umweight），是一个点权之和最大的闭合图，即最大化。closure∑wvvV∈'512-65-37340图3.1闭合图的例子在图3.1中的网络有9个闭合图（含空集）：∅，{3,4,5}，{4,5}，{5}，{2,4,5}，{2,5}，{2,3,4,5}，{1,2,4,5}和{1,2,3,4,5}，其中有最大的闭合图是{3,4,5}，为4。在许多实际应用中，给出的有常常是一个有图（DAG），闭合图的性质恰好反映了间的必要条件的：一个的发生，它所需要的所有前提也都要发生。一个常见的例子就是制定大学的选课计划，其中一些课程需要以另一些课程为基础，这就是给出了有图。若给所有课程打分，最大权闭合图对应了获益最大或效率最高的选课计划，解决了这个问题，就可以容易地选出一个最合理的选课计划。在另外一些实际应用中，给出的是一个有，即有可能出现圈。常见的例子就是工程分期，一个工程可能含有很多项目，项目之间也有依赖。有些项目是需要同期一起开发，互相依赖的（即出现圈）。这样，也可以利用最大权闭合图，将最先应该完成的项目选出来作为工程的第一期。⑩闭合图为作者本人对closure的翻译，该名词出自参考文献[AMO93]，未见有其他中文文献的翻译。[Jiang01]中虽然提及本问题，但未提出对于该类图的通称。第16页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber3.2.构造ConstructionofAlgorithm下面给出将原问题的图G转化为网络NVE=(,NN)的，从而可以利用最小割模型。在原图点集的基础上增加源s和汇t；将原图每条有uv,∈E替换为容量为cuv(,)=∞的有uv,∈EN；增加连接源s到原图每个正v(wv>0)的有sv,∈EN，容量为csv(,)=wv；增加连接原图每个负v(wv<0)到汇t的有，容量为。其中，正无限定义为任意一个大于的整数。更vt,∈ENcvt(,)=−wv∞∑wvvV∈形式化地，有：VVstN=∪{,}EENvv=∈>∈<∪∪{}svvVw,|,0{}vtvVw,|,0⎧=∞∈cuv(,)sv,E⎪⎨csv(,)=>wvvw0⎪cvt(,)=−ww<0⎩vv∞612t∞5∞35∞7∞s34图3.2闭合图构图的例子图3.2是将图3.1转化后的网络：从源s向两个正1,3，从两个负2,5t。3.3.证明Proof定义：若一个st−割满足割中的每条边只都与源s或汇t关联，称该割为简单割（simplecut）。根据该定义，网络N的简单割是不含原图G的E中的任何边的。引理3.1在本问题的网络N中，最小割是简单割。证明：网络N中两类：与源或汇关联的边，容量为有限值；不与源或汇关联的边，即原来E中的边，容量均为正无限。所有与源或汇关联的边组成的割集的容量是有限的，为所有点权的绝对值和。最小割容量也至多为该绝对值和。故最小割不可能取任何容量为正无限的边，即最小割是简单割。■第17页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber先规定一些符号。设简单割[,ST]将网络N的点集VN划分为点集S及其补集T()TV=−NS，满足sS∈，t∈T。设闭合图为V1，它在V中的补集为V1或V2()VVV21=−。+−+−+记V为V中点权为正的点集，V为V中点权为负的点集。同样地，可以定义V1与V1，V2−与V2。下面的工作就是将简单割与闭合图一一对应起来，以便利用最小割模型求解。引理3.2（可行性）网络N的简单割[,ST]与图G的闭合图V1 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 一个一一对应关系：Vs1∪{}=S。证明：(1)闭合图对应简单割：即SV=1∪{}s，TV=1∪{}t，求证[,ST]为简单割。反证法。反设uv,∈E，其中uS∈−={}sV1，vT∈−={}tV1，使得[,ST]含不与源或汇关联的边。则闭合图V1有一个后继不在闭合图内，。(2)简单割对应闭合图：即证VSs1=−{}是闭合图。对于闭合图中∀uV∈1，考察任意一条由u引出的出边uv,∈E，由于简单割[,ST]不含E中的任何边，故vT∉−{}t=V1，即vV∈1，符合闭合图的定义。■推论3.3（对应的数量化）在引理3.2的一一对应下，有：cST[,]=+−∑wvv∑()w(3.1)+−vV∈∈21vV证明：割[,ST]按照与源或汇的关联情况，可以分为3部分：[,ST]=[{},]sV21∪∪[V,{}][tV1,V2]由于割[,ST]是简单割，故[,VV12]=∅。+又由于源s只与正有边，故[{sV},22]=[{sV},]。−同样的汇t只与负有边，故[,{}][Vt11=V,{}]t。+−综上，[,ST]=[{},]sV21∪[V,{}]t，因此式(3.1)成立。■第18页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber定理3.4（最优性）当网络N的取到最小割时，其对应的图G的闭合图将达到最大权。证明：按照定义，闭合图的为正的权的绝对值和减去负的权的绝对值和：wV()1=−−∑wv∑()wv(3.2)+−vV∈∈11vV将式(3.2)与推论3.3的式(3.1)相加，得到：wV()1+=−−++−cS[,]T∑wvvv∑∑∑()ww()wv+−+−vV∈∈11vVvV∈21vV∈=+∑∑wwvv++vV∈∈12vV=∑wvvV∈+整理得：(3.3)wV()1=−∑wvcS[,]TvV∈+观察式(3.3)，目标是最大化，而正的总为定值，故最小化简单割的wV()1∑wvvV∈+容量cST[,]，便可得到最大的wV()1。根据引理3.1，最小割为简单割。所以最小割是最小的简单割，故为网络N的最小割所对应的闭合图。■算法复杂度便是求最小割的复杂度：ON(MaxFlow())。3.4.应用Application3.4.1.最大获利Profit11描述DescriptionADN公司得到了一共n个可以作讯信号中转站的地址。由于这些地址的地理位置差异，在不同的地方建造通讯中转站所需要投入的成本也是不一样的，所幸在前期调查之后这些都是已知数据：建立第i个通讯中转站需要成本pi。另外公司调查得出了所有期望中的用户群，一共m个。第i个用户群的用户会使用中转站ai和中转站bi进行通讯，公司获益ci。ADN公司可以有选择地建立一些中转站（其成本之和为总成本），为一些用户提供服务并获得（之和为总）。那么如何选择最终建立的中转站才能让公司的净获利最大呢？（净获利=总－总成本）11题目来源：NOI2006Day2最大获利(Profit)第19页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber解答Solution首先分析题目中的决策因素。在满足了第i个用户群后，便可以得到ci，满足第i个用户群需要有必要条件：建立中转站ai和中转站bi，同时要花去相应费用。留心这个所谓的必要条件，便可联想到闭合图的性质。分析后发现，本题就是最大权闭合图的一个特例。把它抽象成这样一个有模型：每个用户群i作为一个结点分别向相应的中转站ai和中转站bi连有。事实上，这是一个二分图上的特例。求这个图的最大权闭合图，便可解决本题。复杂度为Onmn(MaxFlow(++,m))。而4.7节给出的结果，可以使本题在仅O(MaxFlow(nnm,+))的时间内解决。这也是本文比较重要的之一。参见应用4.8.2。4.最大密度子图FindingaumDensitySubgraph4.1.引入Introduction定义一个无GVE=(,)的密度(density)D为该图的E与该图的点数V的比值||ED=。给出一个无GVE=(,)，其具有最大密度的子图GVE'=(',')称为最大密度||V|'|E子图（umdensitysubgraph），即最大化D'=。|'|V简记nV=，mE=。123456图4.1最大密度子图的例子举例，在图4.1中，给出了一幅6个点的图，其中在虚线内的点与边组成最大密度子图，第20页共45页[ADN.cn][Library]Thesis最小割模型在学竞赛中的应用Amber5红边组成子图的，密度为。44.2.主算法MainAlgorithm先尝试着更形式化地重新叙述本模型：∑xeizeDf==(x)eE∈∑xvvV∈其中xxve,{0,∈1}，表示对于每个点或每条边是否在子图GVE'=(',')中，即vV∈⇔='1xv，∀∈eE'⇔xe=1。并且对于∀euvE=∈(,)'，必有uv,'∈V。1.6节的分数规划，以上规划就是一个0-1分数规划的模型。根据分数规划步骤，应是进行二分查找，对于一个的猜测值g，构造一个新函数⎧⎫hg()=max⎨1⋅−xevg⋅x⎬x∑∑⎩⎭eE∈∈vV设Df**=()x为原规划的最优解，由推论1.9知：⎧hg()=⇔0g=D*⎪*⎨hg()<⇔0g>D⎪*⎩hg()>⇔0g