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 · Kruskal算法按权重递增选择边并避免形成回路
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. · Kruskal 算法选择不构成回路的边权 1,2,3，连接所有顶点：总权重 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. · 求3x+2y在示例可行域内的最大值。
Check the feasible vertices: (2,2) gives 3×2+2×2=10, the greatest objective value. · 检查可行顶点：(2,2) 给出 3×2+2×2=10，为最大的目标函数值。
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? · 含4个顶点的生成树有多少条边？
A tree on n vertices has n-1 edges, so four vertices need three. · 含n个顶点的树有n-1条边，因此四个顶点需要三条。
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 further 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.