Matrice d'incidence d'un graphe
Soit $G$ un graphe orienté qui possède $n$ sommets numérotés de 1 à $n$, et $m$ arcs numérotés de 1 à $m$. On appelle matrice d'incidence du graphe la matrice $A=(a_{i,j})$ comportant $n$ lignes et $m$ colonnes telle que
- $a_{i,j}$ vaut +1, si l'arc numéroté $j$ admet le sommet $i$ comme origine;
- $a_{i,j}$ vaut -1, si l'arc numéroté $j$ admet le sommet $i$ comme arrivée;
- $a_{i,j}$ vaut 0 dans les autres cas.
Exemple : Voici un exemple de graphe, et la matrice d'incidence associée :
On peut aussi définir la matrice d'incidence d'un graphe non-orienté. Dans un tel graphe, il n'y a plus de notion d'origine et d'arrivée d'une arête. On met donc +1 là où auparavant on mettait +1 ou -1, et on met 0 ailleurs.
Consulter aussi
Recherche alphabétique
Recherche thématique