Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Graphes - Bac blanc ES Sujet 2 - Maths-cours 2018 (spé)

Exercice 4 (5 points)

Candidats ayant suivi l'enseignement de spécialité

Une agence de tourisme propose la visite de certains monuments parisiens.

Chacun de ces monuments est désigné par une lettre comme suit :

Cette agence fait appel à une société de transport par autocar qui propose les liaisons suivantes (chacune de ces liaisons pouvant s'effectuer dans les deux sens de circulation) :

  1. Expliquer pourquoi il est possible de trouver un trajet empruntant une fois et une seule chacune des dix liaisons indiquées sur le graphe.
    Donner un exemple d'un tel trajet.

    1. Donner la matrice d'adjacence MM associée à ce graphe en classant les sommets par ordre alphabétique.

    2. On donne :

      M2=(421321242222123131321311223141121112) M^2 = \begin{pmatrix} 4 &2 &1 &3 &2 &1 \\ 2 &4 &2 &2 &2 &2 \\ 1 &2 &3 &1 &3 &1 \\ 3 &2 &1 &3 &1 &1 \\ 2 &2 &3 &1 &4 &1\\ 1 &2 &1 &1 &1 &2 \end{pmatrix}

      M3=(610951061088810498485458849410105966644462) M^3 = \begin{pmatrix} 6 &10 &9 &5 &10 &6 \\ 10 &8 &8 &8 &10 &4 \\ 9 &8 &4 &8 &5 &4 \\ 5 &8 &8 &4 &9 &4 \\ 10 &10 &5 &9 &6 &6\\ 6 &4 &4 &4 &6 &2 \end{pmatrix}

      Combien y a-t-il de trajets permettant de relier la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant au maximum trois liaisons.
      Justifier votre réponse.

  3. On complète le graphe précédent en indiquant, sur chacune des branches, la durée du trajet, en minutes, entre deux monuments.

    On souhaite aller de la tour Montparnasse à la Basilique du Sacré-Cœur de Montmartre.

    En utilisant un algorithme, déterminer le trajet le plus rapide ainsi que la durée de ce trajet.

Corrigé

  1. Trouver un trajet qui emprunte une fois et une seule chacune des liaisons indiquées sur le graphe revient à déterminer une chaîne eulérienne.

    Le théorème d'Euler indique qu'un graphe connexe contient une chaîne eulérienne si et seulement s'il ne possède que 0 ou 2 sommets de degré impair.

    Les degrés des sommets sont indiqués dans le tableau ci-après :

    Sommet E L M N S T
    Degré 4 4 3 3 4 2

    Le graphe comporte deux sommets de degré impair : M et N. Il est donc possible de relier M (Tour Montparnasse) à N (Cathédrale Notre-Dame de Paris) en empruntant une fois et une seule chacune des liaisons; par exemple : M-E-T-S-E-L-S-N-L-M-N.

    1. En classant les sommets par ordre alphabétique, on obtient la matrice d'adjacence suivante :

      M=(011011101110110100011010110101100010) M = \begin{pmatrix} 0 &1 &1 &0 &1 &1 \\ 1 &0 &1 &1 &1 &0 \\ 1 &1 &0 &1 &0 &0 \\ 0 &1 &1 &0 &1 &0 \\ 1 &1 &0 &1 &0 &1\\ 1 &0 &0 &0 &1 &0 \end{pmatrix}

    2. Le coefficient situé sur la 4e4^{\text{e}} ligne (correspondant à la cathédrale Notre-Dame de Paris) et la 1ère1^{\text{ère}} colonne (correspondant à la tour Eiffel) de la matrice MM est égal à 0.
      Il n'y a donc aucun trajet reliant la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant une et une seule liaison.

      Le coefficient situé sur la 4e4^{\text{e}} ligne et la 1ère1^{\text{ère}} colonne de la matrice M2M^2 est égal à 3.
      Il y a donc 3 trajets reliant la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant exactement deux liaisons.

      Le coefficient situé sur la 4e4^{\text{e}} ligne et la 1ère1^{\text{ère}} colonne de la matrice M3M^3 est égal à 5.
      Il y a donc 5 trajets reliant la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant exactement trois liaisons.

      Au total, on trouve qu'il existe exactement huit trajets permettant de relier la cathédrale Notre-Dame de Paris et la tour Eiffel en utilisant au maximum trois liaisons.

  3. On utilise l'algorithme de Dijkstra :

    Reportez-vous à la page « méthode » : l'algorithme de Dijkstra étape par étape pour obtenir la méthode de construction détaillée de ce tableau.

    Le trajet le plus rapide pour aller de la tour Montparnasse à la Basilique du Sacré-Cœur de Montmartre est le trajet M-N-L-S, c'est à dire Montparnasse - Notre-Dame de Paris - Louvre - Sacré-Cœur.

    Sa durée est de 11 minutes.

Autres exercices de ce sujet :

Dans ce chapitre :

Cours

Exercices

Méthodes