Matrices et graphes &bull Plus court chemin
Corrigé
36
Ens. de Spécialité
matT_1306_01_04C
Afrique &bull Juin 2013
Exercice 2 &bull 5 points
Dans le graphe ci-dessous, les sommets représentent différentes zones de résidence ou d&rsquo activités d&rsquo une municipalité. Une arête reliant deux de ces sommets indique l&rsquo existence d&rsquo une voie d&rsquo accès principale entre deux lieux correspondants.

associée au graphe (les sommets seront mis dans l&rsquo ordre alphabétique). (0,5 point)
Déterminer, en justifiant, le nombre de chemins de longueur 3 reliant et
, puis donner leur liste. (1 point)

Ce même candidat se trouve à la mairie () quand on lui rappelle qu&rsquo il a un rendez-vous avec le responsable de l&rsquo hôpital situé en zone G.
Durée conseillée : 45 min.
Les thèmes en jeu
Graphe pondéré &bull Matrice associée à un graphe &bull Chaîne de longueur donnée &bull Chaîne eulérienne.
Les conseils du correcteur
donnent le nombre de chemins de longueur 3 entre deux sommets donnés.