Correctness:prove by induction Proof plan:We will use induction to prove that at any point of time,the edges found are part of an MST. G2 a At any point of time,we've found some edges ME, 0 M connects vertices into groups G1,...,Gk. By induction,M belongs to some MST T. 11
Correctness: prove by induction ◼ Proof plan: We will use induction to prove that at any point of time, the edges found are part of an MST. ◼ At any point of time, we’ve found some edges 𝑀 ⊆ 𝐸, ❑ 𝑀 connects vertices into groups 𝐺1, … , 𝐺𝑘. ◼ By induction, 𝑀 belongs to some MST 𝑇. 11 𝐺1 𝐺2
Correctness:prove by induction Suppose Kruskal's algorithm picks e'in the next step,connecting,say,G1 and G2. ■ If e'ET,done.If e'T,adding e'into G2 T would produce a cycle. The cycle must cross the cut (G1,V-G1) 5 via at least one other edge e. ■ Since e'is the lightest one among all crossing edges,w(e')<w(e). Let T'=T-e+e',then w(T)<w(T). T'is also a spanning tree. Connected,and has n-1 edges. So T'is also an MST.Induction step done. 12
Correctness: prove by induction ◼ Suppose Kruskal’s algorithm picks 𝑒′ in the next step, connecting, say, 𝐺1 and 𝐺2 . ◼ If 𝑒 ′ ∈ 𝑇, done. If 𝑒 ′ ∉ 𝑇, adding 𝑒 ′ into 𝑇 would produce a cycle. ◼ The cycle must cross the cut (𝐺1, 𝑉 − 𝐺1) via at least one other edge 𝑒. ◼ Since 𝑒′ is the lightest one among all crossing edges, 𝑤 𝑒′ ≤ 𝑤(𝑒). ◼ Let 𝑇 ′ = 𝑇 − 𝑒 + 𝑒′, then 𝑤 𝑇 ′ ≤ 𝑤(𝑇). ◼ 𝑇 ′ is also a spanning tree. ❑ Connected, and has 𝑛 − 1 edges. ◼ So 𝑇 ′ is also an MST. Induction step done. 𝑒 𝑒′ 12 𝐺1 5 𝐺2
Implementing Kruskal's Algorithm: Initialization: Sort the edges E by weight ▣create{v}for each v∈V ▣T= for all edges (u,v)EE,in increasing order of weight: if adding (u,v)doesn't cause a cycle add edge (u,v)to T Question:What's not clearly specified yet? 13
Implementing Kruskal's Algorithm: ◼ Initialization: ❑ Sort the edges 𝐸 by weight ❑ create {𝑣} for each 𝑣 ∈ 𝑉 ❑ 𝑇 = {} ◼ for all edges 𝑢, 𝑣 ∈ 𝐸, in increasing order of weight: ❑ if adding (𝑢, 𝑣) doesn’t cause a cycle ◼ add edge (𝑢, 𝑣) to 𝑇 ◼ Question: What’s not clearly specified yet? 13