Laplaceova matrika

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

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

Definicija[uredi | uredi kodo]

Za dani enostavni graf z vozlišči, so elementi Laplaceove matrike dani kot [1]

kjer

  • pomeni stopnjo v vozlišču

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

Normalizirana oblika pa 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]