Degeneración (teoría de grafos)

En teoría de grafos , un grafo k -degenerado es un grafo no dirigido en el que cada subgrafo no vacío tiene al menos un vértice de grado como máximo${\displaystyle k}$. Es decir, algún vértice del subgrafo toca${\displaystyle k}$o menos de las aristas del subgrafo. La degeneración de un grafo es el valor más pequeño de${\displaystyle k}$para lo cual es${\displaystyle k}$-degenerado. La degeneración de un grafo es una medida de su dispersión y se encuentra dentro de un factor constante de otras medidas de dispersión, como la arboricidad de un grafo.

La degeneración también se conoce como el número k -núcleo , ^{[ 1 ]} ancho , ^{[ 2 ]} y enlace , ^{[ 3 ]} y es esencialmente lo mismo que el número de coloración ^{[ 4 ]} o el número de Szekeres-Wilf (nombrado en honor a Szekeres y Wilf ( 1968 ) ). ${\displaystyle k}$Los grafos -degenerados también se han llamado grafos k -inductivos . ^{[ 5 ]} La degeneración de un grafo se puede calcular en tiempo lineal mediante un algoritmo que elimina repetidamente los vértices de grado mínimo. ^{[ 6 ]} Los componentes conexos que quedan después de todos los vértices de grado menor que${\displaystyle k}$Los elementos que han sido eliminados (repetidamente) se denominan los k -núcleos del grafo y la degeneración de un grafo es el valor más grande.${\displaystyle k}$de tal manera que tenga una${\displaystyle k}$-centro.

Todo bosque finito tiene un vértice aislado (que no incide en ninguna arista) o un vértice hoja (que incide en una sola arista), y todo subgrafo de un bosque es también un bosque; por lo tanto, los árboles y los bosques son grafos 1-degenerados. Todo grafo 1-degenerado es un bosque.

Todo grafo planar finito tiene un vértice de grado cinco o menor; por lo tanto, todo grafo planar es 5-degenerado, y la degeneración de cualquier grafo planar es como máximo cinco. De manera similar, todo grafo planar exterior tiene una degeneración como máximo dos, ^{[ 7 ]} y las redes apolíneas tienen una degeneración de tres.

El modelo de Barabási-Albert para generar redes aleatorias libres de escala ^{[ 8 ]} está parametrizado por un número${\displaystyle m}$de tal manera que cada vértice que se agrega al grafo tenga${\displaystyle m}$vértices previamente añadidos. De ello se deduce que cualquier subgrafo de una red formada de esta manera tiene un vértice de grado como máximo${\displaystyle m}$(el último vértice del subgrafo que se ha añadido al grafo) y las redes de Barabási-Albert se generan automáticamente.${\displaystyle m}$-degenerar.

Cada${\displaystyle k}$- El grafo regular tiene degeneración exactamente${\displaystyle k}$Más concretamente , la degeneración de un grafo es igual a su grado máximo de vértice si y solo si al menos una de las componentes conexas del grafo es regular de grado máximo. Para todos los demás grafos, la degeneración es estrictamente menor que el grado máximo. ^{[ 9 ]}

El número de coloración de un gráfico${\displaystyle G}$fue definido por Paul Erdős y András Hajnal como el menos${\displaystyle \kappa }$para la cual existe un ordenamiento de los vértices de${\displaystyle G}$en el que cada vértice tiene menos de${\displaystyle \kappa }$vecinos que están antes en el ordenamiento. Debe distinguirse del número cromático de${\displaystyle G}$, el número mínimo de colores necesarios para colorear los vértices de manera que no haya dos vértices adyacentes con el mismo color. El orden utilizado para definir el número de coloración proporciona un orden para colorear los vértices de${\displaystyle G}$para el cual un algoritmo de coloración voraz utiliza una cantidad de colores que es como máximo el número de coloración. Sin embargo, en general, otras coloraciones pueden usar menos colores. ^{[ 4 ]}

