Algorithms, networks and linear programming
| English | 中文 | Pinyin |
|---|---|---|
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | 最小生成树 | zuì xiǎo shēng chéng shù |
Cheapest network or shortest route?
- A school must connect buildings with cable. The shortest route between two buildings and the cheapest whole network are different problems.
- This lesson studies minimum spanning tree 最小生成树: A connected cycle-free network joining every vertex with the smallest possible total edge weight.
Choose the mathematical structure
- Kruskal selects edges in increasing weight while avoiding cycles. Dijkstra updates shortest tentative distances from a start. Linear programming optimizes a linear objective over a feasible region; inspect vertices and integer restrictions when required.
- State the allowed inputs and units before calculating. An equation should express the relationship, not just record a calculator entry.
Which description correctly defines minimum spanning tree?
A connected cycle-free network joining every vertex with the smallest possible total edge weight.
Work through a checked case
- Check the result against the starting quantities. Substitute into the original relation, or compare the graph and numerical answer where appropriate.
For vertices A,B,C,D and edges AB=2,BC=3,AC=4,CD=1,BD=5, Kruskal selects CD,AB,BC for total 6. The shortest A-to-D route is A-B-C-D, also 6, but that equality is incidental. Maximize 3x+2y with x+y≤4,x≤2,x,y≥0: the best vertex is (2,2), value 10.
Algorithms, networks and linear programming
Kruskal selects edges in increasing weight while avoiding cycles
Compare the model with the worked case and explain one change.
Find the minimum spanning tree weight for the example network.
Kruskal selects edge weights 1,2,3 without a cycle, connecting every vertex: total 6.
Test a tempting shortcut
- A spanning tree has no cycles and joins all vertices. The largest single edge is not automatically excluded from every optimal solution. A shortest-path algorithm cannot replace a minimum-spanning-tree algorithm.
- When a shortcut fails, identify the assumption it breaks. Keep an exact value until the requested final rounding.
A shortest path between two vertices must also be a minimum spanning tree of the whole network. This claim is false. Explain which definition or assumption it violates.
Find the maximum of 3x+2y for the example feasible region.
Check the feasible vertices: (2,2) gives 3×2+2×2=10, the greatest objective value.
A shortest path between two vertices must also be a minimum spanning tree of the whole network.
A spanning tree has no cycles and joins all vertices. The largest single edge is not automatically excluded from every optimal solution. A shortest-path algorithm cannot replace a minimum-spanning-tree algorithm.
Interpret a new situation
- For critical paths, calculate earliest and latest event times and identify zero-float activities. State units and interpret the optimum. The existing archive has no D1 pairs, so these original tasks do not establish a reviewed D1 past-paper bank.
- A complete solution gives the mathematical result and explains what it means. Check that it is possible in the stated context.
How many edges does a spanning tree on 4 vertices have?
A tree on n vertices has n-1 edges, so four vertices need three.
Match each part of a complete solution to its purpose.
An assumption justifies the model; a check tests the result; interpretation connects it to the question.
Use this in your course
- edexcel IAL mathematics; official unit D1. Other-unit enrichment is identified in the scope review; it is not an extra cash-in requirement.
- Give the method before the final answer, and use the paper's calculator and formula rules. Review a wrong answer by locating the first invalid step.
A connected cycle-free network joining every vertex with the smallest possible total edge weight. Choose the relationship, show the method, check its assumptions and interpret the result.