Laplacematris

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

För en enkel graf G med n noder, definieras laplacematrisen $L_{n\times n}$ som:

$L=D-A,$

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

Elementen i $L$ ges av

$L_{i,j}:=\{\begin{array}{cc}\mathrm{deg}(v_i)& \text{om}i=j\\ -1& \text{om}i\ne j\text{och om }{v}_i\text{ och }{v}_j\text{ är förbundna av en kant}\\ 0& \text{i övriga fall}\end{array}$

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

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

$L=k\cdot I-A$

med enhetsmatrisen $I$.

Exempel

Graf med märkta noder	Gradmatris	-	Grannmatris	=	Laplacematris
	$\left(\begin{array}{cccccc}2& 0& 0& 0& 0& 0\\ 0& 3& 0& 0& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 0& 0& 0& 3& 0& 0\\ 0& 0& 0& 0& 3& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right)$	-	$\left(\begin{array}{cccccc}0& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0\end{array}\right)$	=	$\left(\begin{array}{cccccc}2& -1& 0& 0& -1& 0\\ -1& 3& -1& 0& -1& 0\\ 0& -1& 2& -1& 0& 0\\ 0& 0& -1& 3& -1& -1\\ -1& -1& 0& -1& 3& 0\\ 0& 0& 0& -1& 0& 1\end{array}\right)$