Understanding Minimum Spanning Trees in Graph Theory

Exploring the concept of minimum spanning trees in undirected, weighted graphs. A spanning tree is a connected acyclic subgraph that includes all vertices of the original graph. The Minimum Spanning Tree (MST) problem involves finding the tree with the smallest total edge weight. The cycle property of MSTs is also discussed, highlighting the relationship between edges in the tree and potential cycles. Examples and visual representations further elucidate these fundamental graph theory concepts.

• Minimum Spanning Trees
• Graph Theory
• MST Problem
• Cycle Property
• Acyclic Subgraph

eva_575 Follow

Uploaded on Oct 11, 2024 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

Presentation Transcript

1. Lecture 15 Minimum Spanning Trees CS 161 Design and Analysis of Algorithms Ioannis Panageas

2. Spanning Tree Definition: We are given an undirected, weighted graph ?. A spanning tree of ? is a connected acyclic (tree) subgraph of ?that includes all the vertices of ?(spanning). OAK 10 1 MIA 6 LA 7 9 3 BOS NYC 4 5 8 2 DC ATL Design and Analysis of Algorithms

3. Spanning Tree Definition: We are given an undirected, weighted graph ?. A spanning tree of ? is a connected acyclic (tree) subgraph of ?that includes all the vertices of ?(spanning). OAK 10 1 MIA 6 LA 7 9 3 BOS NYC 4 5 8 2 DC ATL Design and Analysis of Algorithms

4. Spanning Tree Definition: We are given an undirected, weighted graph ?. A spanning tree of ? is a connected acyclic (tree) subgraph of ?that includes all the vertices of ?(spanning). OAK 10 1 MIA 6 LA 7 9 3 BOS NYC 4 5 8 2 DC ATL Design and Analysis of Algorithms

5. Spanning Tree Definition: We are given an undirected, weighted graph ?. A spanning tree of ? is a connected acyclic (tree) subgraph of ?that includes all the vertices of ?(spanning). OAK 10 1 MIA 6 LA 7 9 3 BOS Not a spanning tree. It is not spanning (MIA). NYC 4 5 8 2 DC ATL Design and Analysis of Algorithms

6. Spanning Tree Definition: We are given an undirected, weighted graph ?. A spanning tree of ? is a connected acyclic (tree) subgraph of ?that includes all the vertices of ?(spanning). OAK 10 1 MIA 6 LA 7 9 3 BOS Not a spanning tree. It is not a tree (cycle). NYC 4 5 8 2 DC ATL Design and Analysis of Algorithms

7. Minimum Spanning Tree Problem: We are given an undirected, weighted graph ?, find the minimum spanning tree (MST). OAK 10 1 MIA 6 LA 7 9 3 BOS NYC 4 5 8 2 DC ATL Design and Analysis of Algorithms

8. Minimum Spanning Tree Cycle Property Let ? be a minimum spanning tree of a weighted graph ?. Let ? be an edge of ? that is not in ?and ? let be the cycle formed by ? with ?. OAK 10 1 MIA 6 LA 7 9 3 BOS It holds that: For every edge ? of ?, ???? ? ? ???? ? ? . NYC 4 5 8 2 DC ATL Design and Analysis of Algorithms

9. Minimum Spanning Tree Cycle Property Let ? be a minimum spanning tree of a weighted graph ?. Let ? be an edge of ? that is not in ?and ? let be the cycle formed by ? with ?. OAK 10 1 MIA 6 LA 7 9 3 BOS It holds that: For every edge ? of ?, ???? ? ? ???? ? ? . NYC 4 5 8 2 ? Example 1: Cycle LA, DC, NYC, OAK ? ? = 8 1,6,4 (rest of weights) DC ATL Design and Analysis of Algorithms

10. Minimum Spanning Tree Cycle Property Let ? be a minimum spanning tree of a weighted graph ?. Let ? be an edge of ? that is not in ?and ? let be the cycle formed by ? with ?. OAK 10 1 MIA 6 LA 7 9 3 BOS It holds that: For every edge ? of ?, ???? ? ? ???? ? ? . NYC 4 5 8 2 Example 2: Cycle BOS, ATL, NYC ? ? = 5 2,3 (rest of weights) DC ATL Design and Analysis of Algorithms

11. Minimum Spanning Tree Cycle Property For the sake of contradiction: 8 f 4 9 6 2 3 e Assume there exist ?,? so that 7 8 7 ???? ? ? > ???? ?(?) Replacing ? with ? yields a better spanning tree 8 f 4 9 6 2 3 e 7 8 7 Design and Analysis of Algorithms

12. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

13. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

14. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

15. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

16. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

17. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

18. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

19. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

20. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

21. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

22. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

23. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

24. Kruskals Algorithm for MSTs Idea 1: Greedy approach. Consider the edges from smaller weight to larger. Include each edge in the current solution as long as it does not create a cycle, otherwise discard it. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

25. Kruskals Algorithm for MSTs Why Kruskal s algo works: General argument. Suppose there is a better solution. Assume the ? edges of ? are ordered in increasing order of weights, i.e., w1 ?2 ??. ? has also ? vertices. Let ?1, ,?? 1 be the weight values of the edges in increasing order of the minimum spanning tree ? . Let ?1, ,?? 1be the weight values of the edges in increasing order of Kruskal s spanning tree ?. Design and Analysis of Algorithms

