Chapitre 6
Cours 3
Application du calcul matriciel aux graphes
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Définition
Soit n un entier naturel non nul. On considère un graphe d'ordre n (orienté ou non) dont les sommets sont numérotés de 1 à n, puis rangés dans l'ordre croissant.
La matrice d'adjacence de ce graphe est la matrice carrée de taille n, dont le coefficient a_{i, j} est égal au nombre d'arêtes partant du sommet i pour arriver au sommet j.
La matrice d'adjacence de ce graphe est la matrice carrée de taille n, dont le coefficient a_{i, j} est égal au nombre d'arêtes partant du sommet i pour arriver au sommet j.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
La
matrice d'adjacence
d'un graphe non
orienté est symétrique.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Exemple
En notant \text{M} la matrice d'adjacence du graphe ci‑dessous obtenue en rangeant les sommets dans l'ordre alphabétique,
on a \mathrm{M}=\left(\begin{array}{ccccccc} 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 \end{array}\right).
on a \mathrm{M}=\left(\begin{array}{ccccccc} 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 & 1 & 0 & 0 \end{array}\right).
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Propriété
Soient n et k deux entiers naturels non nuls et \text{M} la matrice d'adjacence d'un graphe d'ordre n, dont les sommets sont numérotés de 1 à n et rangés dans l'ordre croissant.
Le terme de la i-ème ligne et de la j-ième colonne de la matrice \mathrm{M}^{k} donne le nombre de chaînes (ou de chemins) de longueur k reliant le sommet i au sommet j.
Le terme de la i-ème ligne et de la j-ième colonne de la matrice \mathrm{M}^{k} donne le nombre de chaînes (ou de chemins) de longueur k reliant le sommet i au sommet j.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
\mathrm{M}^{1}=\mathrm{M} donne le nombre
de chaînes (ou de
chemins) de longueur
1 reliant deux
sommets.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Démonstration
Voir exercice p. 198.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Exemple
En reprenant l'exemple précédent, on a \mathrm{M}^{4}=\left(\begin{array}{ccccccc}
23 & 20 & 13 & 20 & \colorbox{#fde2c4}{16} & 5 & 23 \\
20 & 20 & 12 & 18 & \colorbox{#fde2c4}{14} & 4 & 18 \\
\colorbox{#fde2c4}{13} & \colorbox{#fde2c4}{12} & \colorbox{#fde2c4}{22} & \colorbox{#fde2c4}{ 6 } & \boldsymbol{\colorbox{#f7cc91}{\color{white}27}} & 12 & 17 \\
20 & 18 & 6 & 21 & 8 & 2 & 20 \\
16 & 14 & 27 & 8 & 35 & 17 & 24 \\
5 & 4 & 12 & 2 & 17 & 10 & 11 \\
23 & 18 & 17 & 20 & 24 & 11 & 31
\end{array}\right).
Il existe donc 27 chaînes de longueur 4 reliant le sommet \text{C} au sommet \text{E}.
On a \mathrm{M}^{2}=\left(\begin{array}{ccccccc} 3 & 2 & 1 & 2 & 1 &\colorbox{#fde2c4}{0} & 2 \\ \colorbox{#fde2c4}{2} & \colorbox{#fde2c4}{3} & \colorbox{#fde2c4}{1} & \colorbox{#fde2c4}{2} & \colorbox{#fde2c4}{1} & \boldsymbol{\colorbox{#f7cc91}{\color{white}0}} & 1 \\ 1 & 1 & 3 & 0 & 3 & 1 & 1 \\ 2 & 2 & 0 & 3 & 0 & 0 & 2 \\ 1 & 1 & 3 & 0 & 4 & 2 & 2 \\ 0 & 0 & 1 & 0 & 2 & 2 & 1 \\ 2 & 1 & 1 & 2 & 2 & 1 & 4 \end{array}\right) donc il n'existe aucune chaîne de longueur 2 reliant le sommet \text{B} au sommet \text{F}.
Il existe donc 27 chaînes de longueur 4 reliant le sommet \text{C} au sommet \text{E}.
On a \mathrm{M}^{2}=\left(\begin{array}{ccccccc} 3 & 2 & 1 & 2 & 1 &\colorbox{#fde2c4}{0} & 2 \\ \colorbox{#fde2c4}{2} & \colorbox{#fde2c4}{3} & \colorbox{#fde2c4}{1} & \colorbox{#fde2c4}{2} & \colorbox{#fde2c4}{1} & \boldsymbol{\colorbox{#f7cc91}{\color{white}0}} & 1 \\ 1 & 1 & 3 & 0 & 3 & 1 & 1 \\ 2 & 2 & 0 & 3 & 0 & 0 & 2 \\ 1 & 1 & 3 & 0 & 4 & 2 & 2 \\ 0 & 0 & 1 & 0 & 2 & 2 & 1 \\ 2 & 1 & 1 & 2 & 2 & 1 & 4 \end{array}\right) donc il n'existe aucune chaîne de longueur 2 reliant le sommet \text{B} au sommet \text{F}.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Application et méthode - 5
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Énoncé
On considère le graphe orienté ci‑après.
1. Déterminer la matrice d'adjacence \text{M} de ce graphe en classant les sommets par ordre alphabétique.
2. a. Déterminer le nombre de chemins de longueur 3 reliant \text{A} à \text{C}.
b. Déterminer le nombre de chemins de longueur 3 reliant \text{C} à \text{B}.
1. Déterminer la matrice d'adjacence \text{M} de ce graphe en classant les sommets par ordre alphabétique.
2. a. Déterminer le nombre de chemins de longueur 3 reliant \text{A} à \text{C}.
b. Déterminer le nombre de chemins de longueur 3 reliant \text{C} à \text{B}.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
1. On détermine la matrice d'adjacence \text{M} en prenant
garde à l'orientation des arêtes.
2. • On souhaite déterminer le nombre de chemins de longueur \color{lightseagreen}\text{3} : cela nécessite donc de connaître \mathrm{M}^{\color{lightseagreen}3}.
• On repère ensuite le coefficient demandé dans cette matrice.
2. • On souhaite déterminer le nombre de chemins de longueur \color{lightseagreen}\text{3} : cela nécessite donc de connaître \mathrm{M}^{\color{lightseagreen}3}.
• On repère ensuite le coefficient demandé dans cette matrice.
Ressource affichée de l'autre côté.
Faites défiler pour voir la suite.
Faites défiler pour voir la suite.
Solution
1. On a \mathrm{M}=\left(\begin{array}{lllll}
0 & 1 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 \\
0 & 0 & 1 & 0 & 1 \\
0 & 1 & 1 & 0 & 0
\end{array}\right).
2. a. On a \mathrm{M}^{3}=\left(\begin{array}{lllll} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \end{array}\right).
Il y a donc une unique chaîne de longueur 3 reliant \text{A} à \text{C}. On constate qu'il n'y a pas de chemin de longueur 3 reliant \text{C} à \text{A}.
b. D'après la matrice \mathrm{M}^{3}, il n'y a donc pas de chemin de longueur 3 reliant \text{C} à \text{B}.
2. a. On a \mathrm{M}^{3}=\left(\begin{array}{lllll} 1 & 1 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 \end{array}\right).
Il y a donc une unique chaîne de longueur 3 reliant \text{A} à \text{C}. On constate qu'il n'y a pas de chemin de longueur 3 reliant \text{C} à \text{A}.
b. D'après la matrice \mathrm{M}^{3}, il n'y a donc pas de chemin de longueur 3 reliant \text{C} à \text{B}.
Pour s'entraîner
Exercices et p. 191
Une erreur sur la page ? Une idée à proposer ?
Nos manuels sont collaboratifs, n'hésitez pas à nous en faire part.
j'ai une idée !
Oups, une coquille
