contrôles en terminale ES

contrôle du 28 mars 2017

Corrigé de l'exercice 4 (spécialité)

Le graphe ci-dessous modélise le réseau routier reliant différents lieux notés A, B, C, D, E, F, G et H. Les arêtes sont pondérées par les temps moyens de parcours, en minutes, en tenant compte des difficultés de la circulation.

Graphe pondéré : L'illustration svg n'est pas visible par votre navigateur.
  1. Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse.

    La chaîne A-B-F-E-D-C-G-H 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éterminons le degré de chacun des sommets.

    SommetsABCDEFGH
    Degré344424232

    Le graphe est connexe et il existe deux sommets de degré impair, il existe donc une chaîne eulérienne d'extrémités A et H.


    Graphe chaîne eulérienne : L'illustration svg n'est pas visible par votre navigateur.
  2. En précisant la méthode utilisée, déterminer le trajet le plus court (en minutes) pour aller de A à H. Préciser la durée totale de ce trajet.

    Pour déterminer le trajet le plus court pour aller de A à H, on utilise l'algorithme de Dijkstra.

    Graphe algorithme de Dijkstra : L'illustration svg n'est pas visible par votre navigateur.
    ABCDEFGHSommet sélectionné
    0

    A (0)

     7 (A)24 (A)15 (A)

    B (7)

      33 (B)24 (A)13 (B)44 (B)

    F (13)

      33 (B)21 (F)19 (F) 44 (B)

    E (19)

      33 (B)21 (F)  44 (B)

    D (21)

      30 (D)   44 (B)

    C (30)

          35 (C)43 (C)

    G (35)

           42 (G)

    H (42)


    Le sommet H étant marqué, pour lire la chaîne de poids minimal, on part de H et on remonte la chaîne en suivant les prédécesseurs. HGCDFBA.

    Le trajet le plus court pour aller de A à H est A - B - F - D - C - G - H. Le temps de parcours est de 42 minutes.



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.