Maths-cours

COURS & EXERCICES DE MATHÉMATIQUES

Close

Matrice de transition - Bac ES Pondichéry 2011

Exercice 3

Candidats ayant suivi l'enseignement de spécialité

Un orchestre doit effectuer une tournée passant par les villes A, B, C, D, E, F, G et H en utilisant le réseau autoroutier.

Le graphe Γ\Gamma ci-dessous représente les différentes villes de la tournée et les autoroutes reliant ces villes (une ville est représentée par un point, une autoroute par une arête) :

Graphe Bac ES Pondichéry 2011

  1. Est-il possible d'organiser la tournée en passant au moins une fois par chaque ville, tout en empruntant une fois et une seule chaque tronçon d'autoroute? (la réponse sera justifiée).
    Si oui citer un trajet de ce type.

  2. On appelle M la matrice associée au graphe Gamma (les sommets étant pris dans l'ordre alphabétique). On donne la matrice M3M^{3} :

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

    Combien existe-t-il de chemins de longueur 3 reliant B à H ? (la réponse devra être justifiée).

    Préciser ces chemins.

  3. Des contraintes de calendrier imposent en fait d'organiser un concert dans la ville F immédiatement après un concert dans la ville A.

    Le graphe Γ\Gamma est complété ci-dessous par les longueurs en kilomètres de chaque tronçon (les longueurs des segments ne sont pas proportionnelles aux distances).

    Graphe 2 Bac ES Pondichéry 2011

    Déterminer, en utilisant un algorithme dont on citera le nom, le trajet autoroutier le plus court (en kilomètres) pour aller de A à F.

    Préciser la longueur en kilomètres de ce trajet.