CLRS23 最小生成树

2017-05-29 | 阅读：次

介绍

我们希望找到一个无环子集，既能够将所有的结点连接起来，又具有最小的权重。我们称这样的树为最小生成树。
本章介绍解决最小生成树问题的两种算法：Kruskal算法和Prim算法。如果使用普通的二叉堆，可以将两个算法的时间复杂度限制在O(ElgV)，使用斐波那契堆Prim算法的运行时间为O(E+VlgV)。这两种算法都是贪心算法。

23.1 最小生成树的形成

通用方法：在每遍循环之前，A是某棵最小生成树的一个子集。

GENERIC-MST(G, w)
    A = {}
    while A does not form a spanning tree
        find an edge (u, v) that is safe for A
        A = A U {(u, v)}
    return A

重点是算法的第三行，如何寻找安全边。
定理23.1：设集合A为E的一个子集，且A包括在图G的某棵最小生成树中，设(S, V-S)是图G中尊重集合A的任意一个切割，又设(u, v)是横跨切割(S, V-S)的一条轻量级边，那么边(u, v)对于集合A是安全的。

初始时A为空，GA中有

棵树，每边循环都将树的数量减少一棵。当森林中只包含一棵树时，该算法终止。

练习23.1-1 Let (u, v) be a minimum-weight edge in a graph G. Show that (u, v) belongs to some minimum spanning tree of G.

In the first step of GENERIC-MST, we could choos such a cut, node u is on one side, node v is on another side. Then (u, v) is a light-edge through this cut. So, it is safe to add (u, v).

练习23.1-2 Professor Sabatier conjectures the following converse of Theorem 23.1. Let G = (V, E) be a connected, undirected graph with a real-valued weight function w defined on E. Let A be a subset of E that is included in some minimum spanning tree for G, let (S, V - S) be any cut of G that respects A, and let (u, v) be a safe edge for A crossing (S, V - S). Then, (u, v) is a light edge for the cut. Show that the professor’s conjecture is incorrect by giving a counterexample.

(B, A): 5
(C, A): 10
A在cut的一边，BC在另一边
则(A, C)是安全的，但不是最轻边

练习23.1-3 Show that if an edge (u, v) is contained in some minimum spanning tree, then it is a light edge crossing some cut of the graph.

In this MST, we remove (u,v) and draw a cut cross (u,v). Now, our strategy is choose a light-weight edge, because (u,v) is in this MST originally, 
then (u,v) is a light edge.

练习23.1-4 Give a simple example of a graph such that the set of edges {(u, v) : there exists a cut (S, V - S) such that (u, v) is a light edge crossing (S, V - S)} does not form a minimum spanning tree.

当三角形三条边权重相同时,每条边在某种 cut 中均是最轻,即结果中存在环,所以不是最小生成树.

练习23.1-5 Let e be a maximum-weight edge on some cycle of G = (V, E). Prove that there is a minimum spanning tree of G′ = (V, E -{e}) that is also a minimum spanning tree of G. That is, there is a minimum spanning tree of G that does not include e.

因为环路上所有其它边都优于e，所以可以不用选它。

练习23.1-6 Show that a graph has a unique minimum spanning tree if, for every cut of the graph, there is a unique light edge crossing the cut. Show that the converse is not true by giving a counterexample.

假设存在两个最小生成树 T 和 T'. 对任意一条边 e 属于 T, 如果从 T 中移除 e, 则 T 变得不连通, 形成 cut (S, V - S), 根据练习 23.1-3 可知, e 是穿过 cut(S, V - S) 
最轻边. 假设边 x 属于 T', 并穿过 cut (S, V - S), 则 x 同样是最轻边. 由于穿过 cut(S, V - S) 的最轻边唯一. 既 e 和 x 是同一条边. 所以 e 也属于 T', 由于我们选择 e
是任意的, 所有在 T 中的边, 同样在 T' 中. 即最小生成树唯一.

反例：
    (B, A): 1
    (C, A): 1
    A在cut的一边，BC在另一边

练习23.1-7 Argue that if all edge weights of a graph are positive, then any subset of edges that connects all vertices and has minimum total weight must be a tree. Give an example to show that the same conclusion does not follow if we allow some weights to be nonpositive.

如果不是树，即T中存在环，两点之间存在多条通路。移除一条，可以得到更小的总权重，与条件矛盾。所以是树。

如果边的权重可以为负，子集T不一定是树。可以找到一种情况其中权重都是负的，环路权重最小。

练习23.1-8 Let T be a minimum spanning tree of a graph G, and let L be the sorted list of the edge weights of T. Show that for any other minimum spanning tree T′ of G, the list L is also the sorted list of edge weights of T′.

https://github.com/gzc/CLRS/blob/master/C23-Minimum-Spanning-Trees/23.1.md

感觉证明题都有点复杂

