Le graphe ci-dessous représente, dans un aéroport donné, toutes les voies empruntées par les avions au roulage. Ces voies, sur lesquelles circulent les avions avant ou après atterrissage, sont appelées taxiways.
Les arêtes du graphe représentent les voies de circulation (les « taxiways ») et les sommets du graphe sont les intersections.
Déterminer le nombre de voies de circulation au total.
Il y a 13 arêtres donc 13 voies de circulation.
Afin que l'aéroport soit déneigé le plus rapidement possible, est-il possible de planifier un parcours pour que les chasse-neige passent par toutes les voies sans emprunter plusieurs fois la même route ? Justifier la réponse et donner un tel parcours.
La chaîne A - B - C - D - E - F - T contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe est connexe.
Le tableau ci-dessous, donne le degré des sommets du graphe :
Sommet du graphe 𝒢 | A | B | C | D | E | F | T |
Degré | 3 | 4 | 4 | 4 | 4 | 4 | 3 |
Le graphe est connexe et il n'y a que deux sommets A et T de degré impair, il existe donc une chaîne eulérienne d'extrémités A et T.
Il est possible de planifier un parcours pour que les chasse-neige passent par toutes les voies sans emprunter plusieurs fois la même route. Par exemple A - B - C - A - T - F - C - D - B - E - D - F - E - T.
Dans le graphe ci-dessous, on a indiqué le sens de circulation pour les avions dans les différentes voies ainsi que le temps de parcours pour chacune en minute(s).
Écrire la matrice M associée à ce graphe (ranger les sommets dans l'ordre alphabétique).
Citer tous les chemins de longueur 3 reliant A à T.
Le nombre total de chemins de longueur 3 reliant A à T est donné par le terme de la matrice .
donc il existe deux chaînes de longueur 3 entre les sommets A et T
Les deux chemins de longueur 3 reliant A à T sont : A - B - E - T et A - C - F - T.
L'avion qui a atterri est en bout de piste en A et doit se rendre le plus rapidement possible au terminal situé au point T.
Déterminer l'itinéraire le plus rapide et en donner la durée.
À l'aide de l'algorithme de Dijkstra, déterminons le temps minimal en minute pour aller de A à T.
A | B | C | D | E | F | T | Sommet sélectionné |
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
4 (A) | 3 (A) | ∞ | ∞ | ∞ | ∞ | C (3) | |
4 (A) | 5 (C) | ∞ | 6 (C) | ∞ | B (4) | ||
4,5 (B) | 5 (B) | 6 (C) | ∞ | D (4,5) | |||
5 (B) | 5 (D) | ∞ | E (5) | ||||
5 (D) | 9 (E) | F (5) | |||||
5,5 (F) | T (5,5) |
Le sommet T étant marqué, pour lire la chaîne de poids minimal, on part de T et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet qui permet d'atteindre le plus rapidement le terminal est A - B - D - F - T. La durée de ce parcours est de 5,5 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.