Matrice d'incidence

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En mathématiques, et plus particulièrement en théorie des graphes, la matrice d'incidence d'un graphe est une matrice qui décrit le graphe en indiquant quels liens arrivent sur quels sommets.

Définition[modifier | modifier le code]

La matrice d'incidence est une matrice n x p, où n est le nombre de sommets du graphe et p est le nombre de liens (arêtes ou arcs).

Cette matrice est définie de deux façons différentes selon que le graphe est orienté ou non orienté.

Si le graphe est orienté, le coefficient de la matrice d'incidence en ligne i et en colonne j vaut :

  • -1 si l'arc x_j sort du sommet v_i
  • 1 si l'arc x_j entre dans le sommet v_i
  • 0 sinon

Si le graphe est non orienté, le coefficient de la matrice d'incidence en ligne i et en colonne j vaut :

  • 1 si le sommet v_i est une extrémité de l'arête x_j
  • 2 si l'arête x_j est une boucle sur v_i
  • 0 sinon

Pour distinguer les deux définitions, on parle de matrice d'incidence orientée et de matrice d'incidence non orientée.

Exemples[modifier | modifier le code]

Cas du graphe non orienté[modifier | modifier le code]

Un graphe non orienté.

Prenons le cas du graphe ci-contre. Il possède 5 sommets et 6 arêtes, la matrice d'incidence aura donc 5 lignes et 6 colonnes :

  • le sommet 1 est l'aboutissement des arêtes 1 et 5
  • le sommet 2 est l'aboutissement des arêtes 1, 2 et 6
  • le sommet 3 est l'aboutissement des arêtes 2 et 3
  • le sommet 4 est l'aboutissement des arêtes 3 et 4
  • le sommet 5 est l'aboutissement des arêtes 4, 5 et 6

ce qui donne la matrice d'incidence :

\begin{pmatrix}
1 & 0 & 0 & 0 & 1 & 0\\
1 & 1 & 0 & 0 & 0 & 1\\
0 & 1 & 1 & 0 & 0 & 0\\
0 & 0 & 1 & 1 & 0 & 0\\
0 & 0 & 0 & 1 & 1 & 1\\
\end{pmatrix}

On remarque que chaque colonne a une somme égale à 2, puisque chaque arête a deux extrémités.

Cas du graphe orienté[modifier | modifier le code]

Un graphe orienté.

Prenons le cas du graphe ci-contre. Il possède 5 sommets et 6 arcs, la matrice d'incidence aura donc 5 lignes et 6 colonnes :

  • le sommet 1 est l'aboutissement des arcs 1 (qui sort) et 5 (qui entre)
  • le sommet 2 est l'aboutissement des arcs 1 (qui entre), 2 (qui sort) et 6 (qui entre)
  • le sommet 3 est l'aboutissement des arcs 2 (qui entre) et 3 (qui sort)
  • le sommet 4 est l'aboutissement des arcs 3 (qui entre) et 4 (qui sort)
  • le sommet 5 est l'aboutissement des arcs 4 (qui entre), 5 (qui sort) et 6 (qui sort)

ce qui donne la matrice d'incidence :

\begin{pmatrix}
-1 &  0 &  0 &  0 &  1 &  0\\
 1 & -1 &  0 &  0 &  0 &  1\\
 0 &  1 & -1 &  0 &  0 &  0\\
 0 &  0 &  1 & -1 &  0 &  0\\
 0 &  0 &  0 &  1 & -1 & -1\\
\end{pmatrix}

