Laplacematris

Från Wikipedia
Hoppa till: navigering, sök

Inom grafteorin är en laplacematris en matrisrepresentation av en graf och kan användas för att finna många egenskaper hos grafen. Tillsammans med Kirchhoffs sats kan den användas för att beräkna antalet uppspännande träd för en given graf. Laplacematrisen är den diskreta laplaceoperatorn för en ändligtdimensionell graf.

Den är uppkallad efter Pierre Simon de Laplace. Den kallas även kirchhoffmatris efter Gustav Kirchhoff.

Definition[redigera | redigera wikitext]

För en enkel graf G med n noder, definieras laplacematrisen som:[1]

där D betecknar grafens gradmatris och A dess grannmatris. För riktade grafer används ingrad eller utgrad beroende på applikationen.

Elementen i ges av

där deg(vi) betecknar graden hos nod vi.

Speciellt är laplacematrisen för en k-reguljär graf

med enhetsmatrisen .

Exempel[redigera | redigera wikitext]

Graf med märkta noder Gradmatris - Grannmatris = Laplacematris
6n-graf.svg - =

Referenser[redigera | redigera wikitext]

  1. ^ Weisstein, Eric W., "Laplacian Matrix", MathWorld. (engelska)