Macierz incydencji

Macierzą incydencji grafu zorientowanego $G=(V,A)$ o zbiorze wierzchołków $V=\{ v_1,...,v_n\}$ i zbiorze łuków $A=\{ e_1,..., e_m\}$, nazywamy macierz $N=(b_{ij})_{ \begin{array}{c} i=1,...,n\\ j=1,...,m \end{array}}$ taką, że

$$b_{ij}= \left\{ \begin{array}{rl} 1 & \mbox{jeśli } v_i \... ...mbox{ i } e_j \mbox{ nie są incydentne} \end{array} \right.$$

Dla grafu z rysunku 8.1 macierzą incydencji jest

$$N= \left[ \begin{array}{rrrr} 1 & -1 & 1 & 0 \\ 0 & 0 & -1 & -1 \\ -1 & 1 & 0 & 1 \end{array} \right]$$