β Key Takeaways
A spanning tree of a connected graph must contain all vertices and be circuit-free, with exactly n-1 edges for n vertices. Kirchhoff's Matrix-Tree Theorem provides a powerful algebraic method to count spanning trees by computing any cofactor of a modified adjacency matrix. For weighted graphs, minimal spanning trees minimize total edge weight and can be found using Kruskal's algorithm (selecting least-weight edges without creating cycles) or Prim's algorithm (growing from a starting vertex by adding the least-weight connecting edge). Both algorithms are greedy and yield optimal minimal spanning trees, though multiple distinct minimal spanning trees may exist for the same graph.
π§ Quick Revision Questions
-
What is the formula for the number of edges to delete from a connected graph with n vertices and e edges to obtain a spanning tree?
-
In Kirchhoff's Matrix-Tree Theorem, how do you construct matrix M from the adjacency matrix of a graph?
-
What is the key difference between Kruskal's algorithm and Prim's algorithm for finding minimal spanning trees?
-
How many non-isomorphic spanning trees does a complete graph Kβ have?
-
If addition of an edge during Kruskal's algorithm produces a circuit, what should you do with that edge?