Baccalauréat 2015 MATHÉMATIQUES Série ES-L

sujet : Centres Étrangers 2015

Corrigé de l'exercice 2 : candidats ayant suivi l'enseignement de spécialité ES

On a schématisé ci-dessous une partie du plan du métro londonien par un graphe Γ dont les sommets sont les stations et les arêtes sont les lignes desservant ces stations.
Chaque station de métro est désignée par son initiale comme indiqué dans la légende.

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

Légende

  • B : Bond Street
  • E : Embankment
  • G : Green Park
  • H : Holborn
  • K : King's Cross St Pancras
  • O : Oxford Circus
  • P : Piccadilly Circus
  • W : Westminster
    1. Déterminer en justifiant si le graphe Γ est connexe.

      La chaîne B - O - K - H - P - E - W - G contient tous les sommets du graphe. Par conséquent, pour toute paire de sommets distincts, il existe une chaîne les reliant donc le graphe Γ est connexe.


    2. Déterminer en justifiant si le graphe Γ est complet.

      Les sommets B et K ne sont pas adjacents donc le graphe Γ n'est pas complet.


  1. Déterminer, en justifiant, si le graphe Γ admet une chaîne eulérienne. Si oui, donner une telle chaîne.

    Graphe, chaîne eulérienne : L'illustration svg n'est pas visible par votre navigateur.

    Légende

    • B : Bond Street
    • E : Embankment
    • G : Green Park
    • H : Holborn
    • K : King's Cross St Pancras
    • O : Oxford Circus
    • P : Piccadilly Circus
    • W : Westminster

    Le graphe étant connexe, déterminons le degré de chacun des sommets :

    Sommets BEGHKOPW
    Degré22432542

    Le graphe est connexe et il n'y a que deux sommets H et O de degré impair, il existe donc une chaîne eulérienne d'extrémités H et O. Par exemple la chaîne O - H - K - O - P - G - O - B - G - W - E - P - H.


  2. Donner la matrice d'adjacence M du graphe Γ (les sommets seront rangés dans l'ordre alphabétique).

    La matrice d'adjacence M du graphe Γ est : M=(0010010000000011100001110000111000010100101110100111010001100000)


    Pour la suite de l'exercice, on donne la matrice M3=(23642731301123646144491064144588322452731739878103361083104114631310).

  3. Un touriste se trouve à la station Holborn. Il prévoit de se rendre à la station Green Park en utilisant exactement trois lignes de métro sur son trajet.

    1. Sans utiliser le graphe, donner le nombre de trajets possibles et justifier la réponse.

      Les termes de la matrice M3 donnent le nombre de chaînes de longueur 3 entre deux sommets du graphe.

      Le terme a4,3=4 de la matrice M3 situé à l'intersection de la quatrième ligne et de la troisième colonne est égal à 4. En partant de la station Holborn, il existe quatre trajets utilisant exactement trois lignes de métro pour se rendre à la station Green Park.


    2. Donner les trajets possibles .

      Les quatre trajets possibles sont : H - K - O - G ; H - O - B - G ; H - O - P - G et H - P - O - G.


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

Légende

  • B : Bond Street
  • E : Embankment
  • G : Green Park
  • H : Holborn
  • K : King's Cross St Pancras
  • O : Oxford Circus
  • P : Piccadilly Circus
  • W : Westminster

Sur le graphe pondéré ci-dessus, on a indiqué la durée, exprimée en minutes, des trajets entre chaque station (la durée est indiquée sur chaque arête du graphe Γ ).

  1. À partir de la station Westminster, ce touriste doit rejoindre la station King's Cross St Pancras le plus rapidement possible pour prendre un train.
    En utilisant l'algorithme de Dijkstra, déterminer le trajet permettant de relier la station Westminster à la station King's Cross St Pancras en une durée minimale. On précisera cette durée.

    Graphe, algorithme de Dijkstra : L'illustration svg n'est pas visible par votre navigateur.

    Légende

    • B : Bond Street
    • E : Embankment
    • G : Green Park
    • H : Holborn
    • K : King's Cross St Pancras
    • O : Oxford Circus
    • P : Piccadilly Circus
    • W : Westminster

    BEGHKOPWSommet sélectionné
    0

    W (0)

    2 (W) 3 (W)

    E (2)

    3 (W) 6 (E)

    G (3)

    4 (G)5 (G) 5 (G)

    B (4)

    5 (G)5 (G)

    O (5)

    6 (O) 10 (O)5 (G)

    P (5)

    6 (O) 10 (O)

    H (6)

    9 (H)

    K (9)


    Le sommet K étant marqué, pour lire la chaîne de poids minimal, on part de K et on "remonte" la chaîne en suivant les prédécesseurs. KHOGW.

    Le trajet permettant de relier la station Westminster à la station King's Cross St Pancras en une durée minimale est W - G - O - H - K. La durée dece trajet est de 9 minutes.



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.