算法课件Lecture6章节.pptVIP

Lecture 6Minimum Spanning Tree--Extension;Properties of MST;Properties of MST;Proof of Property 3;;Second-best MST;MST Property;Second-best MST Properties;Second-best MST Properties;Suppose e1 is the minimum edge in T1\ T2. Then T2 U {e1}?contains a cycle on which there must be some edge e which belongs to T2 but not belongs to T1, since otherwise T1 has a cycle. Let T3=T2 U {e1} \e. Then T3 is a spanning tree. We claim that T3 is better than T2. T3 is not equal to T1. Thus, contradicts to that T2 is a second-best MST. ;Proof of 1: We claim that w(e) w(e1).? Proof by contradiction:? assume that w(e) w(e1).? If we add e to T1, we get a cycle C, which contains some edge e in T1 but e is? not in T2. (otherwise, T2 would contain a cycle). Therefore, the set of edges T4 = T1 - {e} U {e} form a spanning tree, and we must have w(e) w(e), since otherwise T4 would be a spanning tree with weight less than w(T1 ). Thus, w(e) w(e) w(e1),? which contradicts our choice of e1 as the? edge in T1 - T2 of minimum weight. Since T3=T2 U {e1} \e, T3 is better than T2. Proof of 2: T3 differs from T2 by only one edge, while T1 differs from T2 by at least two edges, so, T3 is not equal to T1. Thus, we have formed a spanning tree T3 whose weight is less than w(T2) but is not T1. Hence, contradicts that T2 is a second-best minimum spanning tree. ;Compute the Second-best MST;Compute_max(T) for each pair of vertices u, v ?V do max[u, v] ? 0 for each vertex s ?V do BFS (T, s) //E(T)=O(V);Compute the Second-best MST;Time Complexity Analysis;Bottleneck Spanning Tree;BST vs MST;The BST Problem;A Verification Problem;CHECKBOTTLENECK(G, b) for each vertex u ? V[G] do color[u] ?WHITE u ?randomly chosen vertex in G DFS(u, b) //O(V+E) for each vertex u ?V[G] do if color[u] = WHITE then return FALSE return TRUE;Solve the BST Problem;Solve the Problem in Linear Time;Exercises