Exercice 3 (5 points)

Candidats ayant choisi la spécialité « mathématiques »

Un journaliste britannique d'une revue consacrée à l'automobile doit tester les autoroutes françaises. Pour remplir sa mission, il décide de louer une voiture et de circuler entre six grandes villes françaises : Bordeaux $(B)$, Lyon $(L)$, Marseille $(M)$, Nantes $(N)$, Paris $(P)$ et Toulouse $(T)$.

Le réseau autoroutier reliant ces six villes est modélisé par le graphe ci-dessous sur lequel les sommets représentent les villes et les arêtes les liaisons autoroutières entre ces villes.

Partie A

1. 1. Quel est l'ordre du graphe ?

   2. Le graphe est-il complet ? Justifier la réponse.

2. 1. On admet que le graphe est connexe. Le journaliste envisage de parcourir chacune des liaisons modélisées sur le graphe une fois et une seule. Est-ce possible ? Justifier la réponse.

   2. Le journaliste va-t-il pouvoir louer sa voiture dans un aéroport parisien, parcourir chacune des liaisons une et une seule fois puis rendre la voiture dans le même aéroport ? Justifier la réponse.

3. On nomme $G$ la matrice d'adjacence du graphe (les villes étant rangées dans l'ordre alphabétique). On donne :

   $G = \begin{pmatrix} 0 &\ldots &0 &1 &1 &1 \\ \ldots&0 &1 &1 &1 &1\\ 0 &1 &\ldots &0 &\ldots &1\\ 1 &1 &0 &0 &1 &0 \\ 1 &1 &\ldots &1 &0 &1\\ 1 &1 &1 &0 &1 &0 \end{pmatrix}$   et   $G^3 = \begin{pmatrix} 10 &13 &5 &10 &11 &12\\ 13 &12 &8 &11 &13 &12\\ 5 &8 &2 &5 &5 &7\\ 10 &11 &5 &6 &10 &7\\ 11 &13& 5 &10 &10 &12\\ 12 &12 &7 &7 &12 &8 \end{pmatrix}$

   1. Recopier et compléter la matrice d'adjacence.

   2. Alors qu'il se trouve à Paris, le rédacteur en chef demande au journaliste d'être à Marseille exactement trois jours plus tard pour assister à une course automobile. Le journaliste décidechaque jour de s'arrêter dans une ville différente.

      Déterminer le nombre de trajets possibles.

Partie B

On a indiqué sur le graphe ci-dessous le temps nécessaire en minutes pour parcourir chacune des liaisons autoroutières.

Le journaliste se trouve à Nantes et désire se rendre le plus rapidement possible à Marseille.

Déterminer un trajet qui minimise son temps de parcours.