Posteriormente, y de forma independiente, la degeneración de un grafo G fue definida por Don Lick y Arthur White como la menor${\displaystyle k}$de tal manera que cada subgrafo inducido de${\displaystyle G}$contiene un vértice con${\displaystyle k}$o menos vecinos. La definición sería la misma si se permitieran subgrafos arbitrarios en lugar de subgrafos inducidos, ya que un subgrafo no inducido solo puede tener grados de vértice menores o iguales a los grados de vértice en el subgrafo inducido por el mismo conjunto de vértices. ^{[ 10 ]}

Los dos conceptos de número de coloración y degeneración son equivalentes: en todo grafo finito la degeneración es solo uno menos que el número de coloración. ^{[ 11 ]} Porque, si un grafo tiene un ordenamiento con número de coloración${\displaystyle \kappa }$luego en cada subgrafo${\displaystyle H}$el vértice que pertenece a${\displaystyle H}$y es el último en el orden tiene como máximo${\displaystyle \kappa -1}$vecinos en${\displaystyle H}$; por lo tanto, cada subgrafo${\displaystyle H}$contiene un vértice de bajo grado. En la otra dirección, si${\displaystyle G}$es${\displaystyle k}$-degenerado, entonces un ordenamiento con número de coloración${\displaystyle k+1}$se puede obtener encontrando repetidamente un vértice${\displaystyle v}$con como máximo${\displaystyle k}$vecinos, eliminando${\displaystyle v}$del gráfico, ordenando los vértices restantes y añadiendo${\displaystyle v}$hasta el final del pedido.

Una tercera formulación equivalente es que${\displaystyle G}$es${\displaystyle k}$-degenerado (o tiene como máximo un número de coloración)${\displaystyle k+1}$) si y solo si los bordes de${\displaystyle G}$puede orientarse para formar un grafo acíclico dirigido con grado de salida como máximo${\displaystyle k}$. ^{[ 12 ]} Dicha orientación se puede formar orientando cada arista hacia el primero de sus dos puntos extremos en un ordenamiento de números de coloración. En la otra dirección, si una orientación con grado de salida${\displaystyle k}$Se proporciona un ordenamiento con número de coloración${\displaystyle k+1}$se puede obtener como cualquier ordenamiento topológico del grafo acíclico dirigido resultante.

A${\displaystyle k}$-núcleo de un grafo${\displaystyle G}$es un subgrafo conexo maximal de${\displaystyle G}$en el que todos los vértices tienen grado al menos${\displaystyle k}$. De forma equivalente, es uno de los componentes conexos del subgrafo de${\displaystyle G}$formado eliminando repetidamente todos los vértices de grado menor que${\displaystyle k}$. Si no está vacío${\displaystyle k}$-core existe, entonces, claramente,${\displaystyle G}$tiene degeneración al menos${\displaystyle k}$y la degeneración de${\displaystyle G}$es el más grande${\displaystyle k}$para qué${\displaystyle G}$tiene un${\displaystyle k}$-centro.

Un vértice${\displaystyle u}$tiene esencia${\displaystyle c}$si pertenece a un ${\displaystyle c}$-núcleo pero no a ninguno${\displaystyle (c+1)}$-centro.

El concepto de un${\displaystyle k}$-core se introdujo para estudiar la estructura de agrupamiento de redes sociales ^{[ 13 ]} y para describir la evolución de grafos aleatorios . ^{[ 14 ]} También se ha aplicado en bioinformática , ^{[ 15 ]} visualización de redes , ^{[ 16 ]} y resiliencia de redes en ecología . ^{[ 17 ]} Una revisión del tema, que abarca los conceptos principales, técnicas algorítmicas importantes, así como algunos dominios de aplicación, se puede encontrar en Malliaros et al. (2019) .

La percolación bootstrap es un proceso aleatorio estudiado como un modelo epidémico ^{[ 18 ]} y como un modelo para la tolerancia a fallos en la computación distribuida . ^{[ 19 ]} Consiste en seleccionar un subconjunto aleatorio de celdas activas de una red u otro espacio, y luego considerar el${\displaystyle k}$-núcleo del subgrafo inducido de este subconjunto. ^{[ 20 ]}

Matula y Beck (1983) describen un algoritmo para derivar el orden de degeneración de un grafo.${\displaystyle G=(V,E)}$con conjunto de vértices${\displaystyle V}$y conjunto de bordes${\displaystyle E}$en${\displaystyle O(\vert V\vert +\vert E\vert )}$tiempo y${\displaystyle O(\vert V\vert )}$palabras de espacio, almacenando vértices en una cola de cubetas indexada por grado y eliminando repetidamente el vértice con el grado más pequeño. La degeneración${\displaystyle k}$viene dado por el grado más alto de cualquier vértice en el momento de su eliminación.

En detalle, el algoritmo procede de la siguiente manera:

• Inicializar una lista de salida${\displaystyle L}$.
• Calcular un número${\displaystyle d_{v}}$para cada vértice${\displaystyle v}$en${\displaystyle G}$, el número de vecinos de${\displaystyle v}$que no estén ya en${\displaystyle L}$Inicialmente, estos números son simplemente los grados de los vértices.
• Inicializar un array${\displaystyle D}$de tal manera que${\displaystyle D[i]}$contiene una lista de los vértices${\displaystyle v}$que no estén ya en${\displaystyle L}$para qué${\displaystyle d_{v}=i}$. Eso es,${\displaystyle D[i]=\{v\in V\setminus L\mid d_{v}=i\}}$.
• Inicializar${\displaystyle k}$a 0.
• Repetir${\displaystyle n}$veces:
  • Escanee las celdas de la matriz${\displaystyle D[0],D[1],\dots }$hasta encontrar un${\displaystyle i}$para qué${\displaystyle D[i]}$no está vacío.
  • Colocar${\displaystyle k}$a${\displaystyle \max\{k,i\}}$.
  • Seleccione un vértice arbitrario${\displaystyle v}$de${\displaystyle D[i]}$. Agregar${\displaystyle v}$al principio de${\displaystyle L}$y eliminarlo de${\displaystyle D[i]}$.
  • Por cada vecino${\displaystyle w}$de${\displaystyle v}$no está ya en${\displaystyle L}$, eliminar${\displaystyle w}$de${\displaystyle D[d_{w}]}$, resta uno de${\displaystyle d_{w}}$y añadir${\displaystyle w}$a la ubicación${\displaystyle D[d_{w}]}$indexado por el valor actualizado de${\displaystyle d_{w}}$.

Al final del algoritmo, cualquier vértice${\displaystyle L[i]}$tendrá como máximo${\displaystyle k}$aristas a los vértices${\displaystyle L[1,\ldots ,i-1]}$. El${\displaystyle \ell }$-núcleos de${\displaystyle G}$son los componentes conectados de los subgrafos${\displaystyle H_{\ell }\subset G}$que son inducidos por los vértices${\displaystyle L[1,\ldots ,i]}$, dónde${\displaystyle i}$es el primer vértice con grado${\displaystyle \geq \ell }$en el momento en que se agrega a${\displaystyle L}$.

Si un gráfico${\displaystyle G}$está orientado acíclicamente con grado de salida${\displaystyle k}$, entonces sus bordes pueden dividirse en${\displaystyle k}$bosques eligiendo un bosque para cada borde saliente de cada nodo. Por lo tanto, la arboricidad de${\displaystyle G}$es como máximo igual a su degeneración. En la otra dirección, un${\displaystyle n}$-grafo de vértices que se puede particionar en${\displaystyle k}$Los bosques tienen como máximo${\displaystyle k(n-1)}$bordes y por lo tanto tiene un vértice de grado como máximo${\displaystyle 2k-1}$– por lo tanto, la degeneración es menor que el doble de la arboricidad. También se puede calcular en tiempo polinomial una orientación de un grafo que minimice el grado de salida pero que no requiere ser acíclico. Las aristas de un grafo con dicha orientación se pueden particionar de la misma manera en${\displaystyle k}$pseudobosques y, a la inversa, cualquier partición de las aristas de un grafo en${\displaystyle k}$Los pseudobosques conducen a un grado de salida.${\displaystyle k}$orientación (al elegir una orientación de grado de salida 1 para cada pseudobosque), de modo que el grado de salida mínimo de dicha orientación es la pseudoarboricidad , que de nuevo es como máximo igual a la degeneración. ^{[ 21 ]} El espesor también está dentro de un factor constante de la arboricidad y, por lo tanto, también de la degeneración. ^{[ 22 ]}

A${\displaystyle k}$-El gráfico degenerado tiene como máximo un número cromático${\displaystyle k+1}$Esto se demuestra mediante una simple inducción sobre el número de vértices, que es exactamente igual a la demostración del teorema de los seis colores para grafos planares. Dado que el número cromático es una cota superior en el orden de la clique máxima , el último invariante también es como máximo degeneración más uno. Al usar un algoritmo de coloración voraz en un ordenamiento con número de coloración óptimo, se puede colorear un grafo.${\displaystyle k}$-grafo degenerado usando como máximo${\displaystyle k+1}$colores. ^{[ 23 ]}

Un grafo k -conectado por vértices es un grafo que no puede particionarse en más de un componente eliminando menos de k vértices.${\displaystyle k}$vértices, o equivalentemente un grafo en el que cada par de vértices puede conectarse mediante${\displaystyle k}$caminos disjuntos en vértices. Dado que estos caminos deben salir de los dos vértices del par a través de aristas disjuntas, un${\displaystyle k}$-El grafo conexo por vértices debe tener al menos degeneración${\displaystyle k}$. Conceptos relacionados con${\displaystyle k}$-núcleos pero basados ​​en la conectividad de vértices se han estudiado en la teoría de redes sociales bajo el nombre de cohesión estructural . ^{[ 24 ]}

Si un grafo tiene un ancho de árbol o un ancho de ruta como máximo${\displaystyle k}$, entonces es un subgrafo de un grafo cordal que tiene un orden de eliminación perfecto en el que cada vértice tiene como máximo${\displaystyle k}$vecinos anteriores. Por lo tanto, la degeneración es como máximo igual al ancho del árbol y como máximo igual al ancho del camino. Sin embargo, existen grafos con degeneración limitada y ancho de árbol ilimitado, como los grafos de cuadrícula . ^{[ 25 ]}

La conjetura de Burr-Erdős relaciona la degeneración de un grafo.${\displaystyle G}$al número de Ramsey de${\displaystyle G}$, el menos${\displaystyle n}$de tal manera que cualquier coloración de dos aristas de un${\displaystyle n}$-El grafo completo de vértices debe contener una copia monocromática de${\displaystyle G}$. Específicamente, la conjetura es que para cualquier valor fijo de${\displaystyle k}$, el número de Ramsey de${\displaystyle k}$-grafos degenerados crece linealmente en el número de vértices de los grafos. ^{[ 26 ]} La conjetura fue demostrada por Lee (2017) . ^{[ 27 ]}

Cualquier${\displaystyle n}$-grafo de vértices con degeneración${\displaystyle d}$tiene como máximo${\textstyle (nd)3^{d/3}}$camarillas máximas siempre${\displaystyle d\equiv 0{\bmod {3}}}$y${\displaystyle n\geq d+3}$, ^{[ 28 ]} por lo que se dice que la clase de grafos con degeneración limitada tiene pocas camarillas.

Aunque los conceptos de degeneración y número de coloración se consideran frecuentemente en el contexto de grafos finitos, la motivación original de Paul Erdős y András Hajnal fue la teoría de grafos infinitos. Para un grafo infinito${\displaystyle G}$, se puede definir el número de coloración de forma análoga a la definición para grafos finitos, como el número cardinal más pequeño.${\displaystyle \alpha }$de tal manera que exista un buen ordenamiento de los vértices de${\displaystyle G}$en el que cada vértice tiene menos de${\displaystyle \alpha }$vecinos que están antes en el ordenamiento. La desigualdad entre números de coloración y números cromáticos también se mantiene en este contexto infinito; Erdős y Hajnal afirman que, en la fecha de publicación de su artículo en 1966, esto ya era bien conocido. ^{[ 4 ]}

La degeneración de subconjuntos aleatorios de retículos infinitos se ha estudiado bajo el nombre de percolación bootstrap .

• teoría de grafos
• Ciencia de redes
• Teoría de la percolación
• Estructura núcleo-periferia
• La conjetura de Cereceda