Algorithms, networks and linear programming
| English | Français |
|---|---|
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | arbre couvrant minimal |
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.
Réseau le moins cher ou itinéraire le plus court ?
- Une école doit relier des bâtiments par câbles. L'itinéraire le plus court entre deux bâtiments et le réseau le moins cher sont des problèmes différents.
- Cette leçon étudie l'arbre couvrant minimal : un réseau connexe sans cycle reliant chaque sommet avec le poids total d'arêtes le plus petit possible.
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.
Choisissez la structure mathématique
- Kruskal sélectionne les arêtes par ordre croissant de poids tout en évitant les cycles. Dijkstra met à jour les distances temporaires les plus courtes depuis un point de départ. La programmation linéaire optimise une fonction objectif linéaire sur une région réalisable ; inspectez les sommets et les restrictions entières si nécessaire.
- Énoncez les entrées autorisées et les unités avant de calculer. Une équation doit exprimer la relation, et non simplement enregistrer une saisie de calculatrice.
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.
Travaillez à travers un cas vérifié
- Vérifiez le résultat par rapport aux quantités de départ. Substituez dans la relation originale, ou comparez le graphique et la réponse numérique là où c'est approprié.
Pour les sommets A,B,C,D et les arêtes AB=2, BC=3, AC=4, CD=1, BD=5, Kruskal sélectionne CD, AB, BC pour un total de 6. L'itinéraire le plus court de A à D est A-B-C-D, également 6, mais cette égalité est fortuite. Maximisez 3x+2y avec x+y≤4, x≤2, x,y≥0 : le meilleur sommet est (2,2), valeur 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.
Testez un raccourci tentant
- Un arbre couvrant n'a pas de cycles et relie tous les sommets. La plus grande arête unique n'est pas automatiquement exclue de toute solution optimale. Un algorithme de chemin le plus court ne peut remplacer un algorithme d'arbre couvrant minimal.
- Lorsqu'un raccourci échoue, identifiez l'hypothèse qu'il viole. Conservez une valeur exacte jusqu'au dernier arrondi demandé.
Un chemin le plus court entre deux sommets doit aussi être un arbre couvrant minimal de tout le réseau. Cette affirmation est fausse. Expliquez quelle définition ou quelle hypothèse elle viole.
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.
Interprétez une nouvelle situation
- Pour les chemins critiques, calculez les temps d'événement les plus précoces et les plus tardifs et identifiez les activités à flot nul. Énoncez les unités et interprétez l'optimum. L'archive existante ne contient aucune paire D1, donc ces tâches originales n'établissent pas une banque d'épreuves passées révisées D1.
- Une solution complète fournit le résultat mathématique et explique sa signification. Vérifiez qu'elle est réalisable dans le contexte indiqué.
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.
Utilisez ceci dans votre cursus
- Mathématiques IAL Edexcel ; unité officielle D1. L'enrichissement hors unité est identifié dans l'examen du périmètre ; ce n'est pas une exigence supplémentaire pour le gain de points.
- Présentez la méthode avant la réponse finale, et respectez les règles de calculatrice et de formules du sujet. Revoir une réponse erronée consiste à localiser la première étape invalide.
Un réseau connexe sans cycle reliant chaque sommet avec le poids total d'arêtes le plus faible possible. Choisissez la relation, montrez la méthode, vérifiez ses hypothèses et interprétez le résultat.