Graphe et matrice associée - exercice

Dans cet exercice, vous allez devoir concevoir des matrices à partir d'un graphe représentant les plus grandes villes de départements et les routes qui les relient.

Enoncé de l'exercice

Le graphe affiché représente les villes principales des départements D₁, D₂, et D₃ et les axes routiers les reliant.

1. Combien de chemins permettent de relier la ville M₁ à la ville P₁ ?
2. Combien de chemins permettent de relier la ville M₃ à la ville P₂ ?
3. Donner la matrice A = (a_i,j) où le coefficient a_i,j représente « le nombre de routes reliant la ville M_i avec la ville N_j » pour i ∈ [1 ; 3] et j ∈ [1 ; 2].
4. Donner la matrice B = (b_i,j) où le coefficient b_i,j représente « le nombre de routes reliant la ville N_i avec la ville P_j » pour i ∈ [1 ; 2] et j ∈ [1 ; 2].