Matrice di grado

Template:F Nel campo della teoria dei grafi la matrice di grado è una matrice diagonale che contiene le informazioni sul grado di ogni vertice del grafo, ovvero il numero di archi che sono collegati ad esso. È usata insieme alla matrice delle adiacenze per costruire la matrice laplaciana di un grafo.

Definizione

Preso un grafo $G=(V,E)$ con $\Vert V\Vert =n$ la matrice di grado $D$ per $G$ è una matrice diagonale $n\times n$ definita come:

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

dove il grado $\mathrm{deg}(v_i)$ di un vertice è il numero di archi che termina in un dato vertice. In un grafo non orientato significa che ogni nuovo ciclo aumenta il grado di un vertice di due. In un grafo orientato, invece, il termine grado può riferirsi al numero di archi in entrata o al numero di archi in uscita di un tale vertice.

Esempio

Grafo semplice	Matrice di grado
	$\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)$

Proprietà

La matrice di grado di un grafo k-regolare è una matrice diagonale constate di valore $k$.

Collegamenti esterni

• Template:Collegamenti esterni