Les graphes au service de la course à pied

Il se peut aussi que la course à pied soit au service des graphes car il se murmure que je réfléchis parfois à des maths en courant.

Un ami expatrié dans un pays chaud s’entraîne régulièrement dans une zone urbaine que voici :

Afin de l’aider à minimiser l’énorme potentiel de ce quartier en matière de lassitude, je me suis demandé quel parcours de jogging aurait la distance maximale, sans jamais repasser deux fois par la même rue.  Tout ça me rappelle les graphes et la notion de chaîne eulérienne mais — presque promis — je n’y avais pas songé avant.

Bref.

L’ensemble des rues forme un graphe. On numérote les intersections, c’est-à-dire les sommets du graphe. Les bouts de rue en sont les arêtes. Voici donc :

Il existe des algorithmes subtils et très performants pour chercher une solution mais ils sont assez difficiles (au programme de la spécialité ISN en Terminale S). On peut aussi utiliser sa tête mais c’est fatigant. Voici un algorithme — pas subtil… — écrit en Python qui fait partir notre ami coureur d’un sommet aléatoire et lui fait parcourir aléatoirement les arêtes jusqu’à ce que son chemin ne puisse se poursuivre sur une arête non parcourue. Le tout est exécuté un grand nombre de fois, disons ici 100 000 répétitions. Voici le script :

Ce qui renvoie, par exemple :

distance maximale : 6.287000000000002 m
parcours correspondant : [22, 12, 11, 21, 31, 32, 22, 23, 13, 14, 24, 34, 33, 23, 24, 25, 15, 16, 26, 36, 35, 25, 26, 27, 37, 38, 28, 18, 17, 27, 28]
durée du calcul : 9.988758087158203 s

Vous pouvez alors parcourir le chemin eulérien optimal ici trouvé !

Merci qui ?