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

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

Graph Chatbot

Chattez avec Graph Search

Posez n’importe quelle question sur les cours, conférences, exercices, recherches, actualités, etc. de l’EPFL ou essayez les exemples de questions ci-dessous.

AVERTISSEMENT : Le chatbot Graph n'est pas programmé pour fournir des réponses explicites ou catégoriques à vos questions. Il transforme plutôt vos questions en demandes API qui sont distribuées aux différents services informatiques officiellement administrés par l'EPFL. Son but est uniquement de collecter et de recommander des références pertinentes à des contenus que vous pouvez explorer pour vous aider à répondre à vos questions.