Se connecter
ou

Déterminer et utiliser la matrice d'adjacence d'un graphe

Pour construire la matrice d'adjacence M d'un graphe, on liste sommet par sommet les arêtes qui les relient entre eux.

Une matrice d'adjacence à la puissance n permet de connaître le nombre de chemins de longueurs n entre n'importe quel couple de point du graphe.

On considère le graphe suivant :

-

Construire sa matrice d'adjacence M puis déterminer le nombre de chaînes de longueur 3 reliant les sommets A et C.

Etape 1

Ranger les sommets dans l'ordre

On range les sommets dans un ordre déterminé.

  • Si les sommets sont des lettres, on les range de préférence dans l'ordre alphabétique.
  • Si ce sont des numéros, on les range dans l'ordre croissant.

On range les sommets dans l'ordre alphabétique : A, B, C, D.

Etape 2

Construire la matrice M vide

On construit la matrice vide en associant à chaque ligne et à chaque colonne un sommet, en respectant l'ordre déterminé précédemment.

On construit la matrice vide, en notant les en-têtes des lignes et des colonnes.

\(\displaystyle{M = \begin{pmatrix} & A & B & C &D \cr\cr A & & & & \cr\cr B & & & & \cr\cr C & & & & \cr\cr D & & & & \end{pmatrix}}\)

Etape 3

Remplir la matrice M ligne par ligne

Pour chaque ligne, on complète colonne par colonne :

  • Si le sommet associé à cette ligne est relié (en étant le point de départ de l'arrête dans le cas d'un graphe orienté), au sommet associé à la colonne, on marque le chiffre 1.
  • Sinon on marque le chiffre 0.

La première ligne correspond aux arêtes partant du sommet A :

  • Il n'y a pas de boucle en A : on note donc 0 sur la première colonne.
  • Il y en a une vers B : on note donc 1 sur la deuxième colonne.
  • Il y en a une vers C : on note donc 1 sur la troisième colonne.
  • Il y en a une vers D : on note donc 1 sur la dernière colonne.

On obtient :

\(\displaystyle{M = \begin{pmatrix} & A & B & C &D \cr\cr A &0 &1 & 1&1 \cr\cr B & & & & \cr\cr C & & & & \cr\cr D & & & & \end{pmatrix}}\)

La deuxième ligne correspond aux arêtes partant du sommet B :

  • Il y en a une vers A : on note donc 1 sur la première colonne.
  • Il y en a une vers D : on note donc 1 sur la dernière colonne.

On note 0 au niveau des autres colonnes.

On obtient :

\(\displaystyle{M = \begin{pmatrix} & A & B & C &D \cr\cr A &0 &1 & 1&1 \cr\cr B & 1& 0&0 &1 \cr\cr C & & & & \cr\cr D & & & & \end{pmatrix}}\)

La troisième ligne correspond aux arêtes partant du sommet C :

  • Il y en a une vers A : on note donc 1 sur la première colonne.
  • Il y en a une vers elle-même : on note donc 1 sur la troisième colonne.

On note 0 au niveau des autres colonnes.

On obtient :

\(\displaystyle{M = \begin{pmatrix} & A & B & C &D \cr\cr A &0 &1 & 1&1 \cr\cr B & 1& 0&0 &1 \cr\cr C & 1& 0& 1& 0\cr\cr D & & & & \end{pmatrix}}\)

La dernière ligne correspond aux arêtes partant du sommet D :

  • Il y en a une vers A : on note donc 1 sur la première colonne.
  • Il y en a une vers B : on note donc 1 sur la deuxième colonne.

On note 0 au niveau des autres colonnes.

Finalement, on obtient la matrice d'adjacence M :

\(\displaystyle{M = \begin{pmatrix} & A & B & C &D \cr\cr A &0 &1 & 1&1 \cr\cr B & 1& 0&0 &1 \cr\cr C & 1& 0& 1& 0\cr\cr D & 1& 1& 0&0 \end{pmatrix}}\)

Etape 4

Calculer \(\displaystyle{M^n}\)

Afin de trouver le nombre de chaînes possibles de longueur n reliant deux points d'un graphe, on doit préalablement calculer \(\displaystyle{M^n}\).

Sauf mention contraire de l'énoncé, on peut effectuer le calcul de \(\displaystyle{M^n}\) à la calculatrice.

On cherche le nombre de chemins de longueur 3 entre les sommets A et C. On calcule donc au préalable \(\displaystyle{M^3}\).

À l'aide la calculatrice, on obtient :

\(\displaystyle{M^3 = \begin{pmatrix} 3 &4 & 4&4 \cr\cr 4& 2& 2& 3 \cr\cr 4& 2& 3& 2 \cr\cr 4& 3& 2& 2\end{pmatrix}}\)

Etape 5

En déduire le nombre de chaînes de longueur n

Le nombre de chaînes de longueur n partant du sommet I et allant vers le sommet J est égal au coefficient de \(\displaystyle{a_{ij}}\) (le coefficient à l'intersection de la ligne correspondant au sommet I et de la colonne correspondant au sommet J) de la matrice \(\displaystyle{M^n}\).

On en déduit le nombre de chemins de longueur n reliant les deux points.

Dans un graphe non orienté, le nombre de chaînes reliant I à J est égal au nombre de chemins reliant J à I, donc \(\displaystyle{a_{ij}=a_{ji}}\).

Le nombre de chaînes de longueur 3 entre les sommets A et C est donné par le coefficient correspondant à la ligne A et à la colonne C de la matrice \(\displaystyle{M^3}\).

\(\displaystyle{M^3 = \begin{pmatrix} 3 &4 & \color{Red}{4}&4 \cr\cr 4& 2& 2& 3 \cr\cr 4& 2& 3& 2 \cr\cr 4& 3& 2& 2\end{pmatrix}}\)

Il existe donc 4 chaînes de longueur 3 reliant A à C.

Si le graphe n'est pas orienté, la matrice d'adjacence est symétrique.

La présence d'un 1 sur la diagonale de la matrice M signifie que le sommet en question est relié à lui-même.