Exercice

Sur le graphe ci-dessous les sept sommets A, B, C, D, E, F et G correspondent à sept villes. Une arête reliant deux de ces sommets indique l’existence d’une liaison entre les deux villes correspondantes.

Les questions 1, 2 et 3 sont indépendantes.

1 Est-il possible de trouver un trajet, utilisant les liaisons existantes, qui part d’une des sept villes et y revient en passant une fois et une seule fois par toutes les autres villes ?

2 On note M la matrice associée au graphe ci-dessus. Les sommets sont rangés suivant l’ordre alphabétique.

On donne M 3 =( 0 7 6 1 0 4 2 7 2 1 10 9 1 5 6 1 0 9 8 0 3 1 10 9 2 1 7 5 0 9 8 1 0 6 3 4 1 0 7 6 0 2 2 5 3 5 3 2 2 ).

Donner le nombre de chemins de longueur 3 qui relient le sommet A au sommet F. Les citer tous. Aucune justification n’est demandée.

3 On donne ci-après et sur le graphe ci-après les distances exprimées en centaines de kilomètres entre deux villes pour lesquelles il existe une liaison : AB : 5 ; AC : 7 ; BD : 8 ; BE : 15 ; BG : 6 ; CD : 10 ; CE : 15 ; DF : 20 ; DG : 10 ; EF : 5.

Un représentant de commerce souhaite aller de la ville A à la ville F.

En expliquant la méthode utilisée, déterminer le trajet qu’il doit suivre pour que la distance parcourue soit la plus courte possible et donner cette distance.