Matrice di grado

Questa voce o sezione sull'argomento teoria dei grafi non cita le fonti necessarie o quelle presenti sono insufficienti.

---

Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti.

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.

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

${\displaystyle d_{i,j}:=\left\{\begin{matrix}\deg(v_{i})&{\mbox{se}\ i=j\\0&{\mbox{altrimenti}\end{matrix}\right.}$

dove il grado ${\displaystyle \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.

Grafo semplice	Matrice di grado
	${\displaystyle {\begin{pmatrix}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{pmatrix}$

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

• (EN) Eric W. Weisstein, Degree Matrix, su MathWorld, Wolfram Research.

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica