Exercice

Partie A

On considère le graphe 𝒢 ci-dessous :

1 Déterminer en justifiant si ce graphe :

a. est connexe ; 0,75 pt

b. admet une chaîne eulérienne. 0,75 pt

2 On note M la matrice d’adjacence associée à ce graphe en prenant les sommets dans l’ordre alphabétique.

On donne :

Donner, en justifiant, le nombre de chemins de longueur 3 reliant E à B. 0,75 pt

Partie B

Un club alpin souhaite proposer à ses membres des randonnées de plusieurs jours dans les Alpes. À cet effet, huit refuges notés A, B, C, D, E, F, G et H ont été sélectionnés.

Le graphe 𝒢 de la partie A permet de visualiser les différents itinéraires possibles, les sommets représentant les refuges et les arêtes schématisant tous les sentiers de randonnée balisés les reliant.

1 D’après l’étude effectuée dans la partie A, le club alpin est-il en mesure de proposer :

a. un itinéraire au départ du refuge A qui passerait par tous les refuges en empruntant une fois et une seule fois chacun des sentiers ? Si oui, proposer un tel itinéraire ; 0,75 pt

b. des itinéraires de trois jours (un jour correspondant à une liaison entre deux refuges) reliant le refuge E au refuge B ? Si oui, combien peut-il en proposer ? 1 pt

2 Le graphe 𝒢 est complété ci-dessous par la longueur en kilomètres de chacun des sentiers.

Le club alpin désire aussi proposer à ses membres l’itinéraire le plus court reliant A à H.

Déterminer cet itinéraire et en préciser la longueur en kilomètres. 1 pt