Matrice d'adjacence - Comptage de chaînes (3) - Corrigé

Énoncé

Le lycée de Lucie est situé à Paris proche de la station de métro Invalides. Elle a fait un relevé du plan de métro simplifié du quartier en utilisant seulement les stations suivantes :

• Champs-Élysées Clemenceau (CE)
  
• Châtelet (CH)
• Concorde (CO)
• Duroc (D)
• Charles de Gaulle Etoile (E)
• Franklin Roosevelt (F)
• Invalides (I)
• Montparnasse (M)
• La Motte Piquet Grenelle (MP)
• Odéon (O)
• Pasteur (P)
• Sèvres Babylone (S)
• Trocadéro (T)

Voici le graphe qu'elle a dessiné.

1. Écrire la matrice d'adjacence de ce graphe (on notera les sommets dans l'ordre alphabétique des abréviations ci-dessus).

2. Donner un exemple de chaîne à 5 arêtes reliant Concorde et La Motte Piquet Grenelle.

3. Combien y a-t-il de chaînes à 5 arêtes reliant Concorde et La Motte Piquet Grenelle ?

`` Solution

1. La matrice d'adjacence de graphe est :  \(A=\begin{pmatrix} 0&0&1&0&0&1&1&0&0&0&0&0&0\\0&0&1&0&0&0&0& 0&0&1&0&0&0\\1&1&0&0&0&0&1&0&0&0&0&1&0\\0&0&0&0&0&0&1&1&1&0&0&1&0\\0&0&0&0&0&1&0&0&0&0&0&0&1\\1&0&0&0&1&0&0&0&0&0&0&0&1\\1&0&1&1&0&0&0&0&1&0&0&0&0\\0&0&0&1&0&0&0&0&0&1&1&1&0\\0&0&0&1&0&0&1&0&0&0&1&0&1\\0&1&0&0&0&0&0&1&0&0&0&1&0\\0&0&0&0&0&0&0&1&1&0&0&0&0\\0&0&1&1&0&0&0&1&0&1&0&0&0\\0&0&0&0&1&1&0&0&1&0&0&0&0\end{pmatrix}\)

2. Un exemple de chaîne à 5 arêtes reliant Concorde à La Motte Piquet Grenelle : Concorde - Châtelet - Odéon - Montparnasse - Pasteur - La Motte Piquet Grenelle

3. Pour calculer le nombre de chaînes à 5 arêtes reliant Concorde à La Motte Piquet Grenelle, il faut calculer  \(A^5\)  et prendre son coefficient de la 3^e ligne / 9^e colonne.
On le fait à la calculatrice et on trouve 50 chaînes possibles !