Macierz incydencji

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacja, szukaj

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