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 Trajet minimal - Bac ES Pondichéry 2009

Exercice 2

5 points-Pour les candidats ayant suivi l'enseignement de spécialité
Une agence de voyages organise différentes excursions dans une région du monde et propose la visite de sites incontournables, nommés A, B, C, D, E et F.
Ces excursions sont résumées sur le graphe ci-dessous dont les sommets désignent les sites, les arêtes représentent les routes pouvant être empruntées pour relier deux sites et le poids des arêtes désigne le temps de transport (en heures) entre chaque site.

  1. Justifier que ce graphe est connexe.
  2. Un touriste désire aller du site A au site F en limitant au maximum les temps de transport.
    1. En utilisant un algorithme, déterminer la plus courte chaîne reliant le sommet A au sommet F.
    2. Déduire le temps de transport minimal pour aller du site A au site F.
  3. Un touriste désirant apprécier un maximum de paysages souhaite suivre un parcours empruntant toutes les routes proposées une et une seule fois.
    Si ce parcours existe, le décrire sans justifier; dans le cas contraire justifier qu'un tel parcours n'existe pas.

Corrigé

  1. Deux sommets quelconques de ce graphe peuvent être reliés par une chaîne donc le graphe est connexe.
    1. On utilise l'algorithme de Dijkstra :
       

      A B C D E F Trajet
      0 7(A) \infty 15(A) \infty \infty AB
      19(B) 15(A) 11(B) 23(B) ABE
      19(B) 13(E) 23(B) ABED
      18(D) 23(B) ABEDC
      21(C) ABEDCF

      La plus courte chaîne reliant le sommet A au sommet F est ABEDCF

    2. Le temps de transport minimal pour aller du site A au site F est de 21 heures d'après le tableau précédent.
  2. D'après le théorème d'Euler, il est possible d'emprunter toutes les routes une et une seule fois si le nombre de sommets de degré impair est égal à 0 ou à 2 . Ici, le graphe possède 4 sommets de degré impair : C, D, E, F. Un tel parcours n'existe donc pas.
  Signaler une erreur

Bac S Pondichéry 2009

  • Intégrales et suites - Bac S Pondichéry 2009
  • Nombres complexes Lieux géométriques - Bac S Pondichéry 2009
  • Nombres complexes et suites - Bac S Pondichéry 2009
  • QCM géométrie dans l'espace - Bac S Pondichéry 2009
  • Graphes Trajet minimal - Bac ES Pondichéry 2009
  • Probabilités Lancers successifs - Bac S Pondichéry 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 Algorithme de Dijkstra - Bac ES Métropole 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