Incidenčna matrika

Incidenčna matrika je v matematiki matrika, ki kaže odnos med dvema razredoma objektov. Če se prvi razred označi 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

Incidenčna matrika je matrika $n\times m$, ki predstavlja graf z n ]]točka (teorija grafov)|točkami]] 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četna točka) in enkrat vrednost -1 (končna točka).

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{array}{cc}1,& \text{ kadar je }{v}_i\in e_j\\ 0,& \text{ sicer}\end{array}$

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{array}{cc}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{array}$.

Zgled

Slika:Incidenčna matrika-graf.svg

Točke so označene z rdečimi številkami, povezave so označene s črnimi številkami.

$\leftrightarrow \left[\begin{array}{cccccc}{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{array}\right]$.

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

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

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

Teorija grafov

Usmerjeni in neusmerjeni grafi

Drugi zgled neusmerjenega grafa

V teoriji grafov ima neusmerjeni graf dve vrsti incidenčnih matrik: usmerjene incidenčne matrike in neusmerjene incidenčne matrike. Incidenčna matrika (ali neusmerjena incidenčna matrika) $G$ je matrika z elementi $b_{ij}$ z razsežnostjo $p\times q$, kjer je $p$ število točk in $q$ število povezav. Pri tem je $b_{ij}=1$, če sta točka $v_i$ in povezava $x_j$ v povezavi. V vseh drugih primerih pa so elementi enaki 0.

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

$\left[\begin{array}{cccc}{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{array}\right]$

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 točke $v_1,v_2,v_3,v_4$. Incidenčno matriko se dobi 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 točk in $q$ \,</math> pomeni število povezav. V matriki imajo elementi $p=$ vrednost -1, če povezava $x_j$ zapušča točko, in vrednost +1, če vstopa v točko, v vseh drugih primerih pa vrednost 0. Nekateri uporabljajo pri vrednostih nasprotne predznake.

Usmerjena incidenčna matrika neusmerjenega grafa $G$ je incidenčna matrika, ki je takšna, kot bi se jo dobilo iz usmerjenega grafa katerekoli usmeritve. To pomeni, da je v stolpcu povezave $e$ vrednost +1, v vrstici, ki odgovarja točki $e$ ter -1 v vrstici, k pripada drugi točki povezave $e$. V vseh drugih primerih pa imajo elementi vrednost 0.

Kirchhoffova matrika (Laplaceova matrika) se dobi iz usmerjene 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

• Incidenčna matrika Predloga:Webarchive na MaFiRa Wiki Predloga:Ikona sl
• Predloga:MathWorld
• Incidenčna matrikaPredloga:Slepa povezava na WordiQ Predloga:Ikona en