Macierz incydencji

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{array}{cc}1& \mathrm{j}\mathrm{e}\acute{\mathrm{s}}\mathrm{l}\mathrm{i}{v}_i\text{jest poczatkiem krawedzi}{k}_j\\ -1& \mathrm{j}\mathrm{e}\acute{\mathrm{s}}\mathrm{l}\mathrm{i}{v}_i\mathrm{j}\mathrm{e}\mathrm{s}\mathrm{t}\mathrm{k}\mathrm{o}\acute{\mathrm{n}}\mathrm{c}\mathrm{e}\mathrm{m}\mathrm{k}\mathrm{r}\mathrm{a}\mathrm{w}\mathrm{e}\mathrm{d}\mathrm{z}\mathrm{i}{k}_j\\ 0& \mathrm{j}\mathrm{e}\acute{\mathrm{s}}\mathrm{l}\mathrm{i}{v}_i\mathrm{i}{k}_j\text{nie sa incydentne}\end{array}$

Przykład

graf skierowany

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{array}{ccccc}1& 1& 0& 0& 0\\ -1& 0& -1& 0& 0\\ 0& -1& 1& 1& -1\\ 0& 0& 0& -1& 1\end{array}\right]$

Linki zewnętrzne

• Szablon:Otwarty dostęp Incidence matrix Szablon:Lang, Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-04-05].