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
Za dani enostavni graf z točkami], so elementi Laplaceove matrike dani kot:Laplaceova matrika (MathWorld)
kjer pomeni stopnjo v točki
To pomeni, da je Laplaceova matrika razlika med matriko stopenj in matriko sosednosti istega grafa.
Normalizirana oblika je:
.
Zgled
označeni graf Laplaceova matrika175px
Značilnosti
Za graf in njegovo Laplaceovo matriko , ki ima lastne vrednosti enake : matrika je pozitivno semidefinitna število pojavov vrednosti 0 med lastnimi vrednostmi v Laplaceovi matriki je enako številu povezanih komponent v grafu je vedno enaka 0 se imenuje algebrska povezljivost najmanjša neničelna lastna vrednost se imenuje spektralna vrzel ali Fiedlerjeva vrednost
Glej tudi
seznam vrst matrik
Sklici
Zunanje povezave
Laplaceova matrika Laplaceova matrika na PlanetMath Laplaceova matrika
Kategorija:Matrike