Baccalauréat session 2007 MATHÉMATIQUES Série ES

sujet : Nouvelle Calédonie

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

Sur le graphe ci-contre, les sept sommets A, B, C, D, E, F et G correspondent à sept villes.
Une arête reliant deux de ces sommets indique l'existence d'une liaison entre les deux villes correspondantes.

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

Les questions 1, 2 et 3 sont indépendantes.

  1. Est-il possible de trouver un trajet, utilisant les liaisons existantes, qui part d'une des sept villes et y revient en passant une fois et une seule fois par toutes les autres villes ?

    Trouver un trajet, utilisant les liaisons existantes, qui part d'une des sept villes et y revient en passant une fois et une seule fois par toutes les autres villes revient à chercher un cycle de longueur 7 ( à ne pas confondre avec un cycle eulérien). Il suffit de trouver un trajet qui convienne.

  2. On note M la matrice associée au graphe ci-dessus. Les sommets sont rangés suivant l'ordre alphabétique.

    On donne M3=(076104272110915610980311092175098106341076022535322)
    Donner le nombre de chemins de longueur 3 qui relient le sommet A au sommet F. Les citer tous. Aucune justification n'est demandée.

    Le terme aij situé à l'intersection de la ligne i et de la colonne j de la matrice Mn, donne le nombre de chaînes de longueur n reliant le sommet Xi et le sommet Xj du graphe.

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

    On donne ci-dessous et sur le graphe ci-contre les distances exprimées en centaines de kilomètres entre deux villes pour lesquelles il existe une liaison :

    AB : 5 ; AC : 7 ;
    BD : 8 ; BE : 15 ;
    BG : 6 ; CD : 10 ;
    CE : 15 ; DF : 20 ;
    DG : 10 ; EF : 5 ;


    Un représentant de commerce souhaite aller de la ville A à la ville F.

    En expliquant la méthode utilisée, déterminer le trajet qu'il doit suivre pour que la distance parcourue soit la plus courte possible et donner cette distance

    Algorithme de Dijkstra.


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.