Matrice d'incidence d'un graphe

Dénombrements et probabilités -- Théorie des graphes

  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=(ai,j) comportant n lignes et m colonnes telle que
  • ai,j vaut +1, si l'arc numéroté j admet le sommet i comme origine;
  • ai,j vaut -1, si l'arc numéroté j admet le sommet i comme arrivée;
  • ai,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...

Version imprimable


Pour signaler une erreur, proposer une amélioration, contacter les auteurs, écrivez à
La BibM@th 2000-2013 - V&F Bayart