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  

Za dani enostavni graf  z  točkami], so elementi Laplaceove matrike  dani kot:

  
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

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  

Matrike
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 : 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 Značilnosti Za graf in njegovo Laplaceovo matriko , ki ima lastne vrednosti enake \ : matrika je pozitivno semidefinitna število pojavov vrednostimed lastnimi vrednostmi v Laplaceovi matriki je enako številu povezanih komponent v grafu je vedno enaka 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 Matrike