Les différentes parties sont indépendantes.
Une compagnie aérienne a représenté à l'aide d'un graphe les différentes liaisons assurées par ses avions. Les sommets du graphe sont les initiales des aéroports desservis et les arêtes correspondent aux vols effectués par un avion de cette compagnie entre deux aéroports.
Par exemple, l'arête entre A et G signifie qu'un avion effectue le vol entre les aéroports A et G, en partant de A vers G ou en partant de G vers A.
Le graphe est-il complet ? Interpréter ce résultat dans le cadre de l'exercice.
Les sommets A et C ne sont pas adjacents donc le graphe n'est pas complet. Il n'y a pas de liaison directe entre entre deux aéroports quelconques.
On note M la matrice d'adjacence du graphe ci-dessus en classant les sommets par ordre alphabétique. Compléter les deux lignes manquantes de la matrice M donnée.
La matrice d'adjacence du graphe est :
La compagnie souhaite qu'un avion partant de l'aéroport F effectue 3 vols avant d'arriver à l'aéroport B. À l'aide de la matrice donnée ci-après, déterminer le nombre de trajets possibles.
Le nombre de chaînes de longueur 3 joignant le sommet F au sommet B est donné par le terme d'indice situé à l'intersection de la quatrième ligne et de la deuxième colonne de la matrice .
il y cinq trajets possibles permettant de relier l'aéroport F à l'aéroport B en effectuant 3 vols.
L'entreprise souhaite qu'un même avion puisse parcourir successivement une fois et une seule chaque liaison.
Justifier qu'un avion peut le faire et préciser les aéroports de départ et d'arrivée possibles.
La chaîne A - V - B - P - G - F - L - M - C contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets, il existe une chaîne les reliant. Donc le graphe est connexe.
Le graphe est connexe et il n'y a que deux sommets de degré impair G et V par conséquent, il existe des chaînes eulériennes d'extrémités G et V.
Un avion peut parcourir successivement une fois et une seule chaque liaison à condition de patir de G (ou de V) et d'arriver à V (respectivement ou G).
Lors de ce trajet, combien de fois cet avion doit-il se poser à l'aéroport P ? Expliquer la réponse.
Le sommet P est de degré 4. Lors du parcours de la chaîne eulérienne, lorqu'on arrive en P par une arête on ressort par une arête non utilisée. Par conséquent, on passe deux fois par le sommet P.
Lors de ce trajet cet avion se pose deux fois à l'aéroport P.
Sur le graphe ci-dessous sont indiqués les différents temps de vol en heure entre deux aéroports.
Un client souhaite utiliser une offre promotionnelle de cette compagnie pour voyager de l'aéroport V jusqu'à l'aéroport F. Combien d'heures de vol doit-il envisager au minimum ? Préciser le trajet.
Déterminons un parcours de distance minimale joignant le sommet V au sommet F à l'aide de l'algorithme de Dijkstra.
| V | A | B | C | F | G | L | M | P | Sommet sélectionné |
| 0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | V (0) |
| 1 (V) | 2 (V) | ∞ | ∞ | ∞ | ∞ | ∞ | 4 (V) | A (1) | |
| 2 (V) | ∞ | ∞ | 5 (A) | ∞ | 6 (A) | 4 (V) | B (2) | ||
| ∞ | ∞ | 5 (A) | ∞ | 4 (B) | 4 (V) | M (4) | |||
| 8 (M) | ∞ | 5 (A) | 5 (M) | 4 (V) | P (4) | ||||
| 8 (M) | 10 (P) | 5 (A) | 5 (M) | G (5) | |||||
| 8 (M) | 10 (P) | 5 (M) | L (5) | ||||||
| 8 (M) | 9 (L) | C (8) | |||||||
| 9 (L) | F (9) |
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 temps minimum pour voyager de l'aéroport V jusqu'à l'aéroport F est de 9 heures en effectuant le parcours V - B - M - L - F.
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.