Lecture 8 Greedy Approach Minimum spanning tree How to design greedy algorithms
• Minimum spanning tree • How to design greedy algorithms Lecture 8 Greedy Approach
Roadmap Minimum spanning tree How to design greedy algorithms a Change-making problem a Activity selection problem n Huffman code a Knapsack problem
Roadmap • Minimum spanning tree • How to design greedy algorithms ‣ Change-making problem ‣ Activity selection problem ‣ Huffman code ‣ Knapsack problem
MST Given. Undirected graph G with positive edge weights (connected) Def. A spanning tree of G is a subgraph T that is connected and 5 16 10 10 not connected not acyclic
MST Given. Undirected graph G with positive edge weights (connected). Def. A spanning tree of G is a subgraph T that is connected and acyclic. not connected 23 10 21 14 24 16 4 18 9 7 11 8 5 6 23 10 21 14 24 16 4 18 9 7 11 8 5 6 not acyclic
Minimum spanning tree Problem: Min Spanning Input: A connected undirected graphG=(V, E)in thich each edge has a weighted lenath Output: A spanning tree of G that has minimum cost
Minimum spanning tree Problem: MinSpanning Input: A connected undirected graph G = (V , E ) in which each edge has a weighted length Output: A spanning tree of G that has minimum cost a b h c i d e g f 4 2 7 4 10 9 8 11 8 7 1 2 6 a 14 b h c i d e g f 4 2 7 4 10 9 8 11 8 7 1 2 6 14
Cut property Definition: Cut A cut (S, T s a partition of the vertex set v into two subsets s and t heorem(Cut property)Given any cut, the crossing edge of min weight is in some MST
Cut property a b h c i d e g f 4 2 7 4 10 9 8 11 8 7 1 2 6 14 Definition: Cut A cut {S,T} is a partition of the vertex set V into two subsets S and T. Theorem (Cut property)Given any cut, the crossing edge of min weight is in some MST