Ressource affichée de l'autre côté. 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 ai,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.
Remarque
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.
Exemple
En notant M la matrice d'adjacence du graphe ci‑dessous obtenue en rangeant les sommets dans l'ordre alphabétique,
on a M=0010101000011110010010010110110100101010001110100.
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
Propriété
Soient n et k deux entiers naturels non nuls et 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 Mk 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.
Remarque
M1=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.
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
Exemple
En reprenant l'exemple précédent, on a M4=2320132016523202012181441813122262712172018 6 21822016142783517245412217101123181720241131.
Il existe donc 27 chaînes de longueur 4 reliant le sommet C au sommet E.
On a M2=3212102231210111303112203002113042200102212112214 donc il n'existe aucune chaîne de longueur 2 reliant le sommet B au sommet F.
Ressource affichée de l'autre côté. 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.
Énoncé
On considère le graphe orienté ci‑après.
1. Déterminer la matrice d'adjacence M de ce graphe en classant les sommets par ordre alphabétique.
2. a. Déterminer le nombre de chemins de longueur 3 reliant A à C.
b. Déterminer le nombre de chemins de longueur 3 reliant C à B.
Ressource affichée de l'autre côté. Faites défiler pour voir la suite.
Méthode
1. On détermine la matrice d'adjacence M en prenant
garde à l'orientation des arêtes.
2. • On souhaite déterminer le nombre de chemins de
longueur 3 : cela nécessite donc de connaître M3.
• 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.
Solution
1. On a M=0010010001000111000000010.
2. a. On a M3=1001010011101000001100100.
Il y a donc une unique chaîne de longueur 3 reliant A à C. On constate qu'il n'y a pas de chemin de longueur 3 reliant C à A.
b. D'après la matrice M3, il n'y a donc pas de chemin de longueur 3 reliant C à B.