Minimum spanning tree
A minimum spanning tree (MST) is a special type of subgraph on a network that connects all the nodes together with the minimum possible total weight for the connections.
A minimum spanning tree is a type of tree. It does *not contain any cycles, and there is exactly one path between any two nodes in the tree.
Finding the minimum spanning tree is also known as the minimum connector problem.
Properties of a minimum spanning tree
Some important properties of a minimum spanning tree are:
- It includes all the nodes in the original network.
- It has exactly
N-1edges, whereNis the number of nodes in the network. - The total weight of the edges in the MST is the lowest possible.
- There are no cycles in the MST.
flashcards
| Question | Answer |
|---|---|
| What is a minimum spanning tree (MST)? | A special subgraph that connects all nodes in a network with the minimum possible total weight. |
| What is another name for the problem of finding a minimum spanning tree? | The minimum connector problem. |
| How many edges does a minimum spanning tree have? | Exactly |
| Does a minimum spanning tree contain any cycles? | No, it does not contain any cycles. |
| How many paths exist between any two nodes in a minimum spanning tree? | Exactly one path. |