contrôles en terminale ES

contrôle du 08 février 2014

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

Dans le graphe ci-dessous, les sommets représentent différentes zones de résidence ou d'activités d'une municipalité. Une arête reliant deux de ces sommets indique l'existence d'une voie d'accès principale entre deux lieux correspondants.

Graphe Γ : L'illustration svg n'est pas visible par votre navigateur.
  1. Donner, sans justifier, le degré de chacun des sommets (la réponse pourra être présentée sous forme de tableau où les sommets seront mis dans l'ordre alphabétique).

    Dans un graphe simple non orienté, le degré d'un sommets est le nombre d'arêtes issues de ce sommet :

    SommetABCDEFG
    Degré2455442
    1. Donner la matrice M associée au graphe (les sommets seront mis dans l'ordre alphabétique).

      La matrice M associée au graphe est M=(0110000101110011011100110111011101000111010001010)


    2. On donne la matrice M3=(2785553781213128581212151313551315121312851213131012558131212873558572). Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant A et F puis donner leur liste.

      Le coefficient a1,6=5 situé à l'intersection de la première ligne et de la sixième colonne de la matrice M3 donne le nombre de chaînes de longueur 3 reliant les sommets A et F :

      Il y 5 chemins de longueur 3 reliant A et F : A-B-C-F ; A-B-D-F ; A-B-E-F ; A-C-D-F et A-C-E-F.


  2. Pour sa campagne électorale, un candidat souhaite parcourir toutes les voies d'accès principales de ce quartier sans emprunter plusieurs fois la même voie. Montrer qu'un tel parcours est possible.

    Les coefficients de la matrice M3 sont tous non nuls, par conséquent, il existe au moins une chaîne de longueur 3 reliant deux sommets quelconques du graphe donc le graphe est connexe.
    D'autre part, les sommets C et D sont les seuls sommets de degré impair.

    Le graphe est connexe et il y a exactement deux sommets de degré impair donc il existe une chaîne eulérienne. Il est possible de parcourir toutes les voies d'accès principales de ce quartier sans emprunter plusieurs fois la même voie.


    Chaîne eulérienne : L'illustration svg n'est pas visible par votre navigateur.
  3. Dans le graphe ci-dessous, les valeurs indiquent, en minutes, les durées moyennes des trajets entre les différents lieux via les transports en commun.
    Ce même candidat se trouve à la mairie (A) quand on lui rappelle qu'il a un rendez-vous avec le responsable de l'hôpital situé en zone G.

    Algorithme de Dijkstra : L'illustration svg n'est pas visible par votre navigateur.

    1. En utilisant l'algorithme de Dijkstra, déterminer le chemin de durée minimale que ce candidat devra emprunter pour arriver à son rendez-vous.

      ABCDEFGSommet sélectionné
       0 

      A (0)

      8 (A)4 (A)

      C (4)

      8 (A) 20 (C)16 (C)24 (C)

      B (8)

      12 (B)16 (C)24 (C)

      D (12)

      16 (C) 24 (C)32 (D)

      E (16)

      20(E)32 (D)

      F (20)

      28 (F)

      G (28)


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

      Le chemin de durée minimale que ce candidat devra emprunter pour arriver à son rendez-vous est A-C-E-F-G.


    2. Combien de temps faut-il prévoir pour effectuer ce trajet ?

      Le poids de la chaîne A-C-E-F-G est 28. Il faudra prévoir 28 minutes pour effectuer ce trajet.



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.