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

annales-bss

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

Bac S Métropole 2009

  • Suites et récurrence - Bac S Métropole 2009
  • Calcul d'aires - Bac S Métropole 2009
  • Graphes Algorithme de Dijkstra - Bac ES Métropole 2009
  • Probabilités Combinaisons - Bac S Métropole 2009
  • Nombres complexes - Bac S Métropole 2009
  • Congruences - Bac S Métropole 2009

Dans ce chapitre...

Exercices

  • moyenAjustement affine et probabilités - Bac ES Amérique du Nord 2009
  • moyenCalcul d'aires - Bac S Métropole 2009
  • moyenCongruences-Bac S Liban 2009
  • moyenCongruences - Bac S Métropole 2009
  • moyenCube Barycentres - Bac S Amérique du Nord 2009
  • moyenEquations différentielles Probabilités - Bac S Amérique du Nord 2009
  • moyenEtude d'une fonction - Bac S Liban 2009
  • moyenGéométrie analytique - Bac S Centres étrangers 2009
  • moyenGéométrie analytique Cube - Bac S Liban 2009
  • moyenGraphe - Trajet minimal - Bac ES Amérique du Nord 2009
  • moyenGraphes Trajet minimal - Bac ES Pondichéry 2009
  • moyenIntégrales et suites - Bac S Amérique du Nord 2009
  • moyenIntégrales et suites - Bac S Pondichéry 2009
  • moyenProbabilités Lancers successifs - Bac S Pondichéry 2009
  • moyenNombres complexes Lieux géométriques - Bac S Pondichéry 2009
  • moyenNombres complexes - Bac S Métropole 2009
  • moyenNombres complexes et barycentres - Bac S Liban 2009
  • moyenNombres complexes et suites - Bac S Pondichéry 2009
  • moyenNombres complexes et rotations - Bac S Amérique du Nord 2009
  • moyenProbabilités Combinaisons - Bac S Métropole 2009
  • moyenProbabilités : événements indépendants - Bac S Centres étrangers 2009
  • moyenQCM géométrie dans l'espace - Bac S Pondichéry 2009
  • moyenQCM Nombres complexes - Bac S Centres étrangers 2009
  • moyenQCM Probabilités - Bac S Liban 2009
  • moyenRévisions spécialité - Bac S Centres étrangers 2009
  • moyenSuite de fonctions - Bac S Centres étrangers 2009
  • moyenSuites et récurrence - Bac S Métropole 2009

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