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éfinitionModifier

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   et en colonne   vaut :

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

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

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

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

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

ExemplesModifier

Cas du graphe non orientéModifier

 
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 :

 

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

Cas du graphe orientéModifier

 
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 :

 

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ésModifier

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

Relation aux autres matrices remarquablesModifier

Relation à la matrice laplacienneModifier

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

La matrice laplacienne   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   est la matrice d'incidence d'un graphe orienté  , on peut en déduire la matrice laplacienne   en multipliant   par sa transposée    :

 

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

 

Relation à la matrice d'adjacence et à la matrice des degrésModifier

 
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   est la matrice d'incidence d'un graphe non orienté  , si   est sa matrice d'adjacence et si   est sa matrice des degrés, alors :

 

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

 

En isolant la diagonale des autres valeurs, on trouve :

 

Relation à la matrice d'adjacence du line graphModifier

 
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   est la matrice d'incidence d'un graphe non orienté  , on peut en déduire la matrice d'adjacence   de son line graph en multipliant la transposée   par  , puis en soustrayant deux fois  , la matrice unité d'ordre p :

 

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

 

En calculant :  

Notes et référencesModifier

  1. « matrice d'incidence », sur publimath.irem.univ-mrs.fr (consulté le 3 mai 2020)
  2. « Matrice d'incidence d'un graphe », sur www.bibmath.net (consulté le 3 mai 2020)

Voir aussiModifier

Sur les autres projets Wikimedia :