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

sujet : Asie

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

Les parties I et II sont indépendantes

Le graphe Γ suivant représente le plan d'un zoo.
Le sommet A représente son accès. Les sommets B, C, D, E, F et G désignent les différents secteurs animaliers de ce zoo.
Une arête représente l'allée reliant deux secteurs et est pondérée par la distance de parcours, exprimée en mètres, entre ces deux secteurs.
AB = 90, AC = 290, AD = 175, AE = 150, BC = 185, BD = 155, BE = 180, CD = 120, CG =260, DE = 110, DF = 105, EF = 135, FG = 230.

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

partie i :

Pour mieux visualiser sur le plan les différents secteurs du zoo, on veut les colorier de telle sorte que deux secteurs adjacents ne soient pas de la même couleur.

  1. Quel est le nombre minimum de couleurs nécessaires à la réalisation de ce plan ? Justifier la réponse,

    A-B-C-D est un sous graphe complet d'ordre 4.

    Donc quatre couleurs au moins sont nécessaires à la réalisation de ce plan


  2. Donner un encadrement du nombre chromatique du graphe Γ . Justifier la réponse.

    Soit χ le nombre chromatique du graphe Γ. D'après la question précédente, χ4.

    D'autre part, le plus haut degré des sommets est 5 (sommet D) donc 4χ6


  3. Proposer alors une telle coloration.

    On colorie le graphe à l'aide de l'algorithme de Welsh & Powell :

    Les sommets étant classés dans l'ordre des degrés décroissants D ; A ; B; C ; E ; F; G :

    On attribue successivement la couleur 1 au sommet D, la couleur 2 au sommet A, la couleur 3 au sommet B et la couleur 4 au sommet C.
    Le sommet E est adjacent aux sommets D, A et B la plus petite couleur disponible est la couleur 4.
    Le sommet F est adjacent aux sommets D et E la plus petite couleur qui convienne est la couleur 2.
    Le sommet G n'est pas adjacent au sommet D on lui attribue la couleur 1.

    L'algorithme de Welsh & Powell donne une coloration du graphe à l'aide de quatre couleurs :

    Coloration du graphe : L'illustration svg n'est pas visible par votre navigateur.

    Une coloration avec quatre couleurs est possible et 4χ6 donc le nombre chromatique du graphe est égal à 4.


partie ii :

  1. Pour nettoyer les allées, les services techniques du zoo utilisent une balayeuse automobile.
    Est-il possible que cette balayeuse n'emprunte chaque allée qu'une fois et une seule ? Si oui, proposer un tel chemin, sinon justifier votre réponse.

    Déterminer un chemin qui emprunte chaque allée une fois et une seule c'est chercher si le graphe possède une chaîne eulérienne

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

    La chaîne A-B-C-D-E-F-G passe par tous les sommets du graphe. Donc le graphe Γ est connexe.

    D'autre part les degrés des sommets sont :

    SommetsABCDEFG
    Degrés4445432

    Le graphe Γ est connexe et contient deux sommets de degré impair il admet donc une chaîne eulérienne par exemple D-A-B-C-A-E-B-D-E-F-D-C-G-F.


  2. Les services de sécurité basés au point A doivent intervenir dans le secteur G. Déterminer, à l'aide d'un algorithme, l'itinéraire le plus court.

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

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

    ABCDEFGSommet sélectionné
    0

    A (0)

     90 (A)290 (A)175 (A)150 (A)

    B (90)

      275 (B)175 (A)150 (A)

    E (150)

      275 (B)175 (A) 285 (E)

    D (175)

      275 (B)  280 (D)

    C (275)

         280 (D) 535 (C)

    F (280)

          510 (F)

    G (510)


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

    L'itinéraire le plus court pour aller de A à G est A-D-F-G. La distance parcourue est de 510 m.



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.