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

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]}$

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