Macierz incydencji

Macierz incydencji grafu zorientowanego (skierowanego) $G=(V,K)$ o zbiorze wierzchołków $V={v_{1},\dots ,v_{n}}$ i krawędzi $K={k_{1},..,k_{m}}$ nazywamy macierz $M=(m_{ij}),$ gdzie $i=1,\dots ,n$ oraz $j=1,\dots ,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 $k_{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]$

Linki zewnętrzne

• Incidence matrix (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-04-05].