Cours Annales - Graphes
Exercice d'application

Partie A

Un parcours sportif est composé d’un banc pour abdominaux, de haies et d’anneaux.

Le graphe orienté ci-dessous indique les différents parcours conseillés partant de D et terminant à F.

Les sommets sont : D (départ), B (banc pour abdominaux), H (haies), A (anneaux) et F (fin du parcours).

Les arêtes représentent les différents sentiers reliant les sommets

d9a65008fcbd84ec92b285413cd7a480b2e9d895.png

1. Quel est l’ordre du graphe ?

2. On note $M$ la matrice d’adjacence de ce graphe où les sommets sont rangés dans l’ordre alphabétique.

   a. Déterminer $M$

   6d1931380a56838dea1b33b15b55c69b846bc078.png

    b.Assia souhaite aller de D à F en faisant un parcours constitué de 3 arêtes. Est-ce possible ? Si oui, combien de parcours différents pourra-t-elle emprunter ? Préciser ces trajets.

3. Assia a relevé ses temps de course en minute entre les différents sommets. Ces durées sont portées sur le graphe ci-dessous. Lors d’un entraînement, Assia souhaite courir le moins longtemps possible en allant de D à F.

Déterminer le trajet pour lequel le temps de course est minimal et préciser la durée de sa course.

c99fa58b8369799ff8d24b234b7664bd08ed851a.png

Partie B

Le responsable souhaite ajouter une barre de traction notée T. De nouveaux sentiers sont construits et de nouveaux parcours sont possibles.

La matrice d’adjacence $N$ associée au graphe représentant les nouveaux parcours, dans lequel les sommets sont classés en ordre alphabétique, est :

c04d3491272056153739ecaaa6d57672791e6026.png

 

Compléter l’annexe, en ajoutant les arêtes nécessaires au graphe orienté correspondant à la matrice $N$.

 

Annexe :

2815676de03bc8869c097f76fc943c4fbd6cc31f.png