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.

DefinicijaUredi

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]

 .

ZgledUredi

označeni graf Laplaceova matrika
   

ZnačilnostiUredi

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

Glej tudiUredi

SkliciUredi

Zunanje povezaveUredi

  • Weisstein, Eric Wolfgang. "Laplacian Matrix". MathWorld (angleščina).
  • Laplaceova matrika (angleško)
  • Laplaceova matrika na PlanetMath (angleško)
  • Laplaceova matrika (angleško)