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

-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

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 $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]

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]

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).

Propriétés[modifier | modifier le code]

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[modifier | modifier le code]

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

La matrice laplacienne $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 $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]

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 $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 non 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]

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)-2I_{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}}$

Notes et références[modifier | modifier le code]

↑ ^{a et b} 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
↑ 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
↑ « matrice d'incidence », sur publimath.irem.univ-mrs.fr (consulté le 3 mai 2020)
↑ « Matrice d'incidence d'un graphe », sur www.bibmath.net (consulté le 3 mai 2020)

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Matrice d'incidence, sur Wikimedia Commons
matrice d’incidence, sur le Wiktionnaire
Matrice d'incidence, sur Wikiversity

Portail des mathématiques

[G&M-1] {a et b} 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

[Kaufmann-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)

[1]

[2]

[3]

[4]