Spanning Trees and Minimal Spanning Trees with Applications Flashcards
What is a spanning tree?
A subset of edges in a connected undirected graph that connects all vertices without cycles.
How many edges does a spanning tree have?
|V| - 1, where V is the number of vertices.
What is a minimal spanning tree (MST)?
A spanning tree where the sum of edge weights is as small as possible.
What is the purpose of an MST?
To connect all vertices with minimum total edge weight, removing cycles and reducing redundancy.
Why are cycles bad in networks?
They cause repeated transmissions and bandwidth waste during routing.
What is flooding in networking?
A simple routing strategy where a node sends incoming messages to all outgoing ports except the source.
How does an MST prevent flooding?
Each node forwards messages along a unique path, avoiding repeated broadcasts.
What is the MST cycle property?
If an edge not in the MST is added, it forms a cycle; its weight must be ≥ all edges in that cycle.
What are the two main MST algorithms?
Prim’s Algorithm and Kruskal’s Algorithm.
How does Prim’s Algorithm work?
Starts with one node and grows the MST by adding the lightest edge connecting to an unseen node.
How does Kruskal’s Algorithm work?
Sorts all edges by weight and adds them if they don’t form a cycle.
What data structure is used in Kruskal’s Algorithm?
Disjoint Set (Union-Find).
What kind of graphs suit Prim’s Algorithm?
Dense graphs.
What kind of graphs suit Kruskal’s Algorithm?
Sparse graphs.
What is a routing table in MST routing?
A table at each node mapping destinations to the next hop along the MST.
What happens if a link in the MST fails?
A backup edge (not in the MST) may be reactivated to maintain connectivity.
Why is the term ‘minimal’ preferred over ‘minimum’?
Because there can be multiple spanning trees with the same minimal total weight.
What are real-world applications of MST?
Network routing, road/cable cost optimization, and approximation algorithms.
What condition must a graph satisfy to have a spanning tree?
It must be connected (no isolated vertices or components).
What is the weight of an MST?
The total sum of the weights of its edges.
