088 Réseau routier

 

Problème de théorie des graphes : une réponse figure aussi dans "problèmes pour mathématiciens petits et grands" ( Halmos ).

 

Supposons que l'on sache démontrer que le réseau minimal doive passer par le centre O du carré, ce que je laisse à mes petits camarades de jeu :-), alors on se ramène à un problème classique : trouver R de façon à minimiser la somme des distances RA+RD+RO (et symétriquement S qui minimise SB+SC+SO).
Puisque les trois angles du triangle ADO sont inférieurs à 120°, R est le point de Torricelli du triangle ADO, c'est-à-dire l'unique point duquel on voit chaque côté du triangle sous un angle de 120°.
On obtient ainsi un réseau (RA, RD, RS, SB, SC) de longueur totale (1+sqrt(3)) fois le côté du carré, donc plus petit que le réseau des diagonales, qui mesure 2*sqrt(2) fois le côté du carré.