Theorem 1 ten G=(V, e)be a connected, undirected graph with a real-valued weight function w defined on e 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 such that for any edge e=u, v)in a fu,v cSor u,Vc (V-S) et(x, y) be a light edge crossing(S,V-S) Then, edge(x, y) is safe for A Proof: Let Tont be a minimum spanning tree ( Blue) A--a subset of Topt and(x, y)--a light edge crossing(S, v-S) If(x, y)is not safe then(x, y)is not in T (See the red edge in Figure) There must be another edge(x',y)in Topt crossing(s,v-s). Green) We can replace(x, ,y)in Topt with(x,y) and get anothertree Since(x, y) is light, T,opt is also optimal 16
16 Theorem 1 Given: – G=(V, E) be a connected, undirected graph with a real-valued weight function w defined on E. – 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 such that for any edge e=(u, v) in A, {u, v} S or {u, v} (V-S). – Let (x, y) be a light edge crossing (S,V-S). Then, edge (x, y) is safe for A. Proof: Let Topt be a minimum spanning tree. (Blue) A --a subset of Topt and (x, y)-- a light edge crossing (S, V-S) • If (x, y) is NOT safe, then (x, y) is not in T. – (See the red edge in Figure) • There MUST be another edge (x’, y’) in Topt crossing (S, V-S).(Green) • We can replace (x’, y’) in Topt with (x, y) and get another tree T’opt • Since (x, y) is light , T’opt is also optimal. 1 2 1 1 1 1 1 1
Corollary Given: 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 c be a connected component (tree)in the forest GA=(,A) t (u, v) be a light edge(shortest among all edges connecting C with others components) connecting C to some other component in g Then, edge(u, v) is safe for A. For Kruskal's algorithm) 17
17 Corollary Given: 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 C be a connected component (tree) in the forest GA=(V, A). – Let (u, v) be a light edge (shortest among all edges connecting C with others components) connecting C to some other component in GA. • Then, edge (u,v) is safe for A. (For Kruskal’s algorithm)
The algorithms of Kruskal and prim The two algorithms are elaborations of the generic algorithm They each use a specific rule to determine a safe edge in line 3 of GENERIC MSt In Kruskal's algorithm The set a is a forest The safe edge added to a is always a least-weight edge in the graph that connects two distinct components In Prim's algorithm The set a forms a single tree The safe edge added to a is al ways a least- weight edge connecting the tree to a vertex not in the tree 18
18 The algorithms of Kruskal and Prim • The two algorithms are elaborations of the generic algorithm. • They each use a specific rule to determine a safe edge in line 3 of GENERIC_MST. • In Kruskal's algorithm, – The set A is a forest. – The safe edge added to A is always a least-weight edge in the graph that connects two distinct components. • In Prim's algorithm, – The set A forms a single tree. – The safe edge added to A is always a least-weight edge connecting the tree to a vertex not in the tree
Kruskal’ s Algorithn
Kruskal’s Algorithm 19
Complete Graph
4 1 2 3 2 1 3 5 3 4 2 5 6 4 4 10 A B C D E F G H I J Complete Graph