Macierz incydencji

Ten artykuł należy dopracować:

od 2024-12 → zweryfikować treść i dodać przypisy,
od 2024-12 → poszerzyć o istotne informacje.
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.

Macierz incydencji – dla 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}}$ macierz $M=(m_{ij}),$ gdzie $i=1,\dots ,n$ oraz $j=1,\dots ,m$ taka, ż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}}

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].