En teoría de grafos , el grado (o valencia ) de un vértice de un gráfico es el número de aristas que inciden en el vértice; en un multigrafo , un bucle contribuye con 2 al grado de un vértice, para los dos extremos del borde. [1] El grado de un vértice se denota o . El grado máximo de un gráfico , denotado por , y el grado mínimo de un gráfico, denotado por , son el máximo y el mínimo de los grados de sus vértices. En el multigrafo que se muestra a la derecha, el grado máximo es 5 y el grado mínimo es 0.
En una gráfica regular , cada vértice tiene el mismo grado, por lo que podemos hablar del grado de la gráfica. Un gráfico completo (denotado como , donde es el número de vértices en el gráfico) es un tipo especial de gráfico regular donde todos los vértices tienen el máximo grado posible .
En un gráfico con signo , el número de aristas positivas conectadas al vértice se denomina grados positivos y el número de aristas negativas conectadas se denomina grados negativos . [2] [3]
Lema del apretón de manos
La fórmula de la suma de grados establece que, dada una gráfica ,
.
La fórmula implica que en cualquier gráfico no dirigido, el número de vértices con grado impar es par. Esta afirmación (así como la fórmula de suma de grados) se conoce como lema del apretón de manos . Este último nombre proviene de un problema matemático popular, que consiste en demostrar que en cualquier grupo de personas, el número de personas que han dado la mano a un número impar de otras personas del grupo es par. [4]
secuencia de grados
La secuencia de grados de un gráfico no dirigido es la secuencia no creciente de los grados de sus vértices; [5] para el gráfico anterior es (5, 3, 3, 2, 2, 1, 0). La secuencia de grados es una gráfica invariante , por lo que las gráficas isomorfas tienen la misma secuencia de grados. Sin embargo, la secuencia de grados no identifica, en general, de forma única un gráfico; en algunos casos, los gráficos no isomórficos tienen la misma secuencia de grados.
El problema de secuencia de grados es el problema de encontrar algunas o todas las gráficas siendo la secuencia de grados una secuencia dada no creciente de números enteros positivos. (Los ceros finales pueden ignorarse ya que se realizan trivialmente agregando un número apropiado de vértices aislados al gráfico). Una secuencia que es la secuencia de grados de algún gráfico, es decir, para la cual el problema de secuencia de grados tiene una solución, se llama gráfico . o secuencia gráfica . Como consecuencia de la fórmula de la suma de grados, cualquier secuencia con una suma impar, como (3, 3, 1), no puede realizarse como la secuencia de grados de un gráfico. Lo inverso también es cierto: si una secuencia tiene una suma par, es la secuencia de grados de un multigrafo. La construcción de un gráfico de este tipo es sencilla: conecte los vértices con grados impares en pares (formando una coincidencia ) y complete los recuentos de grados pares restantes mediante bucles automáticos. La cuestión de si una secuencia de grados determinada puede realizarse mediante un gráfico simple es más desafiante. Este problema también se denomina problema de realización de gráficos y puede resolverse mediante el teorema de Erdős-Gallai o el algoritmo de Havel-Hakimi . El problema de encontrar o estimar el número de gráficos con una secuencia de grados determinada es un problema del campo de la enumeración de gráficos .
De manera más general, la secuencia de grados de un hipergrafo es la secuencia no creciente de los grados de sus vértices. Una secuencia es gráfica si es la secuencia de grados de algún hipergrafo uniforme. En particular, una secuencia gráfica es gráfica. Decidir si una secuencia dada es gráfica es factible en tiempo polinomial mediante el teorema de Erdős-Gallai , pero es NP-completa para todos . [6]
Un vértice con grado 1 se llama vértice de hoja o vértice final o vértice colgante, y el borde incidente con ese vértice se llama borde colgante. En el gráfico de la derecha, {3,5} es una arista colgante. Esta terminología es común en el estudio de árboles en teoría de grafos y especialmente árboles como estructuras de datos .
Un vértice con grado n − 1 en un gráfico de n vértices se llama vértice dominante .
Propiedades globales
Si cada vértice del gráfico tiene el mismo grado k , el gráfico se llama k -gráfico regular y se dice que el gráfico en sí tiene grado k . De manera similar, un gráfico bipartito en el que cada dos vértices del mismo lado de la bipartición tienen el mismo grado se llama gráfico biregular .
Un grafo conexo no dirigido tiene un camino euleriano si y sólo si tiene 0 o 2 vértices de grado impar. Si tiene 0 vértices de grado impar, el camino euleriano es un circuito euleriano.
Un gráfico dirigido es un pseudobosque dirigido si y sólo si cada vértice tiene un grado superior a 1 como máximo. Un gráfico funcional es un caso especial de pseudobosque en el que cada vértice tiene un grado superior exactamente 1.
^ Diestel, Reinhard (2005). Teoría de grafos (3ª ed.). Berlín, Nueva York: Springer-Verlag. págs.5, 28. ISBN 978-3-540-26183-4.
^ Ciotti, Valerio; Bianconi, Giestra; Capocci, Andrea; Colaiori, Francesca; Panzarasa, Pietro (2015). "Correlaciones de grados en redes sociales firmadas". Physica A: Mecánica estadística y sus aplicaciones . 422 : 25–39. arXiv : 1412.1024 . Código Bib : 2015PhyA..422...25C. doi :10.1016/j.physa.2014.11.062. S2CID 4995458. Archivado desde el original el 2 de octubre de 2021 . Consultado el 10 de febrero de 2021 .
^ Saberi, Majerid; Khosrowabadi, Reza; Khatibi, Ali; Misic, Bratislav; Jafari, Gholamreza (enero de 2021). "Impacto topológico de los enlaces negativos en la estabilidad de la red cerebral en estado de reposo". Informes científicos . 11 (1): 2176. Código bibliográfico : 2021NatSR..11.2176S. doi :10.1038/s41598-021-81767-7. PMC 7838299 . PMID 33500525.
^ Grossman, Peter (2009). Matemáticas discretas para la informática. Bloomsbury . pag. 185.ISBN _978-0-230-21611-2.
^ Diéstel (2005), pág. 216.
^ Deza, Antoine; Levin, Asaf; Meesum, Syed M.; Onn, Shmuel (enero de 2018). "Optimización sobre secuencias de grados". Revista SIAM de Matemática Discreta . 32 (3): 2067–2079. arXiv : 1706.03951 . doi :10.1137/17M1134482. ISSN 0895-4801. S2CID 52039639.
Referencias
Erdős, P .; Gallai, T. (1960). "Gráfok előírt fokszámú pontokkal" (PDF) . Matematikai Lapok (en húngaro). 11 : 264–274..
Havel, Václav (1955). "Un comentario sobre la existencia de gráficos finitos". Časopis Pro Pěstování Matematiky (en checo). 80 (4): 477–480. doi : 10.21136/CPM.1955.108220 .
Hakimi, SL (1962). "Sobre la realizabilidad de un conjunto de números enteros como grados de los vértices de un gráfico lineal. I". Revista de la Sociedad de Matemáticas Industriales y Aplicadas . 10 (3): 496–506. doi :10.1137/0110037. SEÑOR 0148049..
Sierksma, Gerard; Hoogeveen, Han (1991). "Siete criterios para que secuencias de números enteros sean gráficas". Revista de teoría de grafos . 15 (2): 223–231. doi :10.1002/jgt.3190150209. SEÑOR 1106533..