Une compagnie aérienne utilise huit aéroports que l'on nomme A, B, C, D, E, F, G et H. Entre certains de ces aéroports, la compagnie propose des vols dans les deux sens.
Cette situation est représentée par le graphe Γ ci-dessous, dans lequel :
Déterminer, en justifiant, si le graphe Γ est complet.
Les sommets A et C ne sont pas adjacents donc le graphe Γ n'est pas complet.
Déterminer, en justifiant, si le graphe Γ est connexe.
La chaîne A - E - H - G - F - B - C - D - E 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.
Déterminer, en justifiant, si le graphe Γ admet une chaîne eulérienne. Si oui, donner une telle chaîne.
Le graphe étant connexe, déterminons le degré de chacun des sommets :
Sommets | A | B | C | D | E | F | G | H |
Degré | 3 | 4 | 3 | 4 | 3 | 2 | 3 | 2 |
Il y a quatre sommets de degré impair donc le graphe Γ n'admet pas une chaîne eulérienne.
Donner la matrice d'adjacence M du graphe Γ en respectant l'ordre alphabétique des sommets du graphe.
La matrice d'adjacence M du graphe Γ est :
Pour la suite de l'exercice, on donne les matrices suivantes : Un voyageur souhaite aller de l'aéroport B à l'aéroport H.
Déterminer le nombre minimal de vols qu'il doit prendre, Justifier les réponses à l'aide des matrices données ci-dessus.
Les termes situés à l'intersection de la deuxième ligne et de la dernière colonne des matrices M et sont nuls, il n'existe pas de chaîne de longueur 1 ou 2 entre les sommets B et H. Par contre, le terme situés à l'intersection de la deuxième ligne et de la dernière colonne de la matrice est égal à 4 : il existe quatre chaînes de longueur 3 entre les sommets B et H.
Pour aller de l'aéroport B à l'aéroport H il faut prendre au moins trois vols.
Donner tous les trajets possibles empruntant trois vols successifs.
Pour aller de l'aéroport B à l'aéroport H les 4 trajets possibles sont : B - A - E - H ; B - D - E - H ; B - C - G - H et B - F - G - H.
Les arêtes sont maintenant pondérées par le coût de chaque vol, exprimé en euros.
Un voyageur partant de l'aéroport A doit se rendre à l'aéroport G. En utilisant l'algorithme de Dijkstra, déterminer le trajet le moins cher.
A | B | C | D | E | F | G | H | Sommet sélectionné |
0 | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | ∞ | A (0) |
40 (A) | ∞ | 100 (A) | 45 (A) | ∞ | ∞ | ∞ | B (40) | |
150(B) | 90 (B) | 45 (A) | 160 (B) | ∞ | ∞ | E (45) | ||
150 (B) | 85 (E) | 160 (B) | ∞ | 135 (E) | D (85) | |||
145 (D) | 160 (B) | ∞ | 135 (E) | H (135) | ||||
145 (D) | 160 (B) | 215 (H) | C (145) | |||||
160 (B) | 195 (C) | F (160) | ||||||
195 (C) | G (195) |
Le sommet G étant marqué, pour lire la chaîne de poids minimal, on part de G et on "remonte" la chaîne en suivant les prédécesseurs. .
Le trajet le moins cher pour se rendre de A à G est A - E - D - C - G pour un coût de 195 euros.
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.