Comment relier toutes les villes d'une région par un réseau de fibre optique au moindre coût ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

Ma commune a été raccordée à la fibre optique l'an dernier, et je me suis demandé comment les opérateurs choisissent où poser les câbles. Il faut relier tout le monde, mais chaque kilomètre coûte cher. En NSI, j'ai découvert l'algorithme de Kruskal, un algorithme glouton qui, contrairement à beaucoup d'autres, donne toujours la meilleure solution.

L'enjeu et les notions du programme

Dénombrer les arbres couvrants pour mesurer la difficulté, et justifier qu'un algorithme glouton est ici optimal.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   On connaît le coût de pose d'un câble entre chaque paire de villes. On veut que toutes les villes soient reliées, directement ou non, pour un coût total minimal. Problématique : comment choisir les câbles ?

2. 2. Mathématiques : la forme de la solution

   4 min

   Un réseau de coût minimal n'a pas de cycle : si un cycle existait, on pourrait retirer un câble du cycle sans déconnecter personne et diminuer le coût. Un graphe connexe sans cycle est un arbre. Un arbre à $n$n sommets a exactement $n-1$n-1 arêtes (par récurrence : on retire une feuille et son arête).

   Combien d'arbres possibles ? La formule de Cayley (admise) donne $n^{n-2}$nⁿ⁻² arbres sur $n$n villes numérotées : 3 pour 3 villes, 16 pour 4, 125 pour 5, $10^8$10⁸ pour 10, et $20^{18}\approx 2,6\times 10^{23}$20¹⁸≈2,6×10²³ pour 20. Les essayer tous est impossible.

   Pourquoi le glouton fonctionne : supposons qu'un câble $e$e, le moins cher reliant deux parties du réseau, ne soit pas dans une solution optimale $T$T. En ajoutant $e$e à $T$T, on crée un cycle, qui contient un autre câble $f$f reliant aussi ces deux parties, plus cher ou au même prix. Remplacer $f$f par $e$e donne un arbre de coût inférieur ou égal : on peut donc toujours inclure $e$e.

3. 3. NSI : l'algorithme de Kruskal

   3 min

   On trie les câbles par coût croissant. On les examine un par un : on garde un câble s'il relie deux villes qui ne sont pas encore connectées, on le rejette s'il créerait un cycle. On s'arrête après $n-1$n-1 câbles.

   Pour savoir rapidement si deux villes sont déjà connectées, on maintient des groupes de villes (structure « union-find »). Le coût est dominé par le tri : environ $m\log m$mlog m pour $m$m câbles. Le même problème se pose pour les réseaux électriques, les canalisations ou le regroupement de données en catégories.

4. 4. Conclusion

   1,5 min

   Le réseau le moins cher est un arbre à $n-1$n-1 câbles, choisi parmi $n^{n-2}$nⁿ⁻² possibles. L'algorithme de Kruskal le trouve en prenant les câbles du moins cher au plus cher, et un argument d'échange prouve qu'il est optimal. J'ouvre sur l'algorithme de Prim, qui fait croître l'arbre à partir d'une ville.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Confondre arbre couvrant minimal et plus court chemin entre deux villes.
• Oublier de tester la création d'un cycle.
• Croire que tout algorithme glouton est optimal.

Revoir les notions

• Graphes et marches aléatoires (Terminale maths expertes) →
• Combinatoire et dénombrement (Terminale spé maths) →

Autres questions : graphes et réseaux

• Comment un GPS trouve-t-il le plus court chemin sans essayer tous les itinéraires ?
• Comment classer les pages du web par importance en ne regardant que les liens entre elles ?
• Peut-on parcourir tous les ponts d'une ville une seule fois chacun ? Le problème des ponts de Königsberg
• Est-il vrai que tout le monde sur Terre est relié à n'importe qui par une chaîne de six connaissances ?

Toutes les questions maths-nsi →