Macierz incydencji

Macierz incydencji grafu zorientowanego (skierowanego) G = (V, K) o zbiorze wierzchołków $V = {v_1,...,v_n}$ i krawędzi $K = {k_1,..,k_m}$ nazywamy macierz $M = (m_{ij})$, gdzie i=1,...,n oraz j=1,...,m taką, że:

$m_{ij} = \begin{cases} 1 & \mathrm{je\acute{s}li}\ v_i\ \mbox{jest poczatkiem krawedzi}\ k_j \\ -1 & \mathrm{je\acute{s}li}\ v_i\ \mathrm{jest}\ \mathrm{ko\acute{n}cem\ krawedzi}\ k_j \\ 0 & \mathrm{je\acute{s}li}\ v_i\ \mathrm{i}\ k_j\ \mbox{nie sa incydentne} \end{cases}$

graf skierowany

Przykład:

Jeśli:

• $k_1\ =\ (1,2)$
• $k_2\ =\ (1,3)$
• $k_3\ =\ (3,2)$
• $k_4\ =\ (3,4)$
• $k_5\ =\ (4,3)$

oznaczają wszystkie krawędzie grafu skierowanego z przykładowego rysunku, to macierz incydencji o kolumnach $e_i$ i wierszach $v_i$ może wyglądać tak:

$M=\left[ \begin{matrix} 1 & 1 & 0 & 0 & 0 \\ -1 & 0 & -1 & 0 & 0 \\ 0 & -1 & 1 & 1 & -1 \\ 0 & 0 & 0 & -1 & 1 \end{matrix}\right]$