Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Matrice d'incidence
Résumé
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).
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.