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

Teach 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.

View worksheets & preview

Aspire to Power Learning · https://resources.aspiretopowerlearning.com.au/home-learning/topics/general-3-4-connectors-flow/

Check the starting point

  • Find the bottleneck capacity along a directed path.
  • Distinguish total connector weight from individual route length.

Show the idea

Capacities constrain a source-to-sink flow

Route 3 units through A and 2 through B. The cut consisting of A→T and S→B has capacity 5, proving this flow is maximum.
Select the diagram to view it at full size.

Route 3 units through A and 2 through B. The cut consisting of A→T and S→B has capacity 5, proving this flow is maximum.

Work through an example

Edges AB=1, AC=4, BC=2, BD=5, CD=3. Find an MST.

  1. Use Kruskal's method: list edges in increasing weight order AB=1, BC=2, CD=3, AC=4, BD=5.
  2. Choose AB and BC. Adding CD creates no cycle and connects the remaining vertex D.
  3. The selected three edges connect all four vertices, so they form a spanning tree. Its total weight is 1+2+3=6.
  4. Kruskal's rule selects the least available edge that does not create a cycle, giving a minimum spanning tree.

Answer: AB, BC, CD, total 6.

Teach in small steps

  1. Read the visual model together: Route 3 units through A and 2 through B. The cut consisting of A→T and S→B has capacity 5, proving this flow is maximum.
  2. Model this example aloud: A spanning tree connects 11 vertices. How many edges does it have? Guide: Every tree has one fewer edge than vertices. Result: 10.
  3. Let your learner choose the steps for a new situation: A directed network has S→A=6, A→T=4, S→B=3 and B→T=5. Find maximum flow and a matching cut. Ask which part of the model or rule carries over before checking the worked solution.
  4. After a short break, ask for an independent response: A cut has forward crossing capacities 5,4 and 8; a reverse crossing edge has capacity 6. Find the cut capacity. Compare both the method and conclusion with the checkpoint answers, then revisit any misconception.

Ask and listen

  • For triangle weights AB=4, AC=6 and BC=2, find the minimum spanning tree.
  • Why can a cheapest edge be rejected during minimum-spanning-tree construction?

Adapt the practice

More support

Start with this prerequisite: Find the bottleneck capacity along a directed path. Keep the visual visible. For the first guided problem, focus on this step: Every tree has one fewer edge than vertices.

More challenge

Try this application without looking at its answer: A network already carries flow 12 and has a cut of capacity 12. What does this prove? Then explain why the answer fits the stated domain or context.

Look for understanding

  • Your learner can complete this checkpoint and explain the method: A cut has forward crossing capacities 5,4 and 8; a reverse crossing edge has capacity 6. Find the cut capacity.
  • Your learner can justify or challenge this statement/question using the mathematical definitions: Why can a cheapest edge be rejected during minimum-spanning-tree construction?

Choose the next step

If either checkpoint needs prompting, repeat the worked model with changed values and revisit this caution: A cut gives an upper bound for flow; an actual feasible flow gives a lower bound. When both are secure, use the linked Apply and extend resource and relevant VCE Key Knowledge/Key Skills activity.

Put the idea into practice

The matching topic collection includes learn-and-practise, application and checkpoint PDFs with worked answers. Download the free preview to see representative pages.

Explore this topic’s worksheets