Incidenčna matrika

matrika, ki prikazuje razmerje med dvema razredoma objektov

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

Definicija

uredi

Incidenčna matrika je matrika  , 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  , ki ima   in   ima incidenčna matrika naslednje elemente  . To pomeni, da je:

 

Za usmerjeni graf brez zank  , ki ima   in   ima incidenčna matrika naslednje elemente  :

 .

Zgled

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

 .

V matriki na desni strani so za lažje razumevanje povezave označene z   (prva vrstica), točke pa z   (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

uredi

Usmerjeni in neusmerjeni grafi

uredi
 
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)   je matrika z elementi   z razsežnostjo  , kjer je   število točk in   število povezav. Pri tem je  , če sta točka   in povezava   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.

 

Tudi v tem zgledu je za lažje razumevanje dodana vrstica, ki predstavlja štiri povezave   in stolpec, ki predstavlja štiri točke  . Incidenčno matriko se dobi podobno kot v zgornjem zgledu.

Incidenčna matrika usmerjenega grafa   je matrika z razsežnostjo   in elementi  , kjer   pomeni število točk in   \,</math> pomeni število povezav. V matriki imajo elementi   vrednost -1, če povezava   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   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   vrednost +1, v vrstici, ki odgovarja točki   ter -1 v vrstici, k pripada drugi točki povezave  . V vseh drugih primerih pa imajo elementi vrednost 0.

Kirchhoffova matrika (Laplaceova matrika) se dobi iz usmerjene incidenčne matrike   s pomočjo obrazca:

 

kjer je:

  •   incidenčna matrika
  • oznaka   pomeni transponirano incidenčno matriko.

Zunanje povezave

uredi
  • Incidenčna matrika Arhivirano 2012-05-24 na Wayback Machine. na MaFiRa Wiki (slovensko)
  • Weisstein, Eric Wolfgang. »Incidence Matrix«. MathWorld.
  • Incidenčna matrika[mrtva povezava] na WordiQ (angleško)