CORNELL CS 211 - Minimal Spanning Trees (25 pages)

Previewing pages 1, 2, 24, 25 of 25 page document View the full content.
View Full Document

Minimal Spanning Trees



Previewing pages 1, 2, 24, 25 of actual document.

View the full content.
View Full Document
View Full Document

Minimal Spanning Trees

101 views


Pages:
25
School:
Cornell University
Course:
Cs 211 - Comps & Prog
Comps & Prog Documents
Unformatted text preview:

Minimal Spanning Trees Spanning Tree Assume you have an undirected graph G V E Spanning tree of graph G is tree T E R T V E Tree has same set of nodes All tree edges are graph edges Root of tree is R Think smallest set of edges needed to connect everything together Spanning trees 1 0 A B 2 G F I E C H A1 D Breadth first Spanning Tree 5 F B G 3 I E4 2 9 8 7 H D C 6 Depth first spanning tree Property 1 of spanning trees Graph G V E Spanning tree T V ET R For any edge c in G but not in T there is a simple cycle containing only edge c and edges in spanning tree A edge I H simple cycle is I H G I B G F I E C H edge H C simple cycle is H C B A G H Proof D Proof of Property 1 Edge is c goes u v If u is ancestor of v result is easy u v then v u form a cycle Otherwise there are paths root u and root v b c it is a tree Let p be the node furthest from root on both of these paths Now p u then u v then v p form a cycle A edge I H p is node G simple cycle is I H G I B G F I E C H D edge H C p is node A simple cycle is H C B A G H Useful lemma about trees In any tree T V E E V 1 Proof Useful lemma about trees In any tree T V E E V 1 Proof by induction on V If V 1 we have the trivial tree containing a single node and the result is obviously tree Assume result is true for all trees for which 1 V n and consider a tree S ES VS with V n Such a tree must have at least one leaf node removing the leaf node and edge incident on that node gives a smaller tree T with less than n nodes By inductive assumption ET VT 1 Since ES ET 1 and VS VT 1 the required result follow Converse also true an undirected graph G V E which 1 has a single connected component and 2 has E V 1 must be a tree Property 2 of spanning trees Graph G V E Spanning tree T V ET R For any edge c in G but not in T there is a simple cycle Y containing only edge c and edges in spanning tree Moreover inserting edge c into T and deleting any edge in Y gives another spanning tree T A B G F I E C H D edge H C simple cycle is H C B A G H adding H C to T and deleting A B gives another spanning tree Proof of Property 2 Outline T is a connected component Proof In T numbers of edges number of nodes 1 Proof Therefore from lemma earlier T is a tree Proof of Property 2 T is a connected component Otherwise assume node a is not reachable from node b in T In T there must be a path from b to a that contains edge s t In this path replace edge s t by the path in T obtained by deleting s t from the cycle Y which gives a path from b to a Contradiction thus a must be reachable from b In T numbers of edges number of nodes 1 Proof by construction of T and fact that T is a tree T is same as T with one edge removed one edge added Therefore from lemma T is a tree Building BFS DFS spanning trees dummy 1 0 A B 2 G F I E C H D Use sequence structure as before but put get edges not nodes Get edge s d from structure If d is not in done set add d to done set s d is in spanning tree add out edges d t to seq structure if t is not in done set Example BFS Queue dummy A A B A G A F A G A F B G B C Weighted Spanning Trees Assume you have an undirected graph V E with weights on each edge Spanning tree of graph G is tree V ET E Tree has same set of nodes All tree edges are graph edges Weight of spanning tree sum of tree edge weights Minimal Spanning Tree MST Any spanning tree whose weight is minimal In general a graph has several MST s Applications circuit board routing networking etc G T Example A B 2 9 5 G6 4 1 2 5 5 F C 4 6 3 I H 1 2 E 1 A B 2 9 5 G6 4 1 2 5 5 F C 4 6 3I H 1 2 D E Graph 1 D SSSP tree A B 2 9 5 G6 4 1 2 5 5 F C 6 3 I 4H 1 2 E 1 D Minimal spanning tree Caution in general SSSP tree is not MST Intuition 4 4 1 4 4 SSSP Tree 4 1 MSP SSSP fixed start node MST at any point in construction we have a bunch of nodes that we have reached and we look at the shortest distance from any one of those nodes to a new node Property 3 of minimal spanning trees 2 5 G6 4 1 2 5 5 F C 6 3 I 4H 1 2 E 1 D 9 Edge G H 5 Cycle edges G I I E E D H D all have weights less than G H Graph G V E Spanning tree T V E T R For any edge c in G but not in T there is a simple cycle Y containing only edge c and edges in spanning tree already proved Moreover weight of c must be greater than or equal to weight of any edge in this cycle Proof Property 3 of minimal spanning trees 2 5 G6 4 1 2 5 5 F C 6 3 I 4H 1 2 E 1 D 9 Edge G H 5 Cycle edges G I I E E D H D all have weights less than G H Graph G V E Spanning tree T V E T R Edge c weight of c must be greater than or equal to weight of any edge in this cycle Proof Otherwise let d be an edge on cycle with lower weight Construct T from T by removing c and adding d T is less weight than T so T not minimal Contradiction so d can t exist Building Minimal Spanning Trees Prim s algorithm simple variation of Dijkstra s SSSP algorithm Change Dijkstra s algorithm so the priority of bridge f n is length f n rather than minDistance f length f n Intuition Starts with any node …


View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Minimal Spanning Trees and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Minimal Spanning Trees and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?