Baccalauréat 2016 MATHÉMATIQUES Série ES-L

sujet : Centres Étrangers 2016

Corrigé de l'exercice 3 : candidats ayant suivi l'enseignement de spécialité ES

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.
Graphe Γ : L'illustration svg n'est pas visible par votre navigateur.

partie a

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


    2. 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.


  1. 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 ABCDEFGH
    Degré34343232

    Il y a quatre sommets de degré impair donc le graphe Γ n'admet pas une chaîne eulérienne.


  2. 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 : M=(0101100010110100010100101110100010010001010000100010010100001010)


  3. Pour la suite de l'exercice, on donne les matrices suivantes : M2=(3122110114122020213112012214111112113010102102010201103010110102)etM3=(4837614184883614382741617876733263472314161330504163150414124040) Un voyageur souhaite aller de l'aéroport B à l'aéroport H.

    1. 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 M2 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 M3 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.


    2. 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.


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.

algorithme de Dijkstra : L'illustration svg n'est pas visible par votre navigateur.
ABCDEFGHSommet 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. GCDEA.

Le trajet le moins cher pour se rendre de A à G est A - E - D - C - G pour un coût de 195 euros.



Rechercher des exercices regoupés par thème


[ Accueil ]


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.