What you’ll work on
- Trees and minimum connector problems
- Flow problems
Start with the idea
A minimum spanning tree connects every vertex with least total edge weight and no cycle. Prim’s algorithm repeatedly connects a new vertex by the cheapest available edge.
A flow network has capacities, directions, source and sink. Flow conservation holds at intermediate vertices; a cut capacity provides an upper bound on source-to-sink flow.
A worked example
Edges AB=1, AC=4, BC=2, BD=5, CD=3. Find an MST.
- Select 1, 2, 3 without a cycle
- every vertex is connected.
Answer: AB, BC, CD, total 6.
Try one question
How many edges does a spanning tree on 7 vertices have?
Show answer and explanation
6.
A tree has one fewer edge than vertices.
Inside the collection
| Resource | Length | Practice | Answers |
|---|---|---|---|
| Learn and practise | 4 pages | 4 questions | Included |
| Apply and extend | 4 pages | 4 questions | Included |
| Topic checkpoint | 3 pages | 4 questions | Included |
Read on a device and work in an exercise book, or print the A4 PDFs. These files are not auto-marked digital quizzes.