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 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 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 , 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]

Vozlišča so označena 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), vozlišča pa z (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) je matrika z elementi z razsežnostjo , kjer je število vozlišč in število povezav. pri tem je , če sta vozlišče in povezava 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.

Tudi v tem zgledu je za lažje razumevanje dodana vrstica, ki predstavlja štiri povezave in stolpec, ki predstavlja štiri vozlišča . Incidenčno matriko dobimo podobno kot v zgornjem zgledu.

Incidenčna matrika usmerjenega grafa je matrika z razsežnostjo in elementi , kjer pomeni število vozlišč in \,</math> pomeni število povezav. V matriki imajo elementi vrednost -1, če povezava 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 je incidenčna matrika, ki je takšna, kot bi jo dobili iz usmerjenega grafa katerekoli orientacije. To pomeni, da je v stolpcu povezave vrednost +1, v vrstici, ki odgovarja vozlišču ter -1 v vrstici, k pripada drugemu vozlišču povezave . V vseh ostalih primerih pa imajo elementi vrednost 0.

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

kjer je

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

Zunanje povezave[uredi | uredi kodo]