Matrice di grado

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search

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[modifica | modifica wikitesto]

Preso un grafo con la matrice di grado per è una matrice diagonale definita come:

dove il grado 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.

Esempio[modifica | modifica wikitesto]

Grafo semplice Matrice di grado
6n-graph2.svg

Proprietà[modifica | modifica wikitesto]

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

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