Foundation to VCE • Explore the maths library • Try a free sample
VCE General Mathematics Units 3–4 · Discrete mathematics

Minimum connectors and maximum flow

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.

3 printable resources11 pages12 questionsWorked answers
A$3.90Planned launch price · including GST
One household or one teacher’s own classes
Preview available. Checkout opens soon.The full topic collection is prepared. Explore a sample before choosing.

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.

  1. Select 1, 2, 3 without a cycle
  2. 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

ResourceLengthPracticeAnswers
Learn and practise4 pages4 questionsIncluded
Apply and extend4 pages4 questionsIncluded
Topic checkpoint3 pages4 questionsIncluded

Read on a device and work in an exercise book, or print the A4 PDFs. These files are not auto-marked digital quizzes.