Un club cycliste se prépare pour une compétition.
Le graphe ci-dessous représente l'ensemble des routes empruntables le jour de la compétition: les arêtes représentent les routes et les sommets représentent des points de passage.
Justifier que ce graphe est connexe.
La chaîne fermée D - E - G - F - S - J - I - H - D contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets du graphe il existe au moins une chaîne les reliant donc le graphe est connexe.
Existe-t-il un trajet permettant de parcourir toutes les routes une fois et une seule ? Justifier.
Les degrés des sommets sont :
| Sommets | D | E | F | G | H | I | J | S |
| Degré | 2 | 4 | 5 | 3 | 4 | 4 | 4 | 2 |
Le graphe est connexe et il n'y a que deux sommets F et G de degré impair, il existe donc des chaînes eulérienne d'extrémités F et G.
Il existe des trajets permettant de parcourir toutes les routes une fois et une seule.
Si un tel trajet existe, en citer un.
Par exemple le trajet G - E - H - J - I - F - J - S - F - G - I - H - D - E - F.
Soit M la matrice d'adjacence de ce graphe pour laquelle les sommets sont cités dans l'ordre alphabétique: D, E, F, G, H, I, J, S.
Recopier et compléter uniquement la partie manquante de M.
La matrice d'adjacence de ce graphe est :.
On donne : Un cycliste souhaite aller du point D au point F en empruntant trois routes.
Combien d'itinéraires différents sont possibles ?
Donner la liste complète.
Le coefficient de la première ligne et troisième colonne de la matrice est égal au nombre de chemins permettant d'aller du point D au point F en empruntant trois routes.
Il y a quatre trajets permettant d'aller du point D au point F en empruntant trois routes : {D-E-G-F}, {D-H-E-F}, {D-H-I-F}, {D-H-J-F}.
Dans le graphe ci-dessous, on a indiqué le temps, en minute, mis par un des cyclistes pour parcourir chacune des routes.
Afin de gagner la compétition, il doit choisir le trajet le plus rapide reliant le point D au point S.
Déterminer, en utilisant un algorithme, ce trajet minimal et préciser la durée, en minute, puis en heure de ce trajet.
À l'aide de l'algorithme de Dijkstra, déterminons le trajet qui minimise le trajet reliant le point D au point S.
| D | E | F | G | H | I | J | S | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | B (0) |
| 75 (D) | ∞ | ∞ | 10 (D) | ∞ | ∞ | ∞ | H (10) | |
| 75 (D) | ∞ | ∞ | 96 (H) | 134 (H) | ∞ | E (75) | ||
| 185 (E) | 168 (E) | 96 (H) | 134 (H) | ∞ | I (96) | |||
| 185 (E) | 101 (I) | 134 (H) | ∞ | G (101) | ||||
181 (G) | 134 (H) | ∞ | J (134) | |||||
| 181 (G) | 251 (J) | F (181) | ||||||
240 (F) | S (240) |
Le sommet S étant marqué, pour lire la chaîne de poids minimal, on part de S et on "remonte" la chaîne en suivant les prédécesseurs : .
Le trajet le plus rapide reliant le point D au point S est : D - H - I - G - F - S pour une durée, de 240 minutes soit 6 heures.
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.