Laplaceova matrika
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
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
označeni graf | Laplaceova matrika |
---|---|
Značilnosti uredi
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 uredi
Sklici uredi
Zunanje povezave uredi
- Weisstein, Eric Wolfgang. »Laplacian Matrix«. MathWorld.
- Laplaceova matrika (angleško)
- Laplaceova matrika Arhivirano 2009-12-12 na Wayback Machine. na PlanetMath (angleško)
- Laplaceova matrika Arhivirano 2012-08-13 na Wayback Machine. (angleško)