生成MST（学习笔记）

一、MST的定义：
       ST：e∈E且e∈T。
       MST：所有ST中边权值和最小者。
二、求MST的算法：
        核心思想：贪心（非常经典的应用）
        思路：①破圈法：这可以说是MST最重要的思路，大部分MST的证明都可以用它。
        G->T<=>圈->无圈。在任意一个环中，易证，我们需要删掉最大边，使得生成树最小。因为每一条边的地位都是等价的，在一个环中删去任意一条边都可以使此环连通，所以删掉最大边显然是最优的。
        破圈法就是通过不断地删环中最大边使得图中无环的，其正确性可以通过反证法简单证明。
        ②避圈法：破圈法的反面就是避圈法。破圈法的思想是非常好的，但是实现起来却比较困难，一个方法是正难则反，向最小生成树中加边加点。Kruskal、Prim算法基本都是采用了这种方法。
        具体方法：①Prim算法：类Dijkstra，时间复杂度O((|V|+|E|)log(|V|))。
        ②Kruskal算法：是一种巧妙的连接联通块的思想，时间复杂度O(|E|log(|E|))。
                                Kruskal算法的用途和思想都是很重要的。
                                    比如，它可以用来解决一些最大边权路的问题（如CODEVS1450、CODEVS1001），而且它比Prim算法简单很多，时间复杂度实际上并不比Prim差多少，即使是在完全图里，也是可以使用的。
        ③除此以外，还有据传O(V+E)、O(kE)的高端算法。。
三、MST的性质：
                这一部分是我重点研究的，为此专门研读了《算法导论·最小生成树的形成》一节，所以重点写一下。对其证明的一个很重要的方法是加边构环，判定大小。
        ①割的轻边不一定在最小生成树中。
                证：割的轻边不一定是环的轻边。
        但，最小生成树中的必为割的轻边。（Kruskal）
        ②若图中边权均为正，有最小总权值且连接所有节点的边集必为MST。
            证：易知，若其为T，则必为MST。
                   设若其不为T，则破环，其总权值必定减少，便与题设相悖。
                   ∴其必为T，必为MST。
        ③图G的任一最小生成树，其边权升序列表必相同。
            证：设T1：a1、a2、a3...；T2：b1、b2、b3...为T1与T2已排序的边权列表。
                   设ai<=bi且对任意ak,bk,k∈[1,i)∩N，存在ak=bk。
                   则将bi加入T1，形成环A，易知环A中，bi为最大权值且必存在aj=bi,j>i.
                   ∵aj>=ai
                   ∴aj>=ai<=bi=aj
                   ∴aj=bi
                   ∴证得任意ai，bi，ai=bi
        ④MST是瓶颈生成树。（经典题：繁华的都市）
            证：瓶颈生成树必出自瓶颈图，即最大边权最小连通图，且设其最大边权为w0，则对任意e∈E，w(e)<=w(0)。
                   ∴易知其可用Kruskal求出。
                   ∴最小生成树必为瓶颈生成树。