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.
Quel est l'ordre du graphe ?
Il y a six sommets donc le graphe est d'ordre 6.
Le graphe est-il complet ? Justifier la réponse.
Les sommets M et N ne sont pas ajacents donc le graphe n'est pas complet.
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.
Les degrés des sommets sont :
| Sommets | B | L | M | N | P | T |
| Degrés | 4 | 5 | 2 | 3 | 4 | 4 |
Le graphe est connexe et il n'y a que deux sommets L et N de degré impair, il existe donc des chaînes eulérienne d'extrémités L et N.
Le journaliste peut parcourir chacune des liaisons modélisées sur le graphe une fois et une seule. (Par exemple N - P - T - M - L - N - B - P - L - T - B - L.)
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.
Il y a deux sommets de degré impair donc il n'existe pas de cycle eulérien. Il n'est pas possible 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.
On nomme G la matrice d'adjacence du graphe (les villes étant rangées dans l'ordre alphabétique). On donne :
Recopier et compléter la matrice d'adjacence.
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écide chaque jour de s'arrêter dans une ville différente. Déterminer le nombre de trajets possibles.
Le terme de la matrice situé à l'intersection de la cinquième ligne et de la troisième colonne est égal à 5. Il y a donc cinq trajets différents qui permettent au journaliste d'être à Marseille trois jours plus tard en s'arrêtant chaque jour dans une ville différente.
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.
À l'aide de l'algorithme de Dijkstra, déterminons le trajet qui minimise le temps de parcours pour se rendre de Nantes à Marseille :
| B | L | M | N | P | T | Sommet sélectionné |
| ∞ | ∞ | ∞ | 0 | ∞ | ∞ | N (0) |
| 206 (N) | 396 (N) | ∞ | 222 (N) | ∞ | B (206) | |
| 396 (N) | ∞ | 222 (N) | 359 (B) | P (222) | ||
| 396 (N) | ∞ | 359 (B) | T (359) | |||
| 396 (N) | 595 (T) | L (396) | ||||
| 595 (T) | M (595) |
Le sommet M étant marqué, pour lire la chaîne de poids minimal, on part de M et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet qui minimise le temps de parcours est Nantes, Bordeaux, Toulouse, Marseille pour une durée d'environ 595 minutes.
Les documents présentés ne sont pas libres de droits. Vous pouvez les télécharger et diffuser (en indiquant la provenance) à condition de ne pas en faire un usage commercial.