Un parcours sportif est composé d'un banc pour abdominaux, de haies et d'anneaux. Le graphe orienté ci-contre indique les différents parcours conseillés partant de D et terminant à F. |
Quel est l'ordre du graphe ?
Il y a cinq sommets donc le graphe est d'ordre 5.
On note M la matrice d'adjacence de ce graphe où les sommets sont rangés dans l'ordre alphabétique.
Déterminer M.
La matrice d'adjacence de ce graphe est .
On donne . 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.
Le terme de la matrice situé à l'intersection de la troisième ligne et de la quatrième colonne est égal à 3. Il y a donc trois parcours différents constitués de 3 arêtes qui permettent à Assia d'aller de D à F.
Les parcours possibles sont : D - A - B - F ; D - H - A - F et D - H - B - F.
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.
À l'aide de l'algorithme de Dijkstra on détermine la chaîne de poids minimal entre les sommets D et F.
| D | A | B | F | H | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | D (0) |
| 28 (D) | 40 (D) | ∞ | 19 (D) | H (19) | |
| 28 (D) | 35 (H) | 51 (H) | A (28) | ||
| 35 (H) | 51 (H) | B (35) | |||
49 (B) | F (49) |
Le sommet F étant marqué, pour lire la chaîne de poids minimal, on part de F et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet pour lequel le temps de course est minimal est D - H - B - F avec une durée de 49 minutes.
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
Compléter l'annexe 1 à rendre avec la copie, en ajoutant les arêtes nécessaires au graphe orienté correspondant à la matrice N.
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.