stringtranslate.com

Grado (teoría de grafos)

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.

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, .

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, dado un gráfico ,

.

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]

Valores especiales

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

Propiedades globales

Véase también

Notas

  1. ^ Diéstel, 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 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