Algorithms, networks and linear programming · Algoritmos, redes y programación lineal
| English | Español |
|---|---|
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | árbol generador mínimo |
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? · ¿Cuál descripción define correctamente el árbol generador mínimo?
A connected cycle-free network joining every vertex with the smallest possible total edge weight. · Una red conexa sin ciclos que une cada vértice con el peso total de arista más pequeño posible.
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 y programación lineal
Kruskal selects edges in increasing weight while avoiding cycles · Kruskal selecciona aristas en orden de peso creciente evitando ciclos
Compare the model with the worked case and explain one change. · Compara el modelo con el caso resuelto y explica un cambio.
Find the minimum spanning tree weight for the example network. · Encontrar el peso del árbol generador mínimo para la red de ejemplo.
Kruskal selects edge weights 1,2,3 without a cycle, connecting every vertex: total 6. · Kruskal selecciona pesos de aristas 1,2,3 sin formar ciclos, conectando cada vértice: 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. · Encontrar el máximo de 3x+2y para la región factible de ejemplo.
Check the feasible vertices: (2,2) gives 3×2+2×2=10, the greatest objective value. · Verificar los vértices factibles: (2,2) da 3×2+2×2=10, el mayor valor objetivo.
A shortest path between two vertices must also be a minimum spanning tree of the whole network. · Un camino más corto entre dos vértices también debe ser un árbol generador mínimo de toda la red.
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. · Un árbol generador no tiene ciclos y une todos los vértices. La arista simple más grande no se excluye automáticamente de todas las soluciones óptimas. Un algoritmo de camino más corto no puede reemplazar a un algoritmo de árbol generador mínimo.
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? · ¿Cuántas aristas tiene un árbol generador sobre 4 vértices?
A tree on n vertices has n-1 edges, so four vertices need three. · Un árbol sobre n vértices tiene n-1 aristas, por lo tanto cuatro vértices necesitan tres.
Match each part of a complete solution to its purpose. · Emparejar cada parte de una solución completa con su propósito.
An assumption justifies the model; a check tests the result; interpretation connects it to the question. · Una suposición justifica el modelo; una comprobación verifica el resultado; la interpretación lo conecta con la pregunta.
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.