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{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

Točke so označene 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), 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.

${\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 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 Arhivirano 2012-05-24 na Wayback Machine. na MaFiRa Wiki (slovensko)
• Weisstein, Eric Wolfgang. »Incidence Matrix«. MathWorld.
• Incidenčna matrika na WordiQ (angleško)