Laplaceova matrika

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Laplaceova matrika (tudi Kirchoffova matrika) je matrika s katero se predstavi graf. Skupaj s Kirchoffovim zakonom se lahko uporabi za izračunavanje števila vpetih dreves za dani graf. Razen tega se lahko Laplaceovo matriko uporabi za določanje mnogih značilnosti grafov.

Definicija[uredi | uredi kodo]

Za dani enostavni graf z točkami], so elementi Laplaceove matrike dani kot:[1]

kjer

  • pomeni stopnjo v točki

To pomeni, da je Laplaceova matrika razlika med matriko stopenj in matriko sosednosti istega grafa.

Normalizirana oblika je:[1]

.

Zgled[uredi | uredi kodo]

označeni graf Laplaceova matrika
6n-graf.svg

Značilnosti[uredi | uredi kodo]

Za graf in njegovo Laplaceovo matriko , ki ima lastne vrednosti enake :

Glej tudi[uredi | uredi kodo]

Sklici[uredi | uredi kodo]

Zunanje povezave[uredi | uredi kodo]