Baccalauréat juin 2007 MATHÉMATIQUES Série ES

sujet : centres étrangers

Corrigé de l'exercice 2 : candidats ayant suivi l'enseignement de spécialité

Les parties A et B sont indépendantes

L'objet d'étude est le réseau des égouts d'une ville. Ce réseau est modélisé par le graphe ci-dessous : les sommets représentent les stations et les arêtes, les canalisations.

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

partie a

  1. Ce graphe admet-il une chaîne eulérienne ?

    Les degrés des différents sommets sont :

    SommetsABCDEGS
    Degrés4455233

    Il y a 4 sommets de degré impair C, D, G et S.

    Le nombre de sommets de degré impair est supérieur à deux donc il n'existe pas de chaîne eulérienne.


  2. Justifier que le nombre chromatique de ce graphe est compris entre 4 et 6.

    Soit γ le nombre chromatique de ce graphe.

    Le plus haut degré des sommets est 5 donc γ6.

    {A,B,C,D} est un sous graphe complet d'ordre 4 alors γ4.

    Ainsi, le nombre chromatique de ce graphe est compris entre 4 et 6.


partie b

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

Le graphe pondéré ci-dessus donne, en minutes, les durées des trajets existant entre les différentes stations du réseau des égouts.

  1. Un ouvrier doit se rendre par ce réseau de la station E à la station S. Déterminer, en utilisant un algorithme, le trajet le plus rapide pour aller de E à S et préciser sa durée.

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

    Pour déterminer le plus court chemin possible pour aller de la station E à la station S on utilise l'algorithme de Dijkstra.

    EABCDGSSommet sélectionné et commentaires
     0 

    E de poids 0 on marque les sommets adjacents A et B

     4 (E)7 (E)

    A on marque les sommets adjacents B (4+2<7), C (12 =4+8) et D (13 =5+8)

      6 (A)12 (A) 13 (A)

    B on marque les sommets adjacents C (6+5<12) et D (6+6<13)

       11 (B)12 (B)

    C (11+3>12 on conserve le poids de D ) et on marque les sommets G et S

        12 (B)15 (C)19 (C)

    D (12+5>15 on conserve le poids de G ) et (12+8>20 on conserve le poids de S )

         15 (C)19 (C)

    G (15+5>19 on conserve le poids de S )

          19 (C)

    S

    Pour déterminer le trajet le plus rapide on remonte les sommets à l'envers :
    S vient de C qui vient de B qui vient de A qui vient de E.

    Le trajet le plus rapide est E-A-B-C-S, il dure 19 minutes.


  2. Ayant choisi le trajet le plus rapide, l'ouvrier arrivant en C, apprend que les canalisations CG et CS sont fermées pour cause de travaux et qu'il ne peut les utiliser.

    1. Peut-il terminer, au plus vite, son trajet jusqu'à S ? Combien de temps le trajet entre E et S prendra-t-il dans ce cas ?

      Arrivé en C, l'ouvrier doit pour terminer son trajet utiliser la canalisation DS. Or le trajet le plus rapide pour atteindre la station D en partant de C est celui qui utilise la canalisation CD.

      Le temps du trajet utilisé pour arriver en C est de 11 minutes. Soit une durée totale exprimée en minutes de 11+3+8=22

      Le nouveau trajet est E-A-B-C-D-S, il dure 22 minutes.


    2. S'il avait su dès le départ que les canalisations CG et CS étaient impraticables, quel trajet aurait choisi l'ouvrier pour se rendre, au plus vite de E à S ? Combien de temps ce trajet aurait-il pris ?

      L'algorithme de Dijkstra appliqué au graphe ci-dessous permet de déterminer le plus court chemin possible pour aller de la station E à la station S.

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

      EABCDGS
       0 
       4 (E)7 (E)
        6 (A)12 (A) 13 (A)
         11 (B)12 (B)
          12 (B)
           17 (D)20 (D)
            20 (D)

      Les canalisations CG et CS étant impraticables, le trajet le plus rapide pour arriver en S passe par D en venant de B.

      Le trajet le plus rapide est donc E-A-B-D-S, il dure 20 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.