Licenciatura (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 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. ${\displaystyle v}$ ${\displaystyle \deg(v)}$ ${\displaystyle \deg v}$ ${\displaystyle G}$ ${\displaystyle \Delta (G)}$ ${\displaystyle \delta (G)}$

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 . ${\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, dada una gráfica , ${\displaystyle G=(V,E)}$

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

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

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

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] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle 2}$ ${\displaystyle k}$ ${\displaystyle k=2}$ ${\displaystyle k\geq 3}$

Valores especiales

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

• Un vértice de grado 0 se llama vértice aislado .
• 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.
• Según el teorema de Brooks , cualquier gráfico G que no sea una camarilla o un ciclo impar tiene un número cromático como máximo Δ ( G ), y según el teorema de Vizing, cualquier gráfico tiene un índice cromático como máximo Δ ( G ) + 1.
• Un gráfico k -degenerado es un gráfico en el que cada subgrafo tiene un vértice de grado como máximo k .

Ver también

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

Notas

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.
2. 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 .
3. 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. 
4. Grossman, Peter (2009). Matemáticas discretas para la informática. Bloomsbury . pag. 185.ISBN _ 978-0-230-21611-2.
5. Diéstel (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á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..