国家集训队2007论文集7.胡伯涛《最小割模型

《国家集训队2007论文集7.胡伯涛《最小割模型》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

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

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

3、elatedextendedknowledgeofminimumcutmodel.Thethesissetsfocusonresearchingthatisinfouraspects:1.theapplicationbasedontheminimumcutmodel;2.themaximumweightclosureofagraph;3.themaximumdensitysubgraph;4.theminimumweightvertexcoveringsetandthemaximumweightve

4、rtexindependentsetinthebipartitegraph.Itshowsandanalyzestheconstructionmethodsandthinkingmodesoftheminimumcutmodel.Finally,itsummarizesthemethodsandskillsintheapplicationsoftheminimumcutmodel.[KeyWords]NetworkFlow,MaximumFlow,MinimumCut,MaximumWeightCl

5、osureofaGraph,FindingaMaximumDensitySubGraph,MinimumWeightVertexCoveringSetandMaximumWeightVertexIndependentSet,BipartiteGraph[目录]0.前言Preface...............................................................................................................

6、.................41.预备知识Preliminaries...............................................................................................................41.1.网络与流NetworkandFlow.................................................................................

7、..........41.2.残留网络与增广路径ResidualNetworkandAugmentingPath....................................51.3.最大流与最小割MaximumFlowandMinimumCut....................................................61.4.最小割的算法AlgorithmforMinimumCut.......................................

8、............................81.5.最大流的算法AlgorithmforMaximumFlow................................................................91.6.分数规划FractionalProgramming................................................................................