Bac de maths

Corrigé de l'exercice de spécialité du bac ES de maths d'avril 2013 à Pondichéry

Cacher les corrigés

 On considère le graphe ci-dessous :

 

 

Partie A

1. Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse. Si oui donner une telle chaîne.
Tableau avec les degrés des sommets du graphe :
On remarque que le graphe est connexe et que tous ses sommets sont de degré pair sauf les sommets D et G.
Donc il existe une chaîne eulérienne entre les sommets D et G.
Par exemple :
D,B,C,D,F,C,A,B,E,G,D,E,F,G
2. Ce graphe admet-il un cycle eulérien ? Justifier la réponse. Si oui donner un tel cycle.
Comme on l'a vu dans la question précédente tous les sommets du graphe ne sont pas pairs donc il n'y a pas de cycle eulérien.
3. Donner la matrice M associée au graphe . Les sommets seront pris dans l'ordre alphabétique : A, B, C, D, E, F, G.
La matrice d'adjacence du graphe est la suivante :

 

 

Partie B

Une région est munie d'un réseau de trains, représenté par le graphe ci-dessous.
Les stations sont symbolisées par les sommets A, B, C, D, E, F et G. Chaque arête représente une ligne reliant deux gares. Les temps de parcours (correspondance comprise) en minutes entre chaque sommet ont été rajoutés sur le graphe.
1. Déterminer le plus court chemin en minutes, reliant la gare B à la gare G. Justifier la réponse grâce à un algorithme.
2. Quelle est la longueur en minutes de ce chemin ?
On utilise l'algorithme de Dijkstra.
Les différentes étapes sont regroupées dans le tableau suivant, lorsqu'un sommet est fixé les informations le concernant sont mises en gras.
Le plus court chemin en minute reliant la gare B à la gare G est : B,C,D,F,G.
Il dure 36 minutes.

 

Licence Creative Commons

Conditions Générales d'Utilisation