Minimum Spanning Trees

Table of Contents

1 Reading

Read Algorithms 4.3

2 Video

Here is a video lecture for the slides below.

The video contains sections on

  1. Spanning Trees (0:21)
  2. Observations (1:04)
  3. Motivation (2:30)
  4. Two Approaches (5:00)
  5. Spanning tree via DFS (6:05)
  6. Second Approach (9:57)
  7. Example (10:51)
  8. Cycle Detection (12:06)
  9. Summary So Far (14:48)
  10. Getting to the Point (16:25)
  11. Prim's Algorithm Idea (17:24)
  12. Prim's Example (19:48)
  13. Analysis (24:29)
  14. Kruskal's Algorithm (25:10)
  15. Pseudocode (28:41)
  16. Kruskal's Example (29:58)

The Panopto viewer has table of contents entries for these sections: https://carleton.hosted.panopto.com/Panopto/Pages/Viewer.aspx?id=e24bd70f-e78d-4275-bc5f-ace00164e3bc

3 Slides

You can download the slides in pdf or PowerPoint.

4 Practice Problems1

  1. What is a spanning tree of a graph?
  2. What is a minimum spanning tree of a weighted graph?
  3. Under what conditions can a graph have nonunique minimum spanning trees?
  4. How would you find a maximum spanning tree of an edge-weighted graph?
  5. Given an MST for an edge-weighted graph \(G\), suppose that an edge in \(G\) that does not disconnect \(G\) is deleted. Describe how to find an MST of the new graph in time proportional to \(E\).
  6. Given an MST for an edge-weighted graph \(G\) and a new edge \(e\), describe how to find an MST of the new graph in time proportional to \(V\).
    1. Draw a weighted undirected graph with exactly 3 nodes that has exactly 0 minimum spanning trees.
    2. Draw a weighted undirected graph with exactly 3 nodes that has exactly 1 minimum spanning tree.
    3. Draw a weighted undirected graph with exactly 3 nodes that has exactly 2 minimum spanning trees.
    4. Draw a weighted undirected graph with exactly 3 nodes that has exactly 3 minimum spanning trees.
    5. Can a weighted undirected graph with 3 nodes have more than 3 minimum spanning trees? Why or why not?

5 Learning Block

  • Summary
    • Spanning tree: a subset of edges that connect all the nodes and form no cycles (i.e., a tree that spans the graph)
    • Minimum spanning tree: the spanning tree with the minimum total weight
    • Two (greedy) algorithms for finding minimum spanning tree
      • Prim's
        • Like Dijkstra's, incrementally expand a set of known nodes, select the lowest-cost node each time
        • Except cost is just the weight of the edge that would bring the node into the spanning tree
          • Instead of the cost of the path from source to the unknown node
      • Kruskal's
        • Consider edges in order of increasing weight
        • Output edge as part of minimum spanning tree if it would not introduce a cycle into spanning tree output so far
        • Use union-find data structure to efficiently detect cycles

Footnotes:

1

Solutions:

  1. A tree of edges that includes every vertex. Spanning trees are not possible for disconnected graphs; in that case, a spanning forest is required.
  2. Of all of the spanning trees of a graph, a minimum spanning tree is one whose total edge weight is least.
  3. There are multiple spanning trees of equal minimum weight.
  4. Negative the weight of each edge would be one approach.
  5. If the edge in not in the MST, then the old MST is an MST of the updated graph. Otherwise, deleting the edge from the MST leaves two connected components (i.e., two separate pieces of the graph). Add the minimum weight edge with one vertex in each component.
  6. Adding edge \(e\) to the MST creates a unique cycle. Delete the maximum weight edge on this cycle.
    1. Any unconnected, weighted, undirected graph
    2. Solution needs to have either 2 or 3 non-self edges and if it has 3 non-self edges, then no two can have the same weight
    3. Graph needs 2 non-self edges, with exactly 2 having the same weight and the third edge having a lower weight
    4. Graph needs 3 non-self edges, all with the same weight
    5. A 3-node graph can only have 3 spanning trees because it takes 2 edges (the number of nodes minus 1) to create a spanning tree. If the nodes are A, B, and C, the only possible spanning trees are:
      • (A,B), (A,C)
      • (B,C), (A,C)
      • (A,B), (B,C)