Incidenčna matrika

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Incidenčna matrika je v matematiki matrika, ki kaže odnos med dvema razredoma objektov. Če prvi razred označimo z  x \, in drugi z  y \,, potem ima matrika eno vrstico za vsak element iz  x \, in en stolpec za vsak element iz  y \,. V matriki so elementi v vrstici  x \, in stolpcu  y \, enaki 1, če sta  x \, in  y \, v zvezi in enaki 0, če nista.

Definicija[uredi | uredi kodo]

Incidenčna matrika je matrika  n \times m \,, ki predstavlja graf z n vozlišči in m povezavami. stolpci imajo samo po dva od nič različna elementa. v matrikah, ki pripadajo neusmerjenim grafom, sta po dva elementa enaka 1, v usmerjenih grafih brez zank pa imajo po enkrat vrednost 1 (začetno vozlišče) in enkrat vrednost -1 (končno vozlišče).

Za neusmerjeni graf  g = (v, e) \,, ki ima  v = \{v_1, \dots, v_n \} \, in  e = \{e_1, \dots, e_n \} \, ima incidenčna matrika naslednje elemente  b = (b_{ij}) \,. to pomeni, da je


b_{ij} := \begin{cases}
1, & \text{ kadar je } v_i \in e_j \\
0, & \text{ sicer}
\end{cases}

Za usmerjeni graf brez zank  g = (v, e) \,, ki ima  v = \{v_1, \dots, v_n \} \, in  e = \{e_1, \dots, e_n \} \, ima incidenčna matrika naslednje elemente  b = (b_{ij}) \,


b_{ij} := \begin{cases}
1,  & \text{ kadar je } e_j=(v_i,x) \\
0,  & \text{ kadar je } v_i \notin e_j \\
-1, & \text{ kadar je } e_j=(x,v_i)
\end{cases}
.

Zgled[uredi | uredi kodo]

Vozlišča so označena z rdečimi številkami, povezave so označene s črnimi številkami.

\leftrightarrow\begin{bmatrix}
e_1 & e_2 & e_3 & e_4 & e_5 & e_6\\
1&0&0&0&1&0& v_1\\        
1&1&0&0&0&1& v_2\\
0&1&1&0&0&0& v_3\\
0&0&1&1&0&0& v_4\\
0&0&0&1&1&1& v_5\\
\end{bmatrix}.

V matriki na desni strani so za lažje razumevanje povezave označene z  e_1, \dots, e_n \, (prva vrstica), vozlišča pa z  v_1, \dots, v_n \, (zadnji stolpec).

Incidenčno matriko za graf na levi strani dobimo na naslednji način:

  • V vozlišče 1 (glej oznako na sliki) prihajata dve povezavi, ki sta označeni z 1 in 5. tako dobimo prvo vrstico matrike, ki ima elemente 1, 0, 0, 0, 1, 0.
  • Druga vrstica pripada vozlišču 2, ki mu pripadajo povezave označene z 1, 2 in 6. to nam da elemente v drugi vrstici 1, 1, 0, 0, 0 in 1.
  • Tretja vrstica pripada vozlišču 3, ki mu pripadata dve povezavi, ki sta označeni z 2 in 3. to nam da tretjo vrstico z elementi 0, 1, 1, 0, 0 in 0.
  • Četrta vrstica pripada vozlišču 4, ki mu pripadata samo dve povezavi, ki sta označeni s 3 in 4. to nam da četrto vrstico z elementi 0, 0, 1, 1, 0 in 0.
  • Zadnja vrstica pripada vozlišču 5, ki mu pripadajo tri povezave označene s 4, 5 in 6. To nam da zadnjo vrstico incidenčne matrika z elementi 0, 0, 0, 1, 1 in 1.

Teorija grafov[uredi | uredi kodo]

Usmerjeni in neusmerjeni grafi[uredi | uredi kodo]

Drugi zgled neusmerjenega grafa

V teoriji grafov ima neusmerjeni graf dve vrsti incidenčnih matrik: orientirane incidenčne matrike in neorientirane incidenčne matrike. Incidenčna matrika (ali neorientirana incidenčna matrika)  G \, je matrika z elementi  b_{ij} \, z razsežnostjo  p \times q \,, kjer je  p \, število vozlišč in  q \, število povezav. pri tem je  b_{ij} = 1 \,, če sta vozlišče  v_i \, in povezava  x_j \, v povezavi. V vseh ostalih primerih pa so elementi enaki 0.

Incidenčna matrika grafa na desni je matrika, ki ima 4 vrstice in 4 stolpce.


\begin{bmatrix}
e_1 & e_2 & e_3 & e_4 \\
  1 & 1 & 1 & 0 & v_1\\
  1 & 0 & 0 & 0 & v_2\\
  0 & 1 & 0 & 1 & v_3 \\
  0 & 0 & 1 & 1 & v_4 \\
\end{bmatrix}

Tudi v tem zgledu je za lažje razumevanje dodana vrstica, ki predstavlja štiri povezave  e_1, e_2, e_3, e_4 \, in stolpec, ki predstavlja štiri vozlišča  v_1, v_2, v_3, v_4 \,. Incidenčno matriko dobimo podobno kot v zgornjem zgledu.

Incidenčna matrika usmerjenega grafa  D \, je matrika z razsežnostjo  p \times q \, in elementi  b_{ij} \,, kjer  p \, pomeni število vozlišč in  q \, \,</math> pomeni število povezav. V matriki imajo elementi  p = \, vrednost -1, če povezava  x_j \, zapušča vozlišče, in vrednost +1, če vstopa v vozlišče, v vseh ostalih primerih pa vrednost 0. Nekateri uporabljajo pri vrednostih nasprotne predznake.

Orientirana incidenčna matrika neusmerjenega grafa  G \, je incidenčna matrika, ki je takšna, kot bi jo dobili iz usmerjenega grafa katerekoli orientacije. To pomeni, da je v stolpcu povezave  e \, vrednost +1, v vrstici, ki odgovarja vozlišču  e \, ter -1 v vrstici, k pripada drugemu vozlišču povezave  e \,. V vseh ostalih primerih pa imajo elementi vrednost 0.

Kirchhoffova matrika (Laplaceova matrika) se dobi iz orientirane incidenčne matrike  M(G) \, s pomočjo obrazca

 M(G) M(G)^{T}\,

kjer je

  •  M(G) \, incidenčna matrika
  • oznaka  T \, pomeni transponirano incidenčno matriko.

Zunanje povezave[uredi | uredi kodo]