Grado (teoría de grafos)

Number of edges touching a vertex in a graph

Un gráfico con un bucle que tiene vértices etiquetados por grado.

En teoría de grafos , el grado (o valencia ) de un vértice de un grafo 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 de la arista. ^[1] El grado de un vértice se denota por o . El grado máximo de un grafo se denota por , y es el máximo de los grados de 's vértices'. El grado mínimo de un grafo se denota por , y es el mínimo de los grados de 's vértices'. En el multigrafo que se muestra a la derecha, el grado máximo es 5 y el grado mínimo es 0. ${\displaystyle v}$ ${\displaystyle \deg(v)}$ ${\displaystyle \deg v}$ ${\displaystyle G}$ ${\displaystyle \Delta (G)}$ ${\displaystyle G}$ ${\displaystyle \delta (G)}$ ${\displaystyle G}$

En un grafo regular , cada vértice tiene el mismo grado, por lo que podemos hablar del grado del grafo. Un grafo completo (denotado como , donde es el número de vértices en el grafo) es un tipo especial de grafo regular donde todos los vértices tienen el máximo grado posible, . ${\displaystyle K_{n}}$ ${\displaystyle n}$ ${\displaystyle n-1}$

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]} ${\displaystyle v}$ ${\displaystyle (v)}$ ${\displaystyle (v)}$

Lema del apretón de manos

La fórmula de la suma de grados establece que, dado un gráfico , ${\displaystyle G=(V,E)}$

${\displaystyle \sum _{v\in V}\deg(v)=2|E|\,}$.

La fórmula implica que en cualquier grafo no dirigido, el número de vértices con grado impar es par. Esta afirmación (así como la fórmula de la suma de grados) se conoce como el lema del apretón de manos . El ú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 estrechado la mano a un número impar de otras personas del grupo es par. ^[4]

Secuencia de grados

Dos grafos no isomorfos con la misma secuencia de grados (3, 2, 2, 2, 2, 1, 1, 1).

La secuencia de grados de un grafo no dirigido es la secuencia no creciente de los grados de sus vértices; ^[5] para el grafo anterior es (5, 3, 3, 2, 2, 1, 0). La secuencia de grados es un invariante del grafo , por lo que los grafos isomorfos tienen la misma secuencia de grados. Sin embargo, la secuencia de grados, en general, no identifica de forma única a un grafo; en algunos casos, los grafos no isomorfos tienen la misma secuencia de grados.

El problema de la secuencia de grados es el problema de encontrar algunos o todos los grafos con la secuencia de grados siendo 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 grafo). Una secuencia que es la secuencia de grados de algún grafo, es decir, para la cual el problema de la 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 grafo. 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 grafo de este tipo es sencilla: conecta los vértices con grados impares en pares (formando un ) coincidente y completa los recuentos de grados pares restantes mediante bucles propios. La cuestión de si una secuencia de grados dada puede realizarse mediante un grafo simple es más desafiante. Este problema también se denomina problema de realización de grafos y se puede resolver mediante el teorema de Erdős-Gallai o el algoritmo de Havel-Hakimi . El problema de encontrar o estimar el número de grafos con una secuencia de grado dada es un problema del campo de la enumeración de grafos .

En términos más generales, 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 para mediante el teorema de Erdős–Gallai pero es NP-completa para todo . ^[6] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2}$ ${\displaystyle k}$ ${\displaystyle k=2}$ ${\displaystyle k\geq 3}$

Valores especiales

Un gráfico no dirigido con nodos de hoja 4, 5, 6, 7, 10, 11 y 12

• Un vértice con grado 0 se llama vértice aislado .
• Un vértice con grado 1 se denomina vértice de hoja, vértice final o vértice colgante, y la arista incidente con ese vértice se denomina arista 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 la teoría de grafos y, especialmente, de árboles como estructuras de datos .
• Un vértice con grado n  − 1 en un grafo con n vértices se denomina vértice dominante .

Propiedades globales

• Si cada vértice del grafo tiene el mismo grado  k , el grafo se denomina grafo k -regular y se dice que el grafo en sí tiene grado  k . De manera similar, un grafo bipartito en el que cada dos vértices del mismo lado de la bipartición tienen el mismo grado se denomina grafo birregular .
• Un grafo no dirigido y conexo tiene un camino euleriano si y solo 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 grafo dirigido es un pseudobosque dirigido si y solo si cada vértice tiene un grado de salida como máximo 1. Un grafo funcional es un caso especial de un pseudobosque en el que cada vértice tiene un grado de salida exactamente 1.
• Por el teorema de Brooks , cualquier grafo G que no sea una camarilla o un ciclo impar tiene número cromático como máximo Δ( G ), y por el teorema de Vizing cualquier grafo tiene índice cromático como máximo Δ( G ) + 1.
• Un gráfico k -degenerado es un gráfico en el que cada subgráfico tiene un vértice de grado como máximo k .

Véase también

• Grado de entrada , grado de salida para dígrafos
• Distribución de grados
• Secuencia de grados para grafos bipartitos

Notas

1. Diestel, Reinhard (2005). Graph Theory (3.ª ed.). Berlín, Nueva York: Springer-Verlag. pp. 5, 28. ISBN 978-3-540-26183-4.
2. Ciotti, Valerio; Bianconi, Giestra; Capocci, Andrea; Colaiori, Francesca; Panzarasa, Pietro (2015). "Correlaciones de grado en redes sociales signadas". Physica A: Mecánica estadística y sus aplicaciones . 422 : 25–39. arXiv : 1412.1024 . Código Bibliográfico :2015PhyA..422...25C. doi :10.1016/j.physa.2014.11.062. S2CID  4995458. Archivado desde el original el 2021-10-02 . Consultado el 2021-02-10 .
3. Saberi, Majerid; Khosrowabadi, Reza; Khatibi, Ali; Misic, Bratislav; Jafari, Gholamreza (enero de 2021). "Impacto topológico de los vínculos negativos en la estabilidad de la red cerebral en estado de reposo". Scientific Reports . 11 (1): 2176. Bibcode :2021NatSR..11.2176S. doi :10.1038/s41598-021-81767-7. PMC 7838299 . PMID  33500525. 
4. Grossman, Peter (2009). Matemáticas discretas para computación. Bloomsbury . p. 185. ISBN 978-0-230-21611-2.
5. Diestel (2005), pág. 216.
6. Deza, Antoine; Levin, Asaf; Meesum, Syed M.; Onn, Shmuel (enero de 2018). "Optimización sobre secuencias de grados". Revista SIAM de Matemáticas Discretas . 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 grafo lineal. I". Revista de la Sociedad de Matemáticas Industriales y Aplicadas . 10 (3): 496–506. doi :10.1137/0110037. MR  0148049..
• Sierksma, Gerard; Hoogeveen, Han (1991). "Siete criterios para que las secuencias de números enteros sean gráficas". Journal of Graph Theory . 15 (2): 223–231. doi :10.1002/jgt.3190150209. MR  1106533..