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. 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 » ; 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. Si le graphe est non orienté, la matrice est appelée « matrice d'incidence sommets-arêtes » ;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. 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. 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).