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 页 摘要摘要 本文对最小割模型的定义和性质，以及其相关扩展知识进行了研究。其中着重对最小割模型在以下四个方面的应用展开研究：1. 基于定义的直接应用；2. 最大权闭合图；3. 最大密度子图；4. 二分图的最小点权覆盖集和最大点权独立集。展现与剖析了最小割模型应用的巧妙构图方法和独特思维方式，并对这一类应用的通用方法与技巧给予总结。 关键字关键字 网络流，最大流，最小割，最大权闭合图，最大密度子图，二分图最小点权覆盖集，二分图最大点权独立集 Abstract The purpose of the thesis is to research the definition, properties, and correlated extended knowledge of minimum 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 bipartite 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 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 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 最小割模型在信息学竞赛中的应用 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 Algorithm.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 Set and Maximum Weight Vertex Indep