Macierz incydencji

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

${\displaystyle 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}}}$

Przykład:

Jeśli:

• ${\displaystyle k_{1}=(1,2)}$
• ${\displaystyle k_{2}=(1,3)}$
• ${\displaystyle k_{3}=(3,2)}$
• ${\displaystyle k_{4}=(3,4)}$
• ${\displaystyle k_{5}=(4,3)}$

oznaczają wszystkie krawędzie grafu skierowanego z przykładowego rysunku, to macierz incydencji o kolumnach ${\displaystyle k_{i}}$ i wierszach ${\displaystyle v_{i}}$ może wyglądać tak:

${\displaystyle 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]}$