Macierz incydencji

Macierz incydencji grafu zorientowanego (skierowanego) G = ( V , K ) {\displaystyle G=(V,K)} o zbiorze wierzchołków V = v 1 , … , v n {\displaystyle V={v_{1},\dots ,v_{n}}} i krawędzi K = k 1 , . . , k m {\displaystyle K={k_{1},..,k_{m}}} nazywamy macierz M = ( m i j ) , {\displaystyle M=(m_{ij}),} gdzie i = 1 , … , n {\displaystyle i=1,\dots ,n} oraz j = 1 , … , m {\displaystyle j=1,\dots ,m} taką, że:

m i j = { 1 j e s ´ l i   v i   jest poczatkiem krawedzi   k j − 1 j e s ´ l i   v i   j e s t   k o n ´ c e m   k r a w e d z i   k j 0 j e s ´ l i   v i   i   k j   nie sa incydentne {\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}}}
graf skierowany

Przykład:

Jeśli:

  • k 1 = ( 1 , 2 ) {\displaystyle k_{1}=(1,2)}
  • k 2 = ( 1 , 3 ) {\displaystyle k_{2}=(1,3)}
  • k 3 = ( 3 , 2 ) {\displaystyle k_{3}=(3,2)}
  • k 4 = ( 3 , 4 ) {\displaystyle k_{4}=(3,4)}
  • k 5 = ( 4 , 3 ) {\displaystyle k_{5}=(4,3)}

oznaczają wszystkie krawędzie grafu skierowanego z przykładowego rysunku, to macierz incydencji o kolumnach k i {\displaystyle k_{i}} i wierszach v i {\displaystyle v_{i}} może wyglądać tak:

M = [ 1 1 0 0 0 − 1 0 − 1 0 0 0 − 1 1 1 − 1 0 0 0 − 1 1 ] {\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]}

Linki zewnętrzne

  • publikacja w otwartym dostępie – możesz ją przeczytać Incidence matrix (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-04-05].