Gradmatris

Inom grafteorin är en gradmatris eller valensmatris en diagonalmatris som anger graden has varje nod (det vill säga hur många kanter som ansluter till respektive nod). Den används tillsammans med grannmatrisen för att beräkna grafens laplacematris.

Definition

Gradmatrisen $D$ för en graf $G=(V,E)$ med $|V|=n$ är en $n\times n$ diagonalmatris definierad som:

$d_{i,j}:=\{\begin{array}{cc}\mathrm{deg}(v_i)& \text{om}i=j\\ 0& \text{om}i\ne j\end{array}$

där graden $\mathrm{deg}(v_i)$ för en nod anger hur många kanter som ansluter till densamma (för en oriktad graf innebär detta att varje loop/ögla, en kant som ansluter noden till sig själv, ökar graden med två). Hos en riktad graf kan grad antingen avse ingrad (antalet kanter som går till noden) eller utgrad (antalet kanter som går från noden).

Exempel

Graf med märkta hörn	Gradmatris
	$\left(\begin{array}{cccccc}4& 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)$

Egenskaper

Gradmatrisen till en k-reguljär graf har en diagonal bestående av konstanten k.