当前课程知识点：算法设计与分析 > 4 Greedy Algorithms > 4.8 Correctness of Algorithms > Correctness of Algorithms
为了讨论上的方便
我们先假设所有的费用
也就是权重是不同的
我们有两条性质
分别称为割最优性质和圈最优性质
令S是任意一个点的子集
恰有一个端点属于S的边中
费用最小的记为e
则最小支撑树一定包含e
这条性质 我们称为割最优性质
令C是任意一个圈
f是这个圈上费用最大的边
那么最小支撑树一定不包含f
这条性质 我们称为圈最优性质
下面我们来证明割最优性质
令S是任意一个点的子集
有一个端点在S中的边中
费用最小的记为e
则最小支撑树T^*一定包含e
我们用交换的方法来证明
假设 e不属于T^*
我们把e加入T^*中
它会生成唯一的一个圈C
边e既在圈C中
也在S对应的割集D中
那么一定存在着另外一条边f
它也在C和D的交集中
们在T^*中
删去f 加入e
容易发现得到了一棵支撑树T'
因为c_e 所以T'的费用小于T^*的费用 这与T^*是一个最小支撑树矛盾 我们再来证明圈最优性质 令C是任意一个圈 f是这个圈上费用最大的边 那么最小支撑树T^*一定不包含f 我们仍然用交换的方法来证明 假设f属于T^* 把f从T^*中删除 我们会得到一个割S 边f既在圈C中 也在S对应的割集D中 那么一定存在着另外一条边e 它也在C和D的交集中 我们在T^*中 删去f 加入e 也得到一棵支撑树T' 因为c_e 所以T'的费用小于T6*的费用 这与T*是一个最小支撑树矛盾 下面我们来证明Prim算法的正确性 初始的时候 S中包含任意一个点 根据割最优性质 最小支撑树中一定包含 S对应的割集中费用最小的边 注意 我们假设所有边的费用是不同的 所以这样的边是唯一的 Prim算法就是加入了同样的边 我们可以依次证明 Prim算法得到的一棵树是一棵最小支撑树 下面证明Kruskal算法的正确性 Kruskal算法把边按照费用升序进行排列 第一种情况 如果加入边e会产生一个圈 e一定是这个圈上的最大边 根据圈最优性质 最小支撑树中一定不包含e 而Kruskal算法也不会包含e 第二种情况 边e加入T中不形成圈 它会把不连通的两部分连通 令e=(u,v) 我们考虑这样的一个割 T中与u联通的点的集合为S S对应的割集中 所有的边都未被考虑过 因此e一定是其中费用最小的边 根据割最优性质 最小支撑树中一定包含e 而Kruskal算法就加入了e 总之 Kruskal算法最后得到的解 一定是一棵最小支撑树 在上面的讨论中 我们假设所有边的费用是不同的 我们可以通过扰动的办法 去掉这个假设 比如 假定所有的费用是整数 对于边e_i 增加费用i/n^2 再调用相应的算法 它返回的最小支撑树 也对应为原问题的最小支撑树 最后 Prim算法和Kruskal算法 可以在O(mlog n)的时间内实现 这里略去了分析的细节
-1.1 Introduction
-1.2 A First Problem: Stable Matching
--A First Problem: Stable Matching
-1.3 Gale-Shapley Algorithm
-1.4 Understanding Gale-Shapley Algorithm
--Understanding Gale-Shapley Algorithm
-Homework1
-Lecture note 1
--Lecture note 1 Introduction of Algorithm
-2.1 Computational Tractability
-2.2 Asymptotic Order of Growth
-2.3 A Survey of Common Running Times
--A Survey of Common Running Times
-Homework2
-Lecture note 2
--Lecture note 2 Basics of Algorithm Analysis
-3.1 Basic Definitions and Applications
--Basic Definitions and Applications
-3.2 Graph Traversal
-3.3 Testing Bipartiteness
-3.4 Connectivity in Directed Graphs
--Connectivity in Directed Graphs
-3.5 DAG and Topological Ordering
--DAG and Topological Ordering
-Homework3
-Lecture note 3
-4.1 Coin Changing
-4.2 Interval Scheduling
-4.3 Interval Partitioning
-4.4 Scheduling to Minimize Lateness
--Scheduling to Minimize Lateness
-4.5 Optimal Caching
-4.6 Shortest Paths in a Graph
-4.7 Minimum Spanning Tree
-4.8 Correctness of Algorithms
-4.9 Clustering
-Homework4
-Lecture note 4
--Lecture note 4 Greedy Algorithms
-5.1 Mergesort
-5.2 Counting Inversions
-5.3 Closest Pair of Points
-5.4 Integer Multiplication
-5.5 Matrix Multiplication
--Video
-5.6 Convolution and FFT
-5.7 FFT
--FFT
-5.8 Inverse DFT
-Homework5
-Lecture note 5
--Lecture note 5 Divide and Conquer
-6.1 Weighted Interval Scheduling
--Weighted Interval Scheduling
-6.2 Segmented Least Squares
-6.3 Knapsack Problem
-6.4 RNA Secondary Structure
-6.5 Sequence Alignment
-6.6 Shortest Paths
-Homework6
-Lecture note 6
--Lecture note 6 Dynamic Programming
-7.1 Flows and Cuts
-7.2 Minimum Cut and Maximum Flow
--Minimum Cut and Maximum Flow
-7.3 Ford-Fulkerson Algorithm
-7.4 Choosing Good Augmenting Paths
--Choosing Good Augmenting Paths
-7.5 Bipartite Matching
-Homework7
-Lecture note 7
-8.1 Polynomial-Time Reductions
-8.2 Basic Reduction Strategies I
--Basic Reduction Strategies I
-8.3 Basic Reduction Strategies II
--Basic Reduction Strategies II
-8.4 Definition of NP
-8.5 Problems in NP
-8.6 NP-Completeness
-8.7 Sequencing Problems
-8.8 Numerical Problems
-8.9 co-NP and the Asymmetry of NP
--co-NP and the Asymmetry of NP
-Homework8
-Lecture note 8
--Lecture note 8 NP and Computational Intractability
-9.1 Load Balancing
-9.2 Center Selection
-9.3 The Pricing Method: Vertex Cover
--The Pricing Method: Vertex Cover
-9.4 LP Rounding: Vertex Cover
-9.5 Knapsack Problem
-Homework9
-Lecture note 9
--Lecture note 9 Approximation Algorithms
-10.1 Landscape of an Optimization Problem
--Landscape of an Optimization Problem
-10.2 Maximum Cut
-10.3 Nash Equilibria
-10.4 Price of Stability
-Homework10
-Lecture note 10
--Lecture note 10 Local Search
-11.1 Contention Resolution
-11.2 Linearity of Expectation
-11.3 MAX 3-SAT
-11.4 Chernoff Bounds
-Homework11
-Lecture note 11
--Lecture note 11 Randomized Algorithms
-Exam
