contrôles en terminale ES

bac blanc du 9 Mars 2018

Corrigé de l'exercice 2 : ES spécialité

Le graphe ci-dessous, modélise le plan d'un quartier historique d'une ville. Les sommets sont les différents centres d'intérêts et les arêtes les rues.

Graphe : L'illustration svg n'est pas visible par votre navigateur.
  1. On appelle M la matrice associée à ce graphe les sommets étant rangés dans l'ordre alphabétique.
    On donne deux matrices R=1051419121091185262026171616526414204820382517252915126202617161652649173817372692320151216251626311416191710161716914254241295255231642084112629262019248356841541517124612 et S=1982231715119151083119151622143256221934102621151226123151010565112117162653224815171315222162432136191611141558131722049312115621054152526121719205326106121131644611.

    1. Une des deux matrices R ou S est la matrice M4. Sans calculs, indiquer laquelle des deux matrices R ou S est la matrice M4 en justifiant la réponse.

      Le terme d'indice ij de la matrice M4 donne le nombre de chaînes de longueur 4 entre le sommet de rang i et le sommet de rang j du graphe.

      Le coefficient de la première ligne et quatrième colonne de la matrice R est r1,4=1, celui de la matrice S est s1,4=3. Or il y trois chaînes de longueur 4 entre le sommet A et le sommet D : A - B - C - E - D, A - F - C - E - D et A - F - I - E - D. Donc la matrice R ne peut pas être la matrice M4.

      La matrice S est la matrice M4.


    2. Un touriste a quitté son hôtel H et s'est rendu au jardin J. Au cours de son déplacement, il est passé exactement trois fois devant un des centres d'intérêt du quartier.
      Combien de trajets différents a-t-il pu suivre ? Expliquer.

      Le touriste est passé exactement trois fois devant un des centres d'intérêt du quartier donc son parcours est modélisé par une chaîne de longueur 4 entre le sommet H et le sommet J.

      Le coefficient de la huitième ligne et de la dernière colonne de la matrice M4 étant égal à 4, il y a quatre chaînes de longueur 4 entre le sommet H et le sommet J.

      Le touriste a pu emprunter quatre trajets différents pour aller de son hôtel au jardin.


  2. Déterminer en justifiant si ce graphe est connexe.

    Les termes de la matrice M4 ne sont pas nuls. Par conséquent, pour toute paire de sommets du graphe il existe au moins une chaîne de longueur 4 les reliant donc le graphe est connexe.


  3. Est-il possible pour un touriste de parcourir chaque rue du quartier une et une seule fois en partant de son hôtel H ?

    Effectuer un parcours qui passe une seule fois par chaque rue c'est chercher si il existe une chaîne eulérienne.

    Le graphe est connexe et il n'y a que deux sommets A et G de degré impair, il existe donc des chaînes eulérienne d'extrémités A et G.

    Un touriste ne peut pas parcourir chaque rue du quartier une et une seule fois en partant de son hôtel H.


  4. Sur le graphe pondéré ci-dessous, on a indiqué sur les arêtes les distances en mètres entre les différents lieux.
    À l'aide d'un algorithme, déterminer la distance minimale permettant d'aller du sommet H (hôtel) au sommet J (jardin). Préciser alors le trajet à emprunter.

    Pour déterminer le trajet le plus court pour aller du sommet H au sommet J, on utilise l'algorithme de Dijkstra.

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

    H (0)

    130 (H)260 (H)  

    B (130)

    820 (B) 290 (B)260 (H)570 (B) 

    D (260)

    820 (B) 290 (B) 570 (B)
    540 (D)
     

    C (290)

    820 (B)   540 (D)
    530 (C)
    990 (C) 930 (C)

    E (530)

    820 (B)    990 (C) 930 (C)
    810 (E)

    I (810)

    820 (B)    990 (C)
    940 (I)
      970 (I)

    A (820)

         940 (I)1070 (A)  970 (I)

    F (940)

          1070 (A)
    1050 (F)
      970 (I)

    J (970)


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

    Le trajet le plus court pour aller de H à J est H - B - C - E - I - J, la distance parcourue est de 970 mètres.



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.