Odpre glavni meni

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