Exercice

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 :

● les sommets représentent les aéroports,

● les arêtes représentent les liaisons assurées dans les deux sens par la compagnie.

Partie A

1a. Déterminer, en justifiant, si le graphe Γ est complet. 0,5 pt

b. Déterminer, en justifiant, si le graphe Γ est convexe. 0,5 pt

2 Déterminer, en justifiant, si le graphe Γ admet une chaîne eulérienne. Si oui, donner une telle chaîne. 0,75 pt

3 Donner la matrice d’adjacence M du graphe Γ en respectant l’ordre alphabétique des sommets du graphe. 0,75 pt

4 Pour la suite de l’exercice, on donne les matrices suivantes :

M 2 =( 3 1 2 2 1 1 0 1 1 4 1 2 2 0 2 0 2 1 3 1 1 2 0 1 2 2 1 4 1 1 1 1 1 2 1 1 3 0 1 0 1 0 2 1 0 2 0 1 0 2 0 1 1 0 3 0 1 0 1 1 0 1 0 2 ) et M 3 =( 4 8 3 7 6 1 4 1 8 4 8 8 3 6 1 4 3 8 2 7 4 1 6 1 7 8 7 6 7 3 3 2 6 3 4 7 2 3 1 4 1 6 1 3 3 0 5 0 4 1 6 3 1 5 0 4 1 4 1 2 4 0 4 0 ).

Un voyageur souhaite aller de l’aéroport B à l’aéroport H.

a. Déterminer le nombre minimal de vols qu’il doit prendre. Justifier les réponses à l’aide des matrices données ci-dessus. 0,75 pt

b. Donner tous les trajets possibles empruntant trois vols successifs. 0,75 pt

Partie B

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. 1 pt