算法合集之《最小割模型在信息学竞赛中的应用》

《算法合集之《最小割模型在信息学竞赛中的应用》》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、[ADN.cn][Library]Thesis最小割模型在信息学竞赛中的应用Amber最小割模型在信息学竞赛中的应用ApplicationsofMinimumCutModelinInformatics胡伯涛Amber[ADN.cn]福州第一中学FuzhouNo.1MiddleSchoolhupo001[at]gmail[dot]com第1页共45页[ADN.cn][Library]Thesis最小割模型在信息学竞赛中的应用Amber[摘要]本文对最小割模型的定义和性质，以及其相关扩展知识进行了研究。其中着重对最小割模型在以下四个方面的应用展开研究：1

2、.基于定义的直接应用；2.最大权闭合图；3.最大密度子图；4.二分图的最小点权覆盖集和最大点权独立集。展现与剖析了最小割模型应用的巧妙构图方法和独特思维方式，并对这一类应用的通用方法与技巧给予总结。[关键字]网络流，最大流，最小割，最大权闭合图，最大密度子图，二分图最小点权覆盖集，二分图最大点权独立集[Abstract]Thepurposeofthethesisistoresearchthedefinition,properties,andcorrelatedextendedknowledgeofminimumcutmodel.Thethesisse

3、tsfocusonresearchingthatisinfouraspects:1.theapplicationbasedontheminimumcutmodel;2.themaximumweightclosureofagraph;3.themaximumdensitysubgraph;4.theminimumweightvertexcoveringsetandthemaximumweightvertexindependentsetinthebipartitegraph.Itshowsandanalyzestheconstructionmethods

4、andthinkingmodesoftheminimumcutmodel.Finally,itsummarizesthemethodsandskillsintheapplicationsoftheminimumcutmodel.[KeyWords]NetworkFlow,MaximumFlow,MinimumCut,MaximumWeightClosureofaGraph,FindingaMaximumDensitySubGraph,MinimumWeightVertexCoveringSetandMaximumWeightVertexIndepen

5、dentSet,BipartiteGraph[目录]0.前言Preface................................................................................................................................41.预备知识Preliminaries.............................................................................................

6、..................41.1.网络与流NetworkandFlow...........................................................................................41.2.残留网络与增广路径ResidualNetworkandAugmentingPath....................................51.3.最大流与最小割MaximumFlowandMinimumCut............................

7、........................61.4.最小割的算法AlgorithmforMinimumCut...................................................................81.5.最大流的算法AlgorithmforMaximumFlow................................................................91.6.分数规划FractionalProgramming..........................

8、......................................................