Un guide de randonnée en montagne décrit les itinéraires possibles autour d'un pic rocheux.
La description des itinéraires est donnée par le graphe ci-contre. Les sommets de ce graphe correspondent aux lieux remarquables. Les arêtes de ce graphe représentent les sentiers possibles entre ces lieux.
Légende :
① | Départ | ② | Passerelle |
③ | Roche percée | ④ | Col des 3 vents |
⑤ | Pic rouge | ⑥ | Refuge |
⑦ | Col vert | ⑧ | Pont Napoléon |
⑨ | Cascade des anglais | ⑩ | Arrivée |
Donner un itinéraire allant de D à A passant par tous les sommets du graphe une seule fois mais n'empruntant pas forcément tous les sentiers.
Un itinéraire allant de D à A passant par tous les sommets du graphe une seule fois est 1 - 4 - 9 - 7 - 5 - 2 - 3 - 6 - 8 - 10.
Existe-t-il un itinéraire allant de D à A utilisant tous les sentiers une seule fois ? Justifier votre réponse.
Il y a quatre sommets de degré 3 : les sommets 1, 6 7 et 9 donc il n'existe pas de chaîne eulérienne.
Il n'existe pas un itinéraire allant de D à A utilisant tous les sentiers une seule fois.
On note M la matrice d'adjacence associée à ce graphe, les sommets étant pris dans l'ordre. On donne .
Que représente le nombre 89 situé sur la deuxième ligne et la quatrième colonne ?
Il y a 89 itinéraires allant de la passerelle au col des 3 vents empruntant 5 sentiers.
Déterminer le nombre d'itinéraires allant de D à A empruntant 5 sentiers. Citer un tel itinéraire passant par le pic rouge.
Le nombre situé sur la première ligne et la dixième colonne est égal à 31
Il y a 31 itinéraires allant de D à A empruntant 5 sentiers. Par exemple , D - 2 - 5 - 7 - 8 - A
On a complété ci-dessous, le graphe décrivant les itinéraires avec les temps de parcours en minutes pour chacun des sentiers.
Déterminer l'itinéraire allant de D à A le plus court en temps. On fera apparaître la démarche en utilisant un algorithme.
À l'aide de l'algorithme de Dijkstra, on détermine l'itinéraire allant de D à A le plus court en temps :
| D | ② | ③ | ④ | ⑤ | ⑥ | ⑦ | ⑧ | ⑨ | A | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | D (0) |
| 35 (D) | 15 (D) | 90 (D) | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ③ (15) | |
| 35 (D) | 90 (D) | ∞ | 40 (3) | ∞ | 105(3) | ∞ | ∞ | ② (35) | ||
| 90 (D) | 85 (2) | 40 (3) | ∞ | 105(3) | ∞ | ∞ | ⑥ (40) | |||
| 90 (D) | 80 (6) | ∞ | 95(6) | ∞ | ∞ | ⑤ (80) | ||||
| 90 (D) | 90 (5) | 95(6) | ∞ | ∞ | ④ (90) | |||||
| 90 (5) | 95(6) | 135 (4) | ∞ | ⑦ (90) | ||||||
| 95 (6) | 110 (7) | ∞ | ⑧ (95) | |||||||
| 110 (7) | 135 (8) | ⑨ (110) | ||||||||
| 130 (9) | A (130) |
Le sommet A étant marqué, pour lire la chaîne de poids minimal, on part de A et on "remonte" la chaîne en suivant les prédécesseurs. .
L'itinéraire allant de D à A le plus court en temps est D - 3 - 6 - 5 - 7 - 9 - A, ce trajet dure 130 minutes..
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.