Annales gratuites Bac Général ES spé Maths : Graphe

Le graphe ci-dessous indique, sans respecter d'échelle, les parcours possibles entre les sept bâtiments d'une entreprise importante.

Un agent de sécurité effectue régulièrement des rondes de surveillance. Ses temps de parcours en minutes entre deux bâtiments sont les suivants :

AB : 16 minutes ; AG : 12 minutes ; BC : 8 minutes ; BE : 12 minutes ;
BG : 8 minutes ; CD : 7 minutes ; CE : 4 minutes ; CG : 10 minutes ;
DE : 2 minutes ; EF : 8 minutes ; EG : 15 minutes ; FG : 8 minutes.

1) En justifiant la réponse, montrer qu'il est possible que l'agent de sécurité passe une fois et une seule par tous les chemins de cette usine. Donner un exemple de trajet.

2) L'agent de sécurité peut-il revenir à son point de départ après avoir parcouru une fois et une seule tous les chemins ? Justifier la réponse.

3) Tous les matins, l'agent de sécurité part du bâtiment A et se rend au bâtiment D.
En utilisant un algorithme que l'on explicitera, déterminer le chemin qu'il doit suivre pour que son temps de parcours soit le plus court possible, et donner ce temps de parcours.

Recherche d'une chaîne de poids minimal.

1) Pour que l'agent passe une fois et une seule par tous les chemins, il faut qu'il existe une chaîne Eulérienne à ce graphe connexe. Or un théorème nous dit qu'un graphe connexe admet une chaîne Eulérienne si et seulement si, il a au plus deux sommets de degré impair.
Déterminons les degrés de chacun des sommets :
          A a comme degré 2
          B a comme degré 4
          C a comme degré 4
          D a comme degré 2
          E a comme degré 5
          F a comme degré 2
          G a comme degré 5

Par conséquent, il existe une chaîne Eulérienne à ce graphe.
Un exemple : GABCDECGBEFGE.

2) Pour cela, il faut que le graphe admette un cycle Eulérien. Or un théorème de cours nous dit qu'un graphe connexe admet une cycle Eulérien si et seulement si tous les degrés des sommets sont pairs.
Pour l'exemple qui nous concerne, les degrés de E et G étant impairs, il n'existe pas de cycle Eulérien.

Le chemin le plus court est AGCED, son temps est 28 minutes.

Algorithme de recherche d'une chaîne de poids minimal :
- Attribuer le poids définitif 0 au point initial (A)
- Attribuer aux sommets adjacents à A le poids des arêtes qui les relient (en indiquant la provenance) et aux autres ¥ .
- Prendre le poids le plus petit et le considérer comme définitif (en gras).
- Recommencer le processus à partir du point dont on vient de trouver le poids définitif ( en faisant la somme des poids et en choisissant le poids minimal).
- Réitérer jusqu'a ce que le sommet extrémité ait un poids définitif.

Le poids définitif trouvé est le poids minimal et la chaîne se détermine en lisant le tableau et les provenances.

Il fallait bien connaître son cours sur les chaînes Eulériennes et l'algorithme de recherche de poids minimal.