搜索
[ADN.cn][Library]Thesis昀小割模型在信息学竞赛中的应用Amber第1页共45页昀小割模型在信息学竞赛中的应用ApplicationsofMinimumCutModelinInformatics胡伯涛Amber[ADN.cn]福州第一中学FuzhouNo.1MiddleSchoolhupo001[at]gmail[dot]com[ADN.cn][Library]Thesis昀小割模型在信息学竞赛中的应用Amber第2页共45页[摘要]本文对昀小割模型的定义和性质，以及其相关扩展知识进行了研究。其中着重对昀小割模型在以下四个方面的应用展开研究：1.基于定义的直接应用；2.昀大权闭合图；3.昀大密度子图；4.二分图的昀小点权覆盖集和昀大点权独立集。展现与剖析了昀小割模型应用的巧妙构图方法和独特思维方式，并对这一类应用的通用方法与技巧给予总结。[关键字]网络流，昀大流，昀小割，昀大权闭合图，昀大密度子图，二分图昀小点权覆盖集，二分图昀大点权独立集[Abstract]Thepurposeofthethesisistoresearchthedefinition,properties,andcorrelatedextendedknowledgeofminimumcutmodel.Thethesissetsfocusonresearchingthatisinfouraspects:1.theapplicationbasedontheminimumcutmodel;2.themaximumweightclosureofagraph;3.themaximumdensitysubgraph;4.theminimumweightvertexcoveringsetandthemaximumweightvertexindependentsetinthebipartitegraph.Itshowsandanalyzestheconstructionmethodsandthinkingmodesoftheminimumcutmodel.Finally,itsummarizesthemethodsandskillsintheapplicationsoftheminimumcutmodel.[KeyWords]NetworkFlow,MaximumFlow,MinimumCut,MaximumWeightClosureofaGraph,FindingaMaximumDensitySubGraph,MinimumWeightVertexCoveringSetandMaximumWeightVertexIndependentSet,BipartiteGraph[目录]0.前言Preface................................................................................................................................41.预备知识Preliminaries...............................................................................................................41.1.网络与流NetworkandFlow...........................................................................................41.2.残留网络与增广路径ResidualNetworkandAugmentingPath....................................51.3.昀大流与昀小割MaximumFlowandMinimumCut....................................................61.4.昀小割的算法AlgorithmforMinimumCut...................................................................81.5.昀大流的算法AlgorithmforMaximumFlow................................................................91.6.分数规划FractionalProgramming................................................................................102.基于定义的直接应用ApplicationsbasedontheDefinition....................................................132.1.引入Introduction...........................................................................................................132.2.应用Application............................................................................................................132.2.1.网络战争NetworkWars....................................................................................132.2.2.昀优标号OptimalMarks..................................................................................143.昀大权闭合图MaximumWeightClosureofaGraph..............................................................16[ADN.cn][Library]Thesis昀小割模型在信息学竞赛中的应用Amber第3页共45页3.1.引入Introduction...........................................................................................................163.2.构造ConstructionofAlgorithm....................................................................................173.3.证明Proof......................................................................................................................173.4.应用Application............................................................................................................193.4.1.昀大获利Profit..................................................................................................194.昀大密度子图FindingaMaximumDensitySubgraph............................................................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.二分图的昀小点权覆盖集与昀大点权独立集MinimumWeightVertexCoveringSetandMaximumWeightVertexIndependentSetinaBipartiteGraph.........................................................305.1.引入Introduction...........................................................................................................305.2.二分图的昀小点权覆盖集算法AlgorithmforMinWVCSinaBipartiteGraph.........315.3.二分图的昀大点权独立集算法AlgorithmforMaxWVISinaBipartiteGraph.........325.4.应用Application.........................................................