Degeneración (teoría de grafos)

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 9 de octubre de 2021; la verificación requiere 1 edición .

Un gráfico k -degenerado es un gráfico no dirigido en el que cada subgráfico tiene vértices con grado como máximo k . La degeneración del gráfico es el valor más pequeño de k para el cual el gráfico es k -degenerado. La degeneración del gráfico refleja cuán disperso es el gráficoy (hasta un factor constante) refleja otras medidas de escasez, como la arborescencia del gráfico .

La degeneración también se conoce como el número k -core [1] [2] [3] , ancho [4] y enlace [5] , y es esencialmente lo mismo que el número de coloración [6] o el número de Szekeres - Wilf . Los grafos k -degenerados también se denominan grafos k -inductivos [7] . La degeneración de un gráfico se puede calcular en tiempo lineal utilizando un algoritmo que elimina secuencialmente los vértices con un grado mínimo [8] . El componente conexo que queda después de eliminar todos los vértices con un grado menor que k se denomina k - kernel del gráfico, y la degeneración del gráfico es igual al valor más grande de k para el que hay un k -kernel .

Ejemplos

Cualquier bosque tiene un vértice aislado (sin bordes adyacentes) o un vértice de hoja (incidente exactamente en un borde), por lo que los bosques y los árboles son gráficos de 1 degeneración.

Cualquier gráfico plano finito tiene un vértice de grado cinco o menos, por lo que cualquier gráfico plano tiene degeneración 5 y la degeneración de cualquier gráfico plano no excede de cinco. De manera similar, la degeneración de cualquier gráfico exterior no excede de dos [9] , y la degeneración de los gráficos de Apolonio es igual a tres.

El modelo de Barabasi-Albert para generar redes aleatorias sin escala [10] tiene un número m como parámetro , tal que cada vértice agregado al gráfico está conectado por aristas a los m vértices agregados previamente. De ello se deduce que cualquier subgrafo de la red obtenida de esta manera tiene un grado de vértice de al menos m (este es el grado del último vértice agregado al gráfico), por lo que las redes de Barabasi-Albert son automáticamente m -degeneradas.

Cualquier gráfico k -regular tiene exactamente k degeneración . Más estrictamente, la degeneración de un grafo es igual al mayor grado de un vértice si y solo si al menos una de las componentes conexas del grafo es regular y tiene el grado del grafo mismo. Para todos los demás gráficos, la degeneración es estrictamente menor que el mayor grado de vértices del gráfico [11]

Definiciones

El número de color de un grafo G fue introducido por Erdős y Hajnal [6] como el mayor κ para el que existe un orden de los vértices del grafo G tal que cada vértice tiene menos de κ vecinos que preceden al vértice en el orden. Este número debe distinguirse del número cromático del gráfico G , el número mínimo de colores requerido para colorear un vértice de modo que no haya dos vértices adyacentes que tengan el mismo color. La ordenación que define el número de coloración da el orden en que los vértices de la gráfica G se colorean con un número de colores igual al número de coloración, pero, en general, el número cromático puede ser inferior a este número.

La degeneración de un grafo G fue definida por Lick y White [9] como el número k más pequeño para el cual cualquier subgrafo generado de G contiene un vértice con k o menos vecinos. La definición no cambia si se toman subgrafos arbitrarios en lugar de subgrafos generados, ya que un subgrafo no generado puede tener grados de vértice que no excedan los grados de vértice de un subgrafo generado con el mismo conjunto de vértices.

Los dos conceptos, número colorante y degeneración, son equivalentes: en cualquier gráfico finito, la degeneración es uno menos que el número colorante [12] [13] . Si un grafo tiene un ordenamiento con número de colorante κ, entonces en cada subgrafo H el vértice que pertenece a H y es el último en el ordenamiento tiene como máximo κ − 1 vecinos en H . En la otra dirección, si G es k -degenerado, entonces se puede obtener un ordenamiento con el número de color k  + 1 encontrando secuencialmente un vértice v con como máximo k vecinos, eliminando v del gráfico, ordenando los vértices restantes y sumando v hasta el final del pedido.

