Graphes – Bac ES Polynésie 2018 (spé)
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 , Lyon , Marseille , Nantes , Paris et Toulouse .
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
Quel est l'ordre du graphe ?
Le graphe est-il complet ? Justifier la réponse.
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.
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.
On nomme la matrice d'adjacence du graphe (les villes étant rangées dans l'ordre alphabétique). On donne :
et
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é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.