H153. Randonnées bourbonnaises (2ème épisode) Imprimer
H. Graphes et circuits

calculator_edit.png  

La Sologne  bourbonnaise  comporte un réseau de k sentiers de randonnée pédestre qui relient 7 villages avec  les caractéristiques suivantes :
-    deux villages  quelconques sont reliés entre eux par un sentier au plus,
-    il n’y a pas de sentier qui relie un village à lui-même (absence de boucle),
-    les sentiers sont balisés avec des traits horizontaux de couleurs toutes différentes. Deux sentiers distincts peuvent se croiser en dehors des villages mais on respecte le balisage du sentier lorsque celui-ci croise un ou plusieurs autres sentiers.
-    le réseau contient le plus grand nombre possible de sentiers sans qu'il y ait deux circuits disjoints (c'est à dire sans village commun à deux circuits).
Déterminer k et donner une représentation graphique possible du réseau. [**]
Pour les plus courageux:
Avec n villages, déterminer le nombre maximal de sentiers d'un réseau qui ne contient pas deux circuits disjoints.[****]

 Solution


pdfJean Moreau de Saint Martin et pdfBernard Vignes ont résolu tout ou partie du problème.
Avec n villages, le nombre maximal de sentiers d'un réseau qui ne contient pas deux circuits disjoints est égal à 3n - 6. Avec 7 villages, on obtient la réponse k = 15 à la première question.