Топ-100
Indietro

ⓘ Matrice di grado. Nel campo della teoria dei grafi la matrice di grado è una matrice diagonale che contiene le informazioni sul grado di ogni vertice del grafo, ..




Matrice di grado
                                     

ⓘ Matrice di grado

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.

                                     

1. Definizione

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

d i, j:= { deg ⁡ v i se i = j 0 altrimenti {\displaystyle d_{i,j}:=\left\\right.}

dove il grado deg ⁡ v i {\displaystyle \degv_{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ò riferrisi al numero di archi in entrata o al numero di archi in uscita di un tale vertice.