Représentation et modélisation par la matrice d'incidence
Définition :
La matrice d'incidence aux arcs associée au graphe G=(X,E) non réflexif (sans boucle) est une matrice M de n lignes et m colonnes telle que :
M(i,k)=-1 si et seulement si i est origine de l'arc k
M(j,k)= 1 si et seulement si j est extrémité de l'arc k
M(p,k)=0 si et seulement si p n'est pas adjacent à l'arc j
Avantages et inconvénients
Cette matrice est essentiellement utilisée pour la modélisation de problèmes de programmation linéaire que l'on est amené à écrire pour résoudre des problèmes de graphes. C'est en particulier le cas des problèmes de flots dans les graphes qui sont présentés dans le module avancé sur les algorithmes de graphe.
Sous sa forme étendue, cette matrice est la plus gourmande en espace mémoire.
On n'a pas non plus directement l'information de l'existence ou non d'un arc entre i et j.
