Matrice d'incidence sommet-arc

La matrice d'incidence est de taille $n\,\times\,m$, les sommets sont associés aux lignes, les arcs aux colonnes. Notons ${\mathcal A}_i(G)$ la matrice d'incidence associée au graphe $G=(X,\,E)$. Pour pouvoir l'écrire, nous devons numéroter les arcs du graphe. On obtient alors :

$$a_{ik}\:=\: \left\{ \begin{array}{ll} 1 & \text{si le so... ... $k$} \\ 0 & \text{partout ailleurs} \end{array} \right.$$

Cette notation est très lourde car la matrice est très creuse. En effet sur une même colonne seuls deux éléments ne sont pas nuls : ceux qui correspondent au sommet origine (1) et au sommet destination (-1) de l'arc. Sur une même ligne, le nombre d'éléments égal à 1 nous donne le demi degré supérieur alors que le nombre d'éléments égal à -1 nous indique le demi degré inférieur du sommet. Dans le cas non orienté, on ne place que des 1 et la somme d'une ligne indique le degré du sommet. Cette matrice est inexpoitable du point de vue algorithmique mais elle est extrèmement importante du point de vue théorique car elle permet de faire le lien, par exemple, entre la théorie des flots et la programmation linéaire. Notons que cette matrice s'adapte assez mal au cas des graphes contenant des boucles.