Una tercera definición equivalente de k -degeneración de un gráfico G (o que el número de color no exceda k  + 1) es que un gráfico es k -degenerado si y solo si los bordes de G pueden orientarse para formar un gráfico acíclico dirigido con grado superior a lo sumo k [14 ] . Tal orientación se puede obtener orientando cada borde hacia el primero de los dos vértices del borde de acuerdo con el orden. En la otra dirección, dada una orientación con salida mitad de salida k , se puede obtener una ordenación con número de coloración k  + 1 como una ordenación topológica de un gráfico acíclico dirigido.

k -Núcleos

El k -núcleo de G es el subgrafo conexo máximo de G en el que todos los vértices tienen grado al menos k . De manera equivalente, es uno de los componentes conectados del subgrafo G formado por la eliminación secuencial de todos los vértices con grado menor que k . Si hay un k - kernel no vacío, está claro que G tiene una degeneración de al menos k , y la degeneración de G es el mayor número k para el que G tiene un k - kernel.

Un vértice tiene nuclearidad si el vértice pertenece al -kernel pero no pertenece al -kernel .

El concepto de k -core se introdujo para estudiar la agrupación en redes sociales [15] y para describir el despliegue de grafos aleatorios [16] [17] [18] . El concepto también se ha trasladado a la bioinformática [1] [2] y la visualización de redes [19] [20] .

Algoritmos

Como Matula y Beck [8] describen , uno puede encontrar en tiempo lineal una ordenación de vértices en un grafo finito G que optimiza el número de colores de la ordenación mediante el uso de una cola contenedora para encontrar y eliminar vértices del grado más pequeño. La degeneración es entonces el mayor grado de cualquier vértice en el momento de su remoción.

Más detalladamente, el algoritmo funciona de la siguiente manera:

Al final del algoritmo, k contiene la degeneración del gráfico G y la lista L contiene los vértices en el orden óptimo para el número de color. En un grafo G , los i -kernels son sublistas de la lista L que consisten en los vértices agregados a L después de que k por primera vez toma un valor mayor o igual que i .

La inicialización de las variables L , d v , D y k se puede realizar fácilmente en tiempo lineal. Encontrar el siguiente vértice eliminado v y recalcular los elementos de D que contienen los vecinos del vértice v lleva un tiempo proporcional al valor de d v en este paso, pero la suma de dichos valores es igual al número de aristas del gráfico, por lo que el el tiempo total es lineal.

Relación con otros parámetros del gráfico

Si el grafo G se dirige de forma acíclica con grado exterior k , entonces sus aristas se pueden dividir en k bosques eligiendo un bosque para cada arco saliente de cada vértice. Así, la arborescencia del grafo G no excede su degeneración. En la dirección opuesta, un grafo con n vértices que se puede dividir en k bosques tiene como máximo k ( n  − 1) aristas y, por lo tanto, tiene vértices con un grado máximo de 2k − 1. Es decir, la degeneración es la mitad que la del árbol de gráficos También es posible calcular en tiempo polinomial la orientación de la gráfica que minimiza el grado de semidesviación sin necesidad de que la gráfica sea acíclica. Los bordes de un grafo con esta orientación se pueden dividir de la misma forma en k pseudobosques . Por el contrario, cualquier partición de los bordes del gráfico en k pseudobosques conduce a una orientación con el mayor grado de salida k (al elegir una orientación con un grado de salida de 1 para cada pseudobosque), por lo que el menor grado de salida de tal orientación es un pseudotreeness , que, nuevamente , no supera la degeneración [14 ] [21] [22] [23] [24] . El grosor también es (hasta un factor constante) proporcional a la madera, por lo que lo mismo se aplica a la degeneración [25] .

Un gráfico k -degenerado tiene un número cromático como máximo k  + 1. Esto se puede demostrar por simple inducción sobre el número de vértices, al igual que en la demostración del teorema de los seis colores para gráficos planos. Dado que el número cromático es un límite superior en el orden de la camarilla más grande , este orden no excede la degeneración más uno. Cuando se usa el algoritmo de coloración de ordenación codiciosa con el número óptimo de coloraciones, es posible colorear un gráfico k -degenerado usando como máximo k  + 1 colores [6] [26] .

