Maths-cours

Cours & exercices de mathématiques

  • Troisième
  • Seconde
  • Première
  • Terminale
  • Tle Complément.
  • Tle Expert
  • Quiz
  • 3ème
  • 2nde
  • 1ère
  • Tle
  • Tle Comp
  • Tle XP
  • Quiz

Tle Expert

moyenExercice corrigé

Graphes Algorithme de Dijkstra - Bac ES Métropole 2009

Exercice 2

5 points-Pour les candidats ayant suivi l'enseignement de spécialité

Le graphe ci-dessous représente le plan d'une ville.
Le sommet A désigne l'emplacement des services techniques.
Les sommets B, C, D, E, F et G désignent les emplacements de jardins publics. Une arête représente l'avenue reliant deux emplacements et est pondérée par le nombre de feux tricolores situés sur le trajet.

Les parties I et II sont indépendantes.
Partie I
On s'intéresse au graphe non pondéré.

  1. Répondre sans justification aux quatre questions suivantes :
    1. Ce graphe est-il connexe ?
    2. Ce graphe est-il complet ?
    3. Ce graphe admet-il une chaîne eulérienne ?
    4. Ce graphe admet-il un cycle eulérien ?
  2. Déterminer, en justifiant, le nombre chromatique de ce graphe.

Partie II
On s'intéresse au graphe pondéré.
Proposer un trajet comportant un minimum de feux tricolores reliant A à G.
La réponse sera justifiée par un algorithme.

Corrigé

Partie 1

    1. Le graphe est connexe car pour toute paire de sommets, il existe une chaîne reliant ces sommets.
    2. Le graphe n'est pas complet car les points A et D (par exemple) ne sont pas relié par une arête.
    3. D'après le théorème d'Euler, le graphe admet une chaîne eulérienne. En effet, il n'existe que deux sommets de degré impair(C et D)
    4. D'après le théorème d'Euler, le graphe n'admet pas de cycle eulérien. Il faudrait pour cela qu'il n'existe aucun sommet de degré impair
  1. BCDE forme un sous-graphe complet. Le nombre chromatique du graphe est donc supérieur ou égal à 4.
    On peut colorier le graphe avec 4 couleurs de la façon suivante (par exemple) :
    rouge: A, D
    bleu: B, F
    vert: C, G
    jaune: E
    Le nombre chromatique du graphe est donc 4.

Partie 2

On utilise l'algorithme de Dijkstra :

  A   B C D E F G
0 2 (A) 1 (A) \infty \infty \infty \infty
2 (A) 5 (C) 4 (C) 6 (C) \infty
3 (B) 4 (C) 6 (C) \infty
4 (C) 6 (C) 8 (D)
5 (E) 8 (D)
7 (F)

Le trajet ACEFG comporte le nombre minimum de 7 feux.

  Signaler une erreur

Dans ce chapitre...

Cours

  • Graphes

Exercices

  • moyenGraphe - Trajet minimal - Bac ES Amérique du Nord 2009
  • moyenGraphes : Algorithme de Dijksta
  • moyenGraphes - Bac blanc ES/L Sujet 3 - Maths-cours 2018 (spé)
  • moyenGraphes - Bac blanc ES Sujet 1 - Maths-cours 2018 (spé)
  • moyenGraphes - Bac blanc ES Sujet 2 - Maths-cours 2018 (spé)
  • moyenGraphes - Trajet minimal - Bac ES Polynésie française 2008
  • moyenGraphes Trajet minimal - Bac ES Pondichéry 2009

Méthodes

  • Algorithme de Dijkstra - Étape par étape

VOIR AUSSI...

  • tableau de signe
  • loi de probabilité
  • fonction trigonométrique
  • suite géométrique
  • théorème de thalès
  • polynôme second degré
  • limites
  • fonction affine
  • théorème de pythagore
  • fonction exponentielle
  • division euclidienne
  • trigonométrie
  • python en seconde
  • fonction paire
  • loi normale
  • algorithme de dijkstra
  • tableau de variation
  • fonction dérivée

© 2021 - Maths-cours.fr - Nous contacter

Nous utilisons des cookies pour vous garantir la meilleure expérience sur notre site. Si vous continuez à utiliser ce dernier, nous considérerons que vous acceptez l'utilisation des cookies.Ok