Matriz de grados

Tipos de matrices en la teoría de grafos algebraicos

En el campo matemático de la teoría de grafos algebraicos , la matriz de grado de un grafo no dirigido es una matriz diagonal que contiene información sobre el grado de cada vértice , es decir, el número de aristas unidas a cada vértice. ^[1] Se utiliza junto con la matriz de adyacencia para construir la matriz laplaciana de un grafo: la matriz laplaciana es la diferencia de la matriz de grado y la matriz de adyacencia. ^[2]

Definición

Dado un gráfico con , la matriz de grados para es una matriz diagonal definida como ^[1] ${\displaystyle G=(V,E)}$ ${\displaystyle |V|=n}$ ${\displaystyle D}$ ${\displaystyle G}$ ${\displaystyle n\times n}$

${\displaystyle D_{i,j}:=\left\{{\begin{matrix}\deg(v_{i})&{\mbox{if}}\ i=j\\0&{\mbox{otherwise}}\end{matrix}}\right.}$

donde el grado de un vértice cuenta la cantidad de veces que una arista termina en ese vértice. En un grafo no dirigido , esto significa que cada bucle aumenta el grado de un vértice en dos. En un grafo dirigido , el término grado puede referirse tanto al grado de entrada (la cantidad de aristas entrantes en cada vértice) como al grado de salida (la cantidad de aristas salientes en cada vértice). ${\displaystyle \deg(v_{i})}$

Ejemplo

El siguiente gráfico no dirigido tiene una matriz de grado 6x6 con valores:

Nótese que en el caso de gráficos no dirigidos, una arista que comienza y termina en el mismo nodo aumenta el valor del grado correspondiente en 2 (es decir, se cuenta dos veces).

Propiedades

La matriz de grados de un gráfico k-regular tiene una diagonal constante de . ${\displaystyle k}$

Según la fórmula de suma de grados , la traza de la matriz de grados es el doble del número de aristas del grafo considerado.

Referencias

1. Chung, Fan ; Lu, Linyuan; Vu, Van (2003), "Espectros de grafos aleatorios con grados esperados dados", Actas de la Academia Nacional de Ciencias de los Estados Unidos de América , 100 (11): 6313–6318, Bibcode :2003PNAS..100.6313C, doi : 10.1073/pnas.0937490100 , MR  1982145, PMC  164443 , PMID  12743375.
2. Mohar, Bojan (2004), "Graph Laplacians", en Beineke, Lowell W.; Wilson, Robin J. (eds.), Temas de teoría de grafos algebraicos, Enciclopedia de matemáticas y sus aplicaciones, vol. 102, Cambridge University Press, Cambridge, págs. 113-136, ISBN 0-521-80197-4, Sr.  2125091.