Matrice d'incidence

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

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é, la matrice est appelée « matrice d'incidence sommets-arcs^[1] » ; le coefficient de la matrice d'incidence en ligne ${\displaystyle i}$ et en colonne ${\displaystyle j}$ vaut^[2] :

• -1 si l'arc ${\displaystyle x_{j}}$ sort du sommet ${\displaystyle v_{i}}$
• 1 si l'arc ${\displaystyle x_{j}}$ entre dans le sommet ${\displaystyle v_{i}}$
• 0 sinon

Certains auteurs utilisent une autre convention où les rôles de 1 et -1 sont permutés^[3],[4].

Si le graphe est non orienté, la matrice est appelée « matrice d'incidence sommets-arêtes^[1] » ; le coefficient de la matrice d'incidence en ligne ${\displaystyle i}$ et en colonne ${\displaystyle j}$ vaut :

• 1 si le sommet ${\displaystyle v_{i}}$ est une extrémité de l'arête ${\displaystyle x_{j}}$
• 2 si l'arête ${\displaystyle x_{j}}$ est une boucle sur ${\displaystyle 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

Cas du graphe non orienté

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 :

${\displaystyle {\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é

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 :

${\displaystyle {\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).

Propriétés

La transposée de la matrice d'incidence d'un graphe orienté est la matrice d'incidence du graphe transposé.

Relation aux autres matrices remarquables

Relation à la matrice laplacienne

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

La matrice laplacienne ${\displaystyle K(G)}$ est une autre matrice qui décrit le graphe. C'est une matrice n x n où n 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 ${\displaystyle B(G)}$ est la matrice d'incidence d'un graphe orienté ${\displaystyle G}$, on peut en déduire la matrice laplacienne ${\displaystyle K(G)}$ en multipliant ${\displaystyle B(G)}$ par sa transposée ${\displaystyle ^{\operatorname {t} }\!B(G)}$  :

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

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

${\displaystyle 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

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 n où n 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 ${\displaystyle B(G)}$ est la matrice d'incidence d'un graphe non orienté ${\displaystyle G}$, si ${\displaystyle A(G)}$ est sa matrice d'adjacence et si ${\displaystyle D(G)}$ est sa matrice des degrés, alors :

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

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

${\displaystyle 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 :

${\displaystyle 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

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 ${\displaystyle B(G)}$ est la matrice d'incidence d'un graphe non orienté ${\displaystyle G}$, on peut en déduire la matrice d'adjacence ${\displaystyle A(L(G))}$ de son line graph en multipliant la transposée ${\displaystyle ^{\operatorname {t} }\!B(G)}$ par ${\displaystyle B(G)}$, puis en soustrayant deux fois ${\displaystyle I_{p}}$, la matrice unité d'ordre p :

${\displaystyle A(L(G))=\,^{\operatorname {t} }\!B(G)B(G)-2I_{p}}$

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

${\displaystyle 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 : ${\displaystyle 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}}}$

Notes et références

1. M. Gondran et M. Minoux, Graphes et algorithmes, Eyrolles, coll. « Études et recherches d'EdF », 1979 (ISSN 0399-4198), « 1. Généralités sur les graphes », p. 5-6
2. A. Kaufmann, Méthodes et modèles de la recherche opérationnelle, vol. 2, Dunod, coll. « L'économie d'entreprise », 1968, « 43. Matrice d'incidence », p. 335-336
3. « matrice d'incidence », sur publimath.irem.univ-mrs.fr (consulté le 3 mai 2020)
4. « Matrice d'incidence d'un graphe », sur www.bibmath.net (consulté le 3 mai 2020)

Voir aussi

• Matrice d'adjacence
• Théorie des graphes
• Invariant de Parry-Sullivan