练习23.1-9 Let T be a minimum spanning tree of a graph G = (V, E), and let V′ be a subset of V. Let T′ be the subgraph of T induced by V′, and let G′ be the subgraph of G induced by V′. Show that if T′ is connected, then T′ is a minimum spanning tree of G′.

We use cut(V', V - V') to cut graph. This cut will not influence T' and T' is the subset of T, so to G', T' is safe. if T′ is connected, then T′ is a minimum 
spanning tree of G.

练习23.1-10 Given a graph G and a minimum spanning tree T , suppose that we decrease the weight of one of the edges in T . Show that T is still a minimum spanning tree for G. More formally, let T be a minimum spanning tree for G with edge weights given by weight function w.

We prove by cut. Originally, (x,y) is the light edge in a certain cut(V1, V2). Decreasing the weight of (x,y), (x,y) is still a light edge. So T is a 
minimum spanning tree for G with edge weights given by w′.

练习23.1-11 Given a graph G and a minimum spanning tree T , suppose that we decrease the weight of one of the edges not in T . Give an algorithm for finding the minimum spanning tree in the modified graph.

If(u,v) is not in MST, decrease the weight of(u, v), we may form a new MST T'.
Condition 1 : if the weightest edge e in path from u->v is greater than edge(u,v).Then we can replace e with (u,v).
Condition 2 : if the weightest edge e in path from u->v is less or equal than edge(u,v).Then we need not change,

23.2 Kruskal算法和Prim算法

这两种算法都是前一节所讨论的通用算法的细化，每种算法都使用一条具体的规则来确定GENERIC-MST算法第三行所描述的安全边。
Kruskal算法在所有连接森林中两棵不同树的边里面，找到权重最小的边(u, v)。

MST-KRUSKAL(G, w)
    A = {}
    for each vertex v in G.V
        MAKE-SET(v)
    sort the edges of G.E into nondecreasing order by weight w
    for each edge(u, v) in G>E, taken in nondecreasing order by weight
        if FIND-SET(v) != FIND-SET(v)
            A = A U {(u, v)}
            UNION(u, v)
    return A

运行时间为O(ElgV)

Prim算法的工作原理与Dijkastra的最短路径算法相似。Prim算法的一个性质是集合A中的边总是构成一棵树。这棵树从一个结点开始，不断长大到覆盖所有结点。算法每一步在连接集合A与A之外的结点的所有边中，选择一条轻量级边加入A中。

MST-PRIM(G, w, r)
    for each u in G.V
        u.key = INFINITE
        u.pai = NIL
    r.key = 0
    Q = G.V
    while Q != {}
        u = EXTRACT-MIN(Q)
        for each v in G.Adj[u]
            if v in Q and w(u, v) < v.key
                v.pai = u
                v.key = w(u, v)

PRim算法的运行时间取决于最小优先队列Q的实现方式，如果Q实现为一个二叉最小优先队列，总时间代价为O(ElgV)
如果使用斐波那契堆，运行时间将改善为O(E + VlgV)

练习23.2-1 Kruskal’s algorithm can return different spanning trees for the same input graph G, depending on how ties are broken when the edges are sorted into order. Show that for each minimum spanning tree T of G, there is a way to sort the edges of G in Kruskal’s algorithm so that the algorithm returns T.

The reason why there may be several different MST is that we have several choices on same weighted edge.

Given a minimum spanning tree T we wish to sort the edges in Kruskal’s algorithm such that it produces T. For each edge e in T simply make sure that it 
preceeds any other edge not in T with weight w(e).

练习23.2-2 Suppose that the graph G = (V, E) is represented as an adjacency matrix. Give a simple implementation of Prim’s algorithm for this case that runs in O(V^2) time.

MST-PRIM(G, w, r)
    for each u in G.V
        u.key = -INFINITE
        u.pai = NIL
    r.key = 0
    Q = G.V
    while Q is not empty
        u = EXTRACT-MIN(Q)
        for i = 1 to n
            if matrix[u][i] == 1 and i in Q and w(u, i) < i.key
                i.pai = u
                i.key = w(u, i)

练习23.2-3 Is the Fibonacci-heap implementation of Prim’s algorithm asymptotically faster than the binary-heap implementation for a sparse graph G = (V, E), where

= Θ(V)? What about for a dense graph, where

= Θ(V2)? How must

and

be related for the Fibonacci-heap implementation to be asymptotically faster than the binary-heap implementation?

运行时间分别是 O(ElgV) O(E + VlgV)
根据E和V的关系可以得出。

练习23.2-4 Suppose that all edge weights in a graph are integers in the range from 1 to

. How fast can you make Kruskal’s algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W?

练习23.2-5
练习23.2-6
练习23.2-7
练习23.2-8

Sasuke

Jing

CLRS23 最小生成树

介绍

23.1 最小生成树的形成

23.2 Kruskal算法和Prim算法