On remarque que chaque colonne a une somme nulle, puisqu'un arc sort forcément d'un sommet pour entrer dans un autre, même s'il s'agit du même sommet (cas d'une boucle).

Relation aux autres matrices remarquables[modifier | modifier le code]

Relation à la matrice laplacienne[modifier | modifier le code]

On peut calculer la matrice laplacienne à partir de la matrice d'incidence de ce graphe.

La matrice laplacienne K(G) est une autre matrice qui décrit le graphe. C'est une matrice n x nn est le nombre de sommets. Les coefficients de sa diagonale contiennent le degré des sommets du graphe, et les autres coefficients en ligne i et en colonne j valent -1 si les sommets i et j sont liés et 0 s'ils ne le sont pas.

Si B(G) est la matrice d'incidence d'un graphe orienté G, on peut en déduire la matrice laplacienne K(G) en multipliant B(G) par sa transposée ^{\operatorname t}\!B(G)  :

K(G) = B(G) ^{\operatorname t}\!B(G)

Par exemple, avec le graphe orienté de la figure ci-contre :


K(G) = \begin{pmatrix}
-1 &  0 &  0 &  0 &  1 &  0\\
 1 & -1 &  0 &  0 &  0 &  1\\
 0 &  1 & -1 &  0 &  0 &  0\\
 0 &  0 &  1 & -1 &  0 &  0\\
 0 &  0 &  0 &  1 & -1 & -1\\
\end{pmatrix} \times
\begin{pmatrix}
-1 &  1 &  0 &  0 &  0\\
 0 & -1 &  1 &  0 &  0\\
 0 &  0 & -1 &  1 &  0\\
 0 &  0 &  0 & -1 &  1\\
 1 &  0 &  0 &  0 & -1\\
 0 &  1 &  0 &  0 & -1\\
\end{pmatrix} =
\begin{pmatrix}
 2 & -1 &  0 &  0 & -1\\
-1 &  3 & -1 &  0 & -1\\
 0 & -1 &  2 & -1 &  0\\
 0 &  0 & -1 &  2 & -1\\
-1 & -1 &  0 & -1 &  3\\
\end{pmatrix}

Relation à la matrice d'adjacence et à la matrice des degrés[modifier | modifier le code]

On peut calculer la matrice d'adjacence et la matrice des degrés à partir de la matrice d'incidence de ce graphe.

La matrice d'adjacence d'un graphe est encore une autre matrice qui décrit le graphe. C'est une matrice n x nn est le nombre de sommets. Elle contient 1 en ligne i et en colonne j si les sommets i et j sont reliés et 0 sinon. Pour un graphe non orienté, cette matrice est symétrique.

La matrice des degrés d'un graphe est une matrice diagonale n x n qui répertorie le degré de chaque sommet. Le coefficient en ligne i et en colonne i indique le degré du sommet i, tous les autres coefficients valent 0.

Si B(G) est la matrice d'incidence d'un graphe non orienté G, si A(G) est sa matrice d'adjacence et si D(G) est sa matrice des degrés, alors :

A(G) + D(G) = B(G) ^{\operatorname t}\!B(G)

Par exemple, avec le graphe orienté de la figure ci-contre :


A(G) + D(G) = \begin{pmatrix}
 1 &  0 &  0 &  0 &  1 &  0\\
 1 &  1 &  0 &  0 &  0 &  1\\
 0 &  1 &  1 &  0 &  0 &  0\\
 0 &  0 &  1 &  1 &  0 &  0\\
 0 &  0 &  0 &  1 &  1 &  1\\
\end{pmatrix} \times
\begin{pmatrix}
 1 &  1 &  0 &  0 &  0\\
 0 &  1 &  1 &  0 &  0\\
 0 &  0 &  1 &  1 &  0\\
 0 &  0 &  0 &  1 &  1\\
 1 &  0 &  0 &  0 &  1\\
 0 &  1 &  0 &  0 &  1\\
\end{pmatrix} =
\begin{pmatrix}
 2 &  1 &  0 &  0 &  1\\
 1 &  3 &  1 &  0 &  1\\
 0 &  1 &  2 &  1 &  0\\
 0 &  0 &  1 &  2 &  1\\
 1 &  1 &  0 &  1 &  3\\
\end{pmatrix}

En isolant la diagonale des autres valeurs, on trouve :


A(G) = \begin{pmatrix}
 0 &  1 &  0 &  0 &  1\\
 1 &  0 &  1 &  0 &  1\\
 0 &  1 &  0 &  1 &  0\\
 0 &  0 &  1 &  0 &  1\\
 1 &  1 &  0 &  1 &  0\\
\end{pmatrix} ;
D(G) = \begin{pmatrix}
 2 &  0 &  0 &  0 &  0\\
 0 &  3 &  0 &  0 &  0\\
 0 &  0 &  2 &  0 &  0\\
 0 &  0 &  0 &  2 &  0\\
 0 &  0 &  0 &  0 &  3\\
\end{pmatrix}

Relation à la matrice d'adjacence du line graph[modifier | modifier le code]

line graph correspondant au graphe non orienté précédent.

Le line graph d'un graphe non orienté est obtenu en remplaçant ses arêtes par des sommets, et en reliant les nouveaux sommets si les anciennes arêtes correspondantes partageaient un sommet. La figure ci-contre montre le line graph du graphe non orienté donné en exemple auparavant.

Si B(G) est la matrice d'incidence d'un graphe non orienté G, on peut en déduire la matrice d'adjacence A(L(G)) de son line graph en multipliant la transposée ^{\operatorname t}\!B(G) par B(G), puis en soustrayant deux fois I_p, la matrice unité d'ordre p :

A(L(G)) = \,^{\operatorname t}\!B(G) B(G) - 2 I_p

Par exemple, avec le line graph de la figure ci-contre :


A(L(G)) = \begin{pmatrix}
 1 &  1 &  0 &  0 &  0\\
 0 &  1 &  1 &  0 &  0\\
 0 &  0 &  1 &  1 &  0\\
 0 &  0 &  0 &  1 &  1\\
 1 &  0 &  0 &  0 &  1\\
 0 &  1 &  0 &  0 &  1\\
\end{pmatrix} \times
\begin{pmatrix}
 1 &  0 &  0 &  0 &  1 &  0\\
 1 &  1 &  0 &  0 &  0 &  1\\
 0 &  1 &  1 &  0 &  0 &  0\\
 0 &  0 &  1 &  1 &  0 &  0\\
 0 &  0 &  0 &  1 &  1 &  1\\
\end{pmatrix} -
\begin{pmatrix}
 2 &  0 &  0 &  0 &  0 &  0\\
 0 &  2 &  0 &  0 &  0 &  0\\
 0 &  0 &  2 &  0 &  0 &  0\\
 0 &  0 &  0 &  2 &  0 &  0\\
 0 &  0 &  0 &  0 &  2 &  0\\
 0 &  0 &  0 &  0 &  0 &  2\\
\end{pmatrix}

En calculant : A(L(G)) =
\begin{pmatrix}
 0 &  1 &  0 &  0 &  1 &  1\\
 1 &  0 &  1 &  0 &  0 &  1\\
 0 &  1 &  0 &  1 &  0 &  0\\
 0 &  0 &  1 &  0 &  1 &  1\\
 1 &  0 &  0 &  1 &  0 &  1\\
 1 &  1 &  0 &  1 &  1 &  0\\
\end{pmatrix}

Voir aussi[modifier | modifier le code]