26. Kruskals Algorithm for MSTs Why Kruskal s algo works: General argument. Suppose there is a better solution. Assume the ? edges of ? are ordered in increasing order of weights, i.e., w1 ?2 ??. ? has also ? vertices. Let ?1, ,?? 1 be the weight values of the edges in increasing order of the minimum spanning tree ? . Let ?1, ,?? 1be the weight values of the edges in increasing order of Kruskal s spanning tree ?. There is an index ?, so that ?? < ??. We add edge with value ??in ? , we create a cycle ?. Design and Analysis of Algorithms

27. Kruskals Algorithm for MSTs Why Kruskal s algo works: General argument. Suppose there is a better solution. Assume the ? edges of ? are ordered in increasing order of weights, i.e., w1 ?2 ??. ? has also ? vertices. Let ?1, ,?? 1 be the weight values of the edges in increasing order of the minimum spanning tree ? . Let ?1, ,?? 1be the weight values of the edges in increasing order of Kruskal s spanning tree ?. There is an index ?, so that ?? < ??. We add edge with value ??in ? , we create a cycle ?. If ?? is in ?, we remove it and create a spanning tree smaller than T (contradiction). Design and Analysis of Algorithms

28. Kruskals Algorithm for MSTs Why Kruskal s algo works: General argument. Suppose there is a better solution. Assume the ? edges of ? are ordered in increasing order of weights, i.e., w1 ?2 ??. ? has also ? vertices. Let ?1, ,?? 1 be the weight values of the edges in increasing order of the minimum spanning tree ? . Let ?1, ,?? 1be the weight values of the edges in increasing order of Kruskal s spanning tree ?. There is an index ?, so that ?? < ??. We add edge with value ??in ? , we create a cycle ?. If ?? is in ?, we remove it and create a spanning tree smaller than T (contradiction). If ?? not in ?, by cycle property, ?? is the largest value from edges in C. Kruskal would not have chosen ?? (contradiction). Design and Analysis of Algorithms

29. Prims Algorithm for MSTs Idea 2: Similar to Dijkstra s algorithm. We pick an arbitrary vertex ?. We build the tree by adding one new vertex at a time. Each vertex ? has label ? ? smallest weight of an edge connecting ? to a vertex in the built tree. At each step: We add to the current tree the vertex ? with the smallest ?[?] and the corresponding incident to ? edge. We update the labels of the vertices adjacent to ?. Design and Analysis of Algorithms

30. Prims Algorithm for MSTs Idea 2: Similar to Dijkstra s algorithm. We pick an arbitrary vertex ?. At each step: We add to the current tree the vertex ? with the smallest ?[?] and the corresponding incident to ? edge. We update the labels of the vertices adjacent to ?. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

31. Prims Algorithm for MSTs Idea 2: Similar to Dijkstra s algorithm. We pick an arbitrary vertex ?. At each step: We add to the current tree the vertex ? with the smallest ?[?] and the corresponding incident to ? edge. We update the labels of the vertices adjacent to ?. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

32. Prims Algorithm for MSTs Idea 2: Similar to Dijkstra s algorithm. We pick an arbitrary vertex ?. At each step: We add to the current tree the vertex ? with the smallest ?[?] and the corresponding incident to ? edge. We update the labels of the vertices adjacent to ?. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

33. Prims Algorithm for MSTs Idea 2: Similar to Dijkstra s algorithm. We pick an arbitrary vertex ?. At each step: We add to the current tree the vertex ? with the smallest ?[?] and the corresponding incident to ? edge. We update the labels of the vertices adjacent to ?. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

34. Prims Algorithm for MSTs Idea 2: Similar to Dijkstra s algorithm. We pick an arbitrary vertex ?. At each step: We add to the current tree the vertex ? with the smallest ?[?] and the corresponding incident to ? edge. We update the labels of the vertices adjacent to ?. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

35. Prims Algorithm for MSTs Idea 2: Similar to Dijkstra s algorithm. We pick an arbitrary vertex ?. At each step: We add to the current tree the vertex ? with the smallest ?[?] and the corresponding incident to ? edge. We update the labels of the vertices adjacent to ?. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

36. Prims Algorithm for MSTs Idea 2: Similar to Dijkstra s algorithm. We pick an arbitrary vertex ?. At each step: We add to the current tree the vertex ? with the smallest ?[?] and the corresponding incident to ? edge. We update the labels of the vertices adjacent to ?. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

37. Prims Algorithm for MSTs Idea 2: Similar to Dijkstra s algorithm. We pick an arbitrary vertex ?. At each step: We add to the current tree the vertex ? with the smallest ?[?] and the corresponding incident to ? edge. We update the labels of the vertices adjacent to ?. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

38. Prims Algorithm for MSTs Idea 2: Similar to Dijkstra s algorithm. We pick an arbitrary vertex ?. At each step: We add to the current tree the vertex ? with the smallest ?[?] and the corresponding incident to ? edge. We update the labels of the vertices adjacent to ?. 8 B G 4 E 5 9 F 1 6 3 C 11 7 2 H D 12 10 A Design and Analysis of Algorithms

39. Prims Algorithm for MSTs Pseudocode: Starting vertex Initialization Relaxation Design and Analysis of Algorithms

40. Prims Algorithm for MSTs Pseudocode: Starting vertex Initialization Relaxation Design and Analysis of Algorithms

41. Prims Algorithm for MSTs Pseudocode: Starting vertex Initialization Relaxation ?( ??) Design and Analysis of Algorithms

42. Prims Algorithm for MSTs Pseudocode: Starting vertex Initialization Relaxation Design and Analysis of Algorithms