Logo maths-cours.fr
Logo maths-cours.fr
Connexion Inscription
edit_note Exercices 40 min
Non commencé

Graphe – Trajet minimal – Bac ES Amérique du Nord 2009

Exercice 3

5 points - Candidats ayant suivi l'enseignement de spécialité

Un groupe d'amis organise une randonnée dans les Alpes.

On a représenté par le graphe ci-dessous les sommets B, C, D, F, T, N par lesquels ils peuvent choisir de passer. Une arête entre deux sommets coïncide avec l'existence d'un chemin entre les deux sommets.

Bac ES Amérique du Nord 2009

    1. Recopier et compléter le tableau suivant :

      Sommets B C D F N T
      Degré des sommets du graphe            
    2. Justifier que le graphe est connexe.

  2. Le groupe souhaite passer par les six sommets en passant une fois et une seule par chaque chemin.

    Démontrer que leur souhait est réalisable. Donner un exemple de trajet possible.

  3. Le groupe souhaite associer chaque sommet à une couleur de sorte que les sommets reliés par un chemin n'ont pas la même couleur. On note $ n $ le nombre chromatique du graphe.

    1. Montrer que $ 4 \leqslant n \leqslant 6 $.
    2. Proposer un coloriage du graphe permettant de déterminer son nombre chromatique.

  4. Le groupe se trouve au sommet B et souhaite se rendre au sommet N. Les distances en kilomètres entre chaque sommet ont été ajoutées sur le graphe.

    Bac ES Amérique du Nord 2009 Graphe pondéré

    Indiquer une chaîne qui minimise la distance du trajet. Justifier la réponse.

Corrigé

    1. Tableau des degrés des sommets :

      Sommets B C D F N T
      Degré 2 4 4 5 3 4
    2. Le graphe est connexe car il existe toujours un chemin reliant deux sommets quelconques.
      Par exemple, la chaîne B-C-D-N-T-F contient tous les sommets du graphe.
  2. Pour qu'un groupe puisse parcourir chaque chemin une fois et une seule (chaîne eulérienne), il faut que le nombre de sommets de degré impair soit égal à 0 ou 2.
    Ici, seuls les sommets F (degré 5) et N (degré 3) ont des degrés impairs.
    Le souhait est donc réalisable.
    Un exemple de trajet possible est : F - B - C - F - D - C - T - F - N - T - D - N.

    1. Le plus haut degré du graphe est $ \Delta = 5 $ (sommet F), donc le nombre chromatique $ n $ vérifie $ n \leqslant \Delta + 1 = 6 $.
      De plus, les sommets {C, D, F, T} forment un sous-graphe complet (chaque sommet est relié aux trois autres), donc $ n \geqslant 4 $.
      On en déduit :

      $ 4 \leqslant n \leqslant 6 $

    2. On peut proposer le coloriage suivant avec 4 couleurs :

      • Couleur 1 : F
      • Couleur 2 : C et N
      • Couleur 3 : B et T
      • Couleur 4 : D

      Puisqu'on a réussi à colorier le graphe avec 4 couleurs et que $ n \geqslant 4 $, le nombre chromatique du graphe est $ n = 4 $.

  4. Pour déterminer la chaîne qui minimise la distance entre B et N, on utilise l'algorithme de Dijkstra.

    Sommets B C D F N T Sommet choisi
    Initialisation $ 0 $ $ \infty $ $ \infty $ $ \infty $ $ \infty $ $ \infty $ B (0)
    Étape 1 $ 12_B $ $ \infty $ $ 15_B $ $ \infty $ $ \infty $ C (12)
    Étape 2 $ 14_C $ $ 15_B $ $ \infty $ $ 17_C $ D (14)
    Étape 3 $ 15_B $ $ 26_D $ $ 17_C $ F (15)
    Étape 4 $ 26_D $ $ 17_C $ T (17)
    Étape 5 $ 24_T $ N (24)

    En remontant l'algorithme à partir de N :

    • N vient de T (distance 24)
    • T vient de C (distance 17)
    • C vient de B (distance 12)

    La chaîne qui minimise la distance entre B et N est : B - C - T - N.
    La distance minimale est de 24 km.