contrôles en terminale ES

contrôle du 07 mars 2015

Corrigé de l'exercice 2

On considère le graphe Γ ci-dessous.

Graphe : L'illustration svg n'est pas visible par votre navigateur.
  1. Donner la matrice M associée au graphe Γ (les sommets étant rangés dans l'ordre alphabétique).

    La matrice d'adjacence du graphe Γ est : M=(0100110010100010010110100010100010110100100010110110010100000110)


  2. On donne : M2=(3021112103112211214112111112111012114121122114112111214111101112) et M3=(2743774372734473474595833352533274954853745384954783594533323552)

    1. Montrer, par le calcul, que le coefficient de la quatrième ligne et huitième colonne de la matrice M3 est égal à 2.

      M3=M2×M par conséquent le coefficient de la quatrième ligne et huitième colonne de la matrice M3 s'obtient en effectuant le produit matriciel de la septième ligne de la matrice M2 par la huitième colonne de la matrice M : (11121110)×(00000110)=1×0+1×0+1×0+2×0+1×0+1×1+1×1+0×0=2

    2. Déterminer, en justifiant, le nombre de chaînes de longueur 3 reliant D à H. Les citer toutes.

      Le coefficient de la quatrième ligne et huitième colonne de la matrice M3 est égal à 2 donc il existe deux chaînes de longueur 3 reliant D à H : D-C-G-H et D-E-F-H.


    1. Déterminer en justifiant si le graphe Γ est complet.

      Les sommets A et D ne sont pas adjacents donc le graphe Γ n'est pas complet.


    2. Déterminer en justifiant si le graphe Γ est connexe.

      Aucun terme de la matrice M3 n'est nul. Par conséquent, pour toute paire de sommets distincts, il existe au moins une chaîne de longueur 3 les reliant donc le graphe Γ est connexe.


  3. Le graphe Γ modélise le plan d'un parc. Les arêtes du graphe représentent les allées du parc et les sommets du graphe des plantations d'essences exotiques.


    Est-il possible de visiter ce parc en empruntant une seule fois chaque allée ? Justifier la réponse. Si oui proposer un tel parcours.

    Graphe chaîne eulérienne : L'illustration svg n'est pas visible par votre navigateur.
    Sommet du graphe ΓABCDEFGH
    Degré33424442

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

    Il est possible de visiter ce parc en empruntant une seule fois chaque allée par exemple en effectuant le parcours A - B - C - D - E - C - G - H - F - E - A - F - G - B.


  4. Sur les arêtes du graphe Γ sont indiqués les temps moyens de parcours pour un promeneur exprimés en minutes.
    En précisant la méthode utilisée, déterminer le trajet le plus court (en minutes) pour aller de D à H. Préciser la durée totale de ce trajet.

    À l'aide de l'algorithme de Dijkstra, déterminons le trajet autoroutier le plus court pour aller de D à H.

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

    D (0)

    14 (D) 5 (D)

    E (5)

    16 (E) 13 (E)24 (E)

    C (13)

    16 (E) 19 (C) 24 (E) 35 (C)

    A (16)

    19 (C) 23 (A) 35 (C)

    B (19)

    23 (A) 31 (B)

    F (23)

    31 (B) 41 (F)

    G (31)

    40 (G)

    H (40)


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

    Le trajet le plus court pour aller de D à H est D - E - C - B - G - H. Le temps moyen de parcours est de 40 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.