contrôles en terminale ES

bac blanc du 12 février 2009

Corrigé de l'exercice 3 : Élèves ayant suivi l'enseignement de spécialité

Sur la carte ci-dessous, sont représentés sept pays avec leurs frontières.

Carte : L'illustration svg n'est pas visible par votre navigateur.
  1. On s'intéresse aux frontières séparant ces pays. :

    1. Traduire cette carte par un graphe dont les sommets sont les pays et où chaque arête représente une frontière entre deux pays.

      Graphe : L'illustration svg n'est pas visible par votre navigateur.
    2. 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 Sans calculs, indiquer quelle est la matrice M3.
      R=(4223311242311322322023325222312241211021211322214) ; S=(81291274111289121147996116461212111212412711612661044446261176121066) ; T=(4122311242312312322123326323212342222122322323224)

      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.

      Les matrices R et T ne conviennent pas pour plusieurs raisons, entre autres :

      • Il existe plus d'une chaîne de longueur 3 qui relient les sommets A et G ( A-C-D-G, A-B-D-G, A-D-E-G, … ) or r1,7=1 et t1,7=1.

      • Le graphe n'est pas orienté et la matrice T n'est pas symétrique.

      • Il existe au moins une chaîne de longueur 3 qui relient les sommets C et F par exemple B-D-E-F or r3,6=0 et r6,3=0.

      La matrice S est la seule susceptible d'être égale à M3


    3. Est-il possible, dans tous les cas, de se rendre d'un pays à un autre en franchissant exactement trois frontières ?

      Les termes de la matrice M3 sont différents de 0 alors, il est possible, dans tous les cas, de se rendre d'un pays à un autre en franchissant exactement trois frontières.


    4. Est-il possible de visiter tous les pays en franchissant une et une seule fois chacune des frontières ?

      Visiter tous les pays en franchissant une et une seule fois chacune des frontières revient à chercher une chaîne eulérienne Un graphe connexe admet une chaîne eulérienne si et seulement si le nombre de ses sommets de degré impair est 0 ou 2.

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

      • Déterminons le degré de chacun des sommets.

        SommetsABCDEFG
        Degré4435424

      Le graphe est connexe et il existe deux sommets de degré impair, il admet 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 :

      Graphe,chaîne eulérienne : L'illustration svg n'est pas visible par votre navigateur.

      Il existe une chaîne eulérienne donc il est possible de visiter tous les pays en franchissant une et une seule fois chacune des frontières.


  2. Proposer une coloration de la carte (ou du graphe) avec le minimum de couleurs afin que deux pays qui ont une frontière commune aient des couleurs différentes.

    Soit X le nombre chromatique du graphe.

    Le plus haut degré des sommets est 5 donc X6.D'autre part, {A;B;C;D} est un sous graphe complet d'ordre 4 donc X4. Ainsi, 4X6.

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

    Or à l'aide de l'algorithme de Welsh et Powell on obtient une coloration avec 4 couleurs. Donc le nombre nombre chromatique du graphe est égal à 4.

    Quatre couleurs sont nécessaires pour colorier la carte.


    Coloriage de la carte : L'illustration svg n'est pas visible par votre navigateur.
  3. Une personne désire se rendre en train d'une ville située dans le pays A à une autre ville du pays F. Le graphe pondéré ci-dessous donne, en heures, les durées moyennes des liaisons ferroviaires existantes entre les différents pays en tenant compte des temps d'attente entre deux correspondances.

    En précisant la méthode utilisée, déterminer le trajet le plus court que cette personne devra utiliser pour son voyage. Combien de temps faut-il prévoir pour effectuer ce trajet ?

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

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

    A (0)

     4 (A)3 (A)7 (A)6 (A)

    C (3)

     4(A)  5 (C)6 (A)

    B (4)

       5 (C)7 (B) 6 (A)

    D (5)

        7 (B) 6 (A)

    G (6)

        7 (B)10 (G)  

    E (7)

         9 (E) 

    F (9)


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

    Le trajet le plus court possible pour aller de A à F est A-B-E-F. Il faudra prévoir environ 9  heures 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.