contrôles en terminale ES

bac blanc du 08 avril 2014

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

On considère le graphe ci-dessous :

Graphe : L'illustration svg n'est pas visible par votre navigateur.
  1. On appelle M la matrice associée à ce graphe, les sommets étant pris dans l'ordre alphabétique. Une des trois matrices R, S ou T est la matrice M3.
    R=(4223341242311322322023325222312241211021211422214) S=(81291274111289121147996116461212111212412711612661044446261176121066) T=(4122341242312312322123326323212342222122322323224)
    Sans calculer la matrice M3, indiquer quelle est la matrice M3 en justifiant votre choix.

    Les sommets étant classés dans l'odre alphabétique, les termes de la matrice M3 donnent le nombre de chaînes de longueur 3 reliant deux sommets quelconques.

    • Le graphe n'est pas orienté et la matrice T n'est pas symétrique par conséquent, la matrice T ne convient pas.

    • Il existe au moins une chaîne de longueur 3 qui relie les sommets C et F par exemple C-B-E-F or r3,6=0 et r6,3=0 donc la matrice R ne convient pas.

    La matrice S est la seule des trois matrices proposées susceptible d'être égale à M3


  2. Ce graphe est-il complet ? Ce graphe est-il connexe ?

    • Le graphe est d'ordre 7 et aucun des sommet n'est de degré 6 donc le graphe n'est pas complet.


    • La chaîne A-B-C-D-E-F-G 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.


  3. Ce graphe admet-il une chaîne eulérienne ? Justifier la réponse. Si oui donner une telle chaîne.

    Déterminons le degré de chacun des sommets.

    SommetsABCDEFG
    Degré4435424

    Le graphe est connexe et il existe deux sommets de degré impair, il existe donc une chaîne eulérienne commençant par un des deux sommets de degré impair (C ou D) et finissant par le deuxième sommet de degré impair. Par exemple la chaîne : C - A - B - E - F - G - E - D - G - A - D - B - C - D.


    Graphe : L'illustration svg n'est pas visible par votre navigateur.
  4. Un représentant, a modélisé à l'aide du graphe ci-dessous le réseau routier reliant différents clients notés A, B, C, D, E, F et G. Les arêtes sont pondérés par les distances en kilomètre à parcourir.

    Graphe : L'illustration svg n'est pas visible par votre navigateur.

    Après avoir visité le client C, ce représentant souhaite se rendre chez le client D.

    1. En précisant la méthode utilisée, déterminer le trajet le plus court (en kilomètres) pour aller de C à D. Préciser la longueur en kilomètres de ce trajet.

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

      Algorithme de Dijkstra : L'illustration svg n'est pas visible par votre navigateur.
      ABCDEFGSommet sélectionné
      0

      C (0)

      35 (C)6 (C) 43 (C)

      B (6)

      35 (C)  43 (C)14 (B)

      E (14)

      35 (C)  43 (C) 20 (E) 25 (E)

      F (20)

      35 (C)  43 (C)  25 (E)

      G (25)

      33 (G)  43 (C)   

      A (33)

         42 (A)   

      D (42)


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

      Le trajet le plus court possible pour aller de C à D est C-B-E-G-A-D. La distance parcourue est de 42 km.


    2. Existe-t-il un parcours de même distance permettant à ce représentant de visiter tous ses clients ?

      Le parcours obtenu à l'aide de l'algorithme de Dijkstra ne permet pas au représentant de visiter le client F or la chaîne E-F-G a un poids égal à celui de l'arête E-G

      Le trajet C-B-E-F-G-A-D permet au représentant de visiter tous ses clients en parcourant la même distance de 42 km.



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.