Savoir utiliser la matrice d'adjacence d'un graphe - Exercice 1

6 min
10
On considère le graphe GG représenté ci-dessous :
Question 1

Donner la matrice d’adjacence MM du graphe GG (les sommets seront rangés dans l’ordre alphabétique)

Correction
M=(0110110010100100110110010)M=\left(\begin{array}{ccccc} {0} & {1} & {1} & {0} & {1} \\ {1} & {0} & {0} & {1} & {0} \\ {1} & {0} & {0} & {1} & {0} \\ {0} & {1} & {1} & {0} & {1} \\ {1} & {0} & {0} & {1} & {0} \end{array}\right)
Question 2

À l'aide de la calculatrice, donner M2M^{2} .

Correction
D'après la calculatrice, on obtient :
M2=(3003002202022023003002202)M^{2}=\left(\begin{array}{ccccc} {3} & {0} & {0} & {3} & {0} \\ {0} & {2} & {2} & {0} & {2} \\ {0} & {2} & {2} & {0} & {2} \\ {3} & {0} & {0} & {3} & {0} \\ {0} & {2} & {2} & {0} & {2} \end{array}\right)
Question 3

Combien y a-t-il de chemins de longueur 22 reliant BB à CC ?

Correction
Soit GG un graphe et MM sa matrice d’adjacence.
Le nombre de chemins de longueur nn joignant le sommet ii au sommet jj est donné par le terme d’indice i,ji,j de la matrice MnM^{n}
Pour déterminer le nombre de chemins de longueur 22 reliant le sommet BB au sommet CC, on doit calculer M2M^{2} . D'après la question 22, nous connaissons M2M^{2} .
Nous allons prendre la valeur de l'intersection entre la deuxième ligne (en référence au sommet BB) et la troisième colonne (en référence au sommet CC)
Nous mettons en rouge\red{\text{en rouge}} cette valeur dans la matrice M2M^{2}
M2=(3003002202022023003002202)M^{2}=\left(\begin{array}{ccccc} {3} & {0} & {0} & {3} & {0} \\ {0} & {2} & {{\color{red}{2}}} & {0} & {2} \\ {0} & {2} & {2} & {0} & {2} \\ {3} & {0} & {0} & {3} & {0} \\ {0} & {2} & {2} & {0} & {2} \end{array}\right)
Il y a donc 2{\color{red}{2}} chemins de longueur 22 reliant le sommet BB au sommet CC .
Question 4

À l'aide de la calculatrice, donner M3M^{3} .

Correction
D'après la calculatrice, on obtient :
M3=(0660660060600600660660060)M^{3}=\left(\begin{array}{ccccc} {0} & {6} & {6} & {0} & {6} \\ {6} & {0} & {0} & {6} & {0} \\ {6} & {0} & {0} & {6} & {0} \\ {0} & {6} & {6} & {0} & {6} \\ {6} & {0} & {0} & {6} & {0} \end{array}\right)
Question 5

Combien y a-t-il de chemins de longueur 33 reliant AA à EE ?

Correction
Soit GG un graphe et MM sa matrice d’adjacence.
Le nombre de chemins de longueur nn joignant le sommet ii au sommet jj est donné par le terme d’indice i,ji,j de la matrice MnM^{n}
Pour déterminer le nombre de chemins de longueur 33 reliant le sommet AA au sommet EE, on doit calculer M3M^{3} . D'après la question 44, nous connaissons M3M^{3} .
Nous allons prendre la valeur de l'intersection entre la première ligne (en référence au sommet AA) et la cinquième colonne (en référence au sommet EE)
Nous mettons en rouge\red{\text{en rouge}} cette valeur dans la matrice M3M^{3}
M3=(0660660060600600660660060)M^{3}=\left(\begin{array}{ccccc} {0} & {6} & {6} & {0} & {{\color{red}{6}}} \\ {6} & {0} & {0} & {6} & {0} \\ {6} & {0} & {0} & {6} & {0} \\ {0} & {6} & {6} & {0} & {6} \\ {6} & {0} & {0} & {6} & {0} \end{array}\right)
Il y a donc 6{\color{red}{6}} chemins de longueur 33 reliant le sommet AA au sommet EE .

Signaler une erreur

Aide-nous à améliorer nos contenus en signalant les erreurs ou problèmes que tu penses avoir trouvés.

Connecte-toi ou crée un compte pour signaler une erreur.