Rejoignez la communauté !
Co-construisez les ressources dont vous avez besoin et partagez votre expertise pédagogique.
Nombres complexes
Ch. 1
Nombres complexes, point de vue algébrique
Ch. 2
Nombres complexes, point de vue géométrique
Arithmétique
Ch. 3
Divisibilité dans Z
Ch. 4
PGCD et applications
Ch. 5
Nombres premiers
Graphes et matrices
Ch. 6
Calcul matriciel et applications aux graphes
Ch. 7
Suites et matrices
Annexes
Cahier d'algorithmique et de programmation
Chapitre 6
Cours 3
Application du calcul matriciel aux graphes
17 professeurs ont participé à cette page
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).
Le zoom est accessible dans la version Premium.
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}.
Le zoom est accessible dans la version Premium.
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.
Oups, une coquille
j'ai une idée !
Nous préparons votre pageNous vous offrons 5 essais
YolèneÉmilieJean-PaulFatimaSarah