En el campo matemático de la teoría de grafos , la matriz de grados es una matriz diagonal que contiene información sobre el grado de cada vértice , es decir, el número de aristas adjuntas a cada vértice. [1] Se utiliza junto con la matriz de adyacencia para construir la matriz laplaciana de un gráfico. [2]
Definición
Dado un gráfico con , la matriz de grados por es un matriz diagonal definida como [1]
donde el grado de un vértice cuenta el número de veces que una arista termina en ese vértice. En un gráfico no dirigido , esto significa que cada bucle aumenta el grado de un vértice en dos. En un gráfico dirigido , el término grado puede referirse a indegree (el número de bordes entrantes en cada vértice) o outdegree (el número de bordes salientes en cada vértice).
Ejemplo
El siguiente gráfico no dirigido tiene una matriz de 6x6 grados con valores:
Gráfico etiquetado con vértice | Matriz de grados |
---|---|
Tenga en cuenta que en el caso de gráficos no dirigidos, un borde que comienza y termina en el mismo nodo aumenta el valor de grado correspondiente en 2 (es decir, se cuenta dos veces).
Propiedades
La matriz de grados de una gráfica k-regular tiene una diagonal constante de.
Referencias
- ^ a b Chung, Fan ; Lu, Linyuan; Vu, Van (2003), "Espectros de gráficos aleatorios con grados esperados dados", Actas de la Academia Nacional de Ciencias de los Estados Unidos de América , 100 (11): 6313–6318, doi : 10.1073 / pnas.0937490100 , MR 1982145 , PMC 164443 , PMID 12743375.
- ^ Mohar, Bojan (2004), "Graph Laplacians", en Beineke, Lowell W .; Wilson, Robin J. (eds.), Temas de la teoría de grafos algebraicos , Encyclopedia of Mathematics and its Applications, 102 , Cambridge University Press, Cambridge, págs. 113-136, ISBN 0-521-80197-4, Señor 2125091.