cut property
The fact that, for any way of splitting a graph's vertices into two groups, the cheapest edge crossing between the groups belongs to some minimum spanning tree.
In more detail
It is the exchange argument behind every greedy MST algorithm: if a tree skipped that edge, swapping it in for a dearer crossing edge would make the tree cheaper. Prim's algorithm applies it to the cut between the tree so far and everything else.
Related terms
- minimum spanning tree — The spanning tree of a weighted, connected graph whose edges have the smallest possible total weight.
- exchange argument — A proof technique for greedy algorithms: show that any optimal solution can be changed, one swap at a time, to include the greedy choice without getting worse.
- Prim's algorithm — An algorithm that builds a minimum spanning tree by growing it from one start vertex, always adding the cheapest edge leading out of the tree.
Taught in
- Recognising The Common Growth Rates — Algorithms & Data Structures for Working Engineers
- Minimum Spanning Trees: Kruskal And Prim — Algorithms & Data Structures for Working Engineers
- Divide And Conquer And The Recurrence — Algorithms & Data Structures for Working Engineers
- Backtracking: Search With Pruning — Algorithms & Data Structures for Working Engineers
- Recognising The Pattern — Algorithms & Data Structures for Working Engineers