Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Graphes - Bac ES Métropole 2018 (spé)

Exercice 3 (5 points)

Candidats de ES ayant choisi l'enseignement de spécialité

Partie A

Un parcours sportif est composé d'un banc pour abdominaux, de haies et d'anneaux. Le graphe orienté ci-dessous indique les différents parcours conseillés partant de D et terminant à F.

Les sommets sont : D (départ), B (banc pour abdominaux), H (haies), A (anneaux) et F (fin du parcours).

Les arêtes représentent les différents sentiers reliant les sommets.

  1. Quel est l'ordre du graphe ?

  2. On note MM la matrice d'adjacence de ce graphe où les sommets sont rangés dans l'ordre alphabétique.

    1. Déterminer MM.

    2. On donne M3=(0000000000010300000000010)M^3 = \begin{pmatrix} 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \end{pmatrix}

      Assia souhaite aller de D à F en faisant un parcours constitué de 3 arêtes.

      Est-ce possible ? Si oui, combien de parcours différents pourra-t-elle emprunter ?

      Préciser ces trajets.

  3. Assia a relevé ses temps de course en minute entre les différents sommets. Ces durées sont portées sur le graphe ci-dessous.

    Lors d'un entraînement, Assia souhaite courir le moins longtemps possible en allant de D à F. Déterminer le trajet pour lequel le temps de course est minimal et préciser la durée de sa course.

Partie B

Le responsable souhaite ajouter une barre de traction notée T. De nouveaux sentiers sont construits et de nouveaux parcours sont possibles.

La matrice d'adjacence NN associée au graphe représentant les nouveaux parcours, dans lequel les sommets sont classés en ordre alphabétique, est

N=(010101000100110010000000110101000100)N = \begin{pmatrix} 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 & 0 \end{pmatrix}

Compléter l'annexe à rendre avec la copie, en ajoutant les arêtes nécessaires au graphe orienté correspondant à la matrice NN.


Annexe

À rendre avec la copie