Un grafo conectado por k vértices es un grafo que no se puede descomponer en múltiples componentes eliminando menos de k vértices o, de manera equivalente, es un gráfico en el que cada par de vértices se puede conectar mediante k caminos que no tienen vértices comunes. Dado que estos dos vértices deben pasar por diferentes aristas en estos caminos, un gráfico conectado por k vértices debe tener al menos k degeneración . Un concepto similar a k -cores, pero basado en la conectividad de vértices, es estudiado en la teoría de redes sociales bajo el nombre de conexiones estructurales [27] .

Si el ancho del árbol o el ancho del camino del grafo es como máximo k , entonces es un subgrafo de un grafo cordal que tiene un orden de eliminación perfecto tal que cada vértice tiene como máximo k vecinos predecesores. Por lo tanto, la degeneración no excede el ancho del árbol y el ancho del camino. Sin embargo, hay gráficos con degeneración limitada y ancho de árbol ilimitado, como las redes [28] .

La conjetura de Erdős-Boer se refiere a la conexión entre la degeneración de un gráfico G y el número de Ramsey de un gráfico G , el n más grande , para el cual cualquier coloración de dos colores de los bordes de un gráfico completo con n vértices debe contener una copia monocromática. de la gráfica G. Específicamente, la conjetura establece que para cualquier valor fijo de k , el número de Ramsey de gráficos k -degenerados crece linealmente con el número de vértices del gráfico [29] . La conjetura fue probada por Lee [30] .

Gráficos infinitos

Aunque los conceptos de degeneración y número de colores a menudo implican el contexto de grafos finitos, el objetivo inicial de Erdős y Hajnal [6] fue la teoría de grafos infinitos. Para un grafo infinito G , se puede definir el número colorante, de manera similar a la definición para grafos finitos, como el número cardinal más pequeño α para el cual existe un ordenamiento de los vértices de G bien ordenado , en el que cada vértice tiene menos que α vecinos entre los vértices anteriores en el ordenamiento. La desigualdad entre el número de color y el número cromático también es válida para el caso infinito. Erdős y Hajnal [6] argumentaron esto, y en el momento de la publicación de su artículo el hecho era bien conocido.

La degeneración de subconjuntos aleatorios de redes infinitas se estudia en una teoría llamada percolación iniciadora .

Notas

  1. ↑ 1 2 Altaf-Ul-Amin, Nishikata, Koma, Miyasato et al., 2003 .
  2. ↑ 1 2 Wuchty, Almaas, 2005 .
  3. ↑ Bader, Hogue, 2003 .
  4. ↑ Freuder, 1982 .
  5. ↑ Kirousis, Thilikos, 1996 .
  6. ↑ 1 2 3 4 5 Erdős, Hajnal, 1966 .
  7. ↑ Iraní, 1994 .
  8. ↑ 1 2 Matula, Beck, 1983 .
  9. ↑ 12 Lick , White, 1970 .
  10. ↑ Barabasi, Albert, 1999 .
  11. ↑ Jensen y Toft ( Jensen, Toft 2011 ), pág. 78 : "Es fácil ver que col( G ) = Δ( G ) + 1 si y solo si G tiene una componente regular Δ( G )". En la notación de Jensen y Toft, col( G ) es igual a la degeneración + 1, y Δ( G ) es igual al grado máximo del vértice.
  12. ↑ Matula, 1968 .
  13. ↑ Lick y White, 1970 , p. 1084 Proposición 1.
  14. ↑ 1 2 Chrobak, Eppstein, 1991 .
  15. ↑ Seidman, 1983 .
  16. ↑ Bollobas, 1984 .
  17. ↑ Luczak, 1991 .
  18. ↑ Dorogovtsev, Goltsev, Mendes, 2006 .
  19. ↑ Gaertler, Patrignani, 2004 .
  20. ↑ Álvarez-Hamelín, Dall'Asta, Barrat, Vespignani, 2005 .
  21. ↑ Gabow, Westermann, 1992 .
  22. ↑ Venkateswaran, 2004 .
  23. ↑ Asahiro, Miyano, Ono, Zenmyo, 2006 .
  24. ↑ Kowalik, 2006 .
  25. ↑ Dean, Hutchinson, Scheinerman, 1991 .
  26. ↑ Székeres, Wilf, 1968 .
  27. ↑ Moody, Blanco, 2003 .
  28. ↑ Robertson, Seymour, 1984 .
  29. ↑ Burr, Erdős, 1975 .
  30. ↑ Lee, 2017 .

Literatura