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  :

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)