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 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 | uredi kodo]

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 | uredi kodo]

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 | uredi kodo]

Usmerjeni in neusmerjeni grafi[uredi | uredi kodo]

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 | uredi kodo]