Algorithms, networks and linear programming · Algoritmos, redes e programação linear
| English | Português |
|---|---|
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | árvore geradora mínima |
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? · Qual descrição define corretamente árvore geradora mínima?
A connected cycle-free network joining every vertex with the smallest possible total edge weight. · Uma rede conectada sem ciclos que une todos os vértices com o menor peso total possível das arestas.
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 · Algoritmos, redes e programação linear
Kruskal selects edges in increasing weight while avoiding cycles · Kruskal seleciona arestas em ordem crescente de peso evitando ciclos
Compare the model with the worked case and explain one change. · Compare o modelo com o caso resolvido e explique uma mudança.
Find the minimum spanning tree weight for the example network. · Encontre o peso da árvore geradora mínima para a rede de exemplo.
Kruskal selects edge weights 1,2,3 without a cycle, connecting every vertex: total 6. · Kruskal seleciona pesos de aresta 1,2,3 sem formar ciclos, conectando todos os vértices: 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. · Encontre o máximo de 3x+2y para a região viável de exemplo.
Check the feasible vertices: (2,2) gives 3×2+2×2=10, the greatest objective value. · Verifique os vértices viáveis: (2,2) resulta em ⟨⟩3×2+2×2=10, o maior valor objetivo.
A shortest path between two vertices must also be a minimum spanning tree of the whole network. · O caminho mais curto entre dois vértices deve ser também uma árvore geradora mínima de toda a rede.
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. · Uma árvore geradora não possui ciclos e conecta todos os vértices. A maior aresta individual não é automaticamente excluída de todas as soluções ótimas. Um algoritmo de caminho mais curto não pode substituir um algoritmo de árvore geradora mínima.
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? · Quantas arestas tem uma árvore geradora sobre 4 vértices?
A tree on n vertices has n-1 edges, so four vertices need three. · Uma árvore sobre n vértices tem n-1 arestas, então quatro vértices precisam de três.
Match each part of a complete solution to its purpose. · Associe cada parte de uma solução completa ao seu propósito.
An assumption justifies the model; a check tests the result; interpretation connects it to the question. · Uma suposição justifica o modelo; uma verificação testa o resultado; a interpretação conecta-o à pergunta.
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.