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.
Remarque
La
matrice d’adjacence
d’un graphe non
orienté est symétrique.
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⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞.
Définition
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.
Remarque
M1=M donne le nombre
de chaînes (ou de
chemins) de longueur
1 reliant deux
sommets.
En reprenant l’exemple précédent, on a M4=⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎛2320132016523202012181441813122262712172018621822016142783517245412217101123181720241131⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎞.
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.
Application et méthode - 5
Énoncé
On considère le graphe orienté ci‑contre.
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.
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.
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.
Utilisation des cookies
En poursuivant votre navigation sans modifier vos paramètres, vous acceptez l'utilisation des cookies permettant le bon fonctionnement du service. Pour plus d’informations, cliquez ici.