stringtranslate.com

Degeneración (teoría de grafos)

Un grafo 2-degenerado: cada vértice tiene como máximo dos vecinos a su izquierda, por lo que el vértice más a la derecha de cualquier subgrafo tiene como máximo grado dos. Su núcleo 2, el subgrafo que queda después de eliminar repetidamente vértices de grado menor a dos, está sombreado.

En teoría de grafos , un grafo k -degenerado es un grafo no dirigido en el que cada subgrafo tiene un vértice de grado k como máximo : es decir, algún vértice en el subgrafo toca k o menos de las aristas del subgrafo. La degeneración de un grafo es el valor más pequeño de k para el cual es k -degenerado. La degeneración de un grafo es una medida de cuán disperso es, y está 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 número de núcleo k , [1] ancho , [2] y enlace , [3] y es esencialmente lo mismo que el número de coloración [4] o número de Szekeres-Wilf (nombrado así por Szekeres y Wilf  (1968)). Los grafos k -degenerados también se han llamado grafos k -inductivos . [5] La degeneración de un grafo puede calcularse en tiempo lineal mediante un algoritmo que elimina repetidamente los vértices de grado mínimo. [6] Los componentes conectados que quedan después de que todos los vértices de grado menor que k hayan sido (repetidamente) eliminados se denominan k -núcleos del grafo y la degeneración de un grafo es el valor más grande k tal que tiene un k -núcleo.

Ejemplos

Todo bosque finito tiene un vértice aislado (que no incide en ninguna arista) o un vértice de hoja (que incide exactamente en una arista); 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 menos; 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 plano exterior tiene una degeneración como máximo dos, [7] y las redes apolíneas tienen una degeneración tres.

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

Todo grafo k -regular tiene una degeneración exactamente  k . Más fuertemente, la degeneración de un grafo es igual a su grado máximo de vértice si y solo si al menos uno de los componentes conexos 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]

Definiciones y equivalencias

El número de coloración de un grafo G fue definido por Erdős y Hajnal (1966) como el menor κ para el cual existe un ordenamiento de los vértices de G en el cual cada vértice tiene menos de κ vecinos que están antes en el ordenamiento. Debe distinguirse del número cromático de G , el número mínimo de colores necesarios para colorear los vértices de modo que no haya dos vértices adyacentes con el mismo color; el ordenamiento que determina el número de coloración proporciona un orden para colorear los vértices de G con el número de coloración, pero en general el número cromático puede ser menor.

La degeneración de un grafo G fue definida por Lick y White (1970) como el k menor tal que cada subgrafo inducido de G contiene un vértice con 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 que sean menores o iguales a los grados de vértice en el subgrafo inducido por el mismo conjunto de vértices.

Los dos conceptos de número colorante y degeneración son equivalentes: en cualquier grafo finito la degeneración es sólo uno menos que el número colorante. [10] Porque, si un grafo tiene un ordenamiento con número colorante κ entonces en cada subgrafo H el vértice que pertenece a H y es último en el ordenamiento tiene como máximo κ − 1 vecinos en H . En la otra dirección, si G es k -degenerado, entonces un ordenamiento con número colorante k  + 1 se puede obtener encontrando repetidamente un vértice v con como máximo k vecinos, quitando v del grafo, ordenando los vértices restantes y añadiendo v al final del orden.

Una tercera formulación equivalente es que G es k -degenerado (o tiene un número de coloración como máximo k  + 1) si y solo si las aristas de G pueden orientarse para formar un grafo acíclico dirigido con un grado de salida como máximo k . [11] Tal orientación puede formarse orientando cada arista hacia el primero de sus dos puntos finales en un ordenamiento de número de coloración. En la otra dirección, si se da una orientación con un grado de salida k ,  se puede obtener un ordenamiento con un número de coloración k + 1 como un ordenamiento topológico del grafo acíclico dirigido resultante.

a-Núcleos

Un k -núcleo de un grafo G es un subgrafo conexo maximalista de G en el que todos los vértices tienen un grado de al menos k . De manera equivalente, es uno de los componentes conexos del subgrafo de G formado al eliminar repetidamente todos los vértices de grado menor que k . Si existe un k -núcleo no vacío , entonces, claramente, G tiene una degeneración de al menos k , y la degeneración de G es el k más grande para el cual G tiene un k -núcleo.

Un vértice tiene centralidad si pertenece a un núcleo pero no a ningún núcleo.

El concepto de un k -núcleo se introdujo para estudiar la estructura de agrupamiento de las redes sociales [12] y para describir la evolución de gráficos aleatorios . [13] También se ha aplicado en bioinformática , [14] visualización de redes , [15] y resiliencia de redes en ecología . [16] Se puede encontrar un estudio del tema, que cubre los conceptos principales, técnicas algorítmicas importantes y algunos dominios de aplicación, en Malliaros et al. (2019).

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

Algoritmos

Matula y Beck (1983) describen un algoritmo para derivar el orden de degeneración de un grafo con un conjunto de vértices V y un conjunto de aristas E en el tiempo y en el espacio, almacenando los vértices en una cola de cubos indexada por grado y eliminando repetidamente el vértice con el grado más bajo. La degeneración k está dada por el grado más alto de cualquier vértice en el momento de su eliminación.

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

Al final del algoritmo, cualquier vértice tendrá como máximo k aristas hacia los vértices . Los l -núcleos de G son los subgrafos que son inducidos por los vértices , donde i es el primer vértice con grado en el momento en que se agrega a L .

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

Si un grafo G está orientado acíclicamente con un grado de salida k , entonces sus aristas pueden dividirse en k bosques eligiendo un bosque para cada arista saliente de cada nodo. Por lo tanto, la arboricidad de G es como máximo igual a su degeneración. En la otra dirección, un grafo de n -vértices que puede dividirse en k bosques tiene como máximo k ( n  − 1) aristas y, por lo tanto, tiene un vértice de grado como máximo 2 k − 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 se requiere que sea acíclica. Los bordes de un gráfico con tal orientación se pueden dividir de la misma manera en k pseudobosques y, a la inversa, cualquier partición de los bordes de un gráfico en k pseudobosques conduce a una orientación de grado de salida k (eligiendo una orientación de grado de salida 1 para cada pseudobosque), por lo que el grado de salida mínimo de tal orientación es la pseudoarboricidad , que nuevamente es como máximo igual a la degeneración. [20] El espesor también está dentro de un factor constante de la arboricidad y, por lo tanto, también de la degeneración. [21]

Un grafo k -degenerado tiene un número cromático como máximo k  + 1; esto se demuestra mediante una inducción simple sobre el número de vértices que es exactamente como la prueba del teorema de los seis colores para grafos planares. Dado que el número cromático es un límite superior en el orden de la clique máxima , el último invariante también es como máximo degeneración más uno. Al utilizar un algoritmo de coloración voraz en un ordenamiento con un número de coloración óptimo, se puede colorear un grafo k -degenerado utilizando como máximo k  + 1 colores. [22]

Un grafo con conexión de k vértices es un grafo que no se puede dividir en más de un componente mediante la eliminación de menos de k vértices, o equivalentemente un grafo en el que cada par de vértices se puede conectar mediante k caminos disjuntos entre vértices. Dado que estos caminos deben salir de los dos vértices del par a través de aristas disjuntas, un grafo con conexión de k vértices debe tener una degeneración de al menos k . Los conceptos relacionados con los 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 . [23]

Si un grafo tiene un ancho de árbol o un ancho de camino como máximo 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 k vecinos anteriores. Por lo tanto, la degeneración es como máximo igual al ancho de árbol y como máximo igual al ancho de camino. Sin embargo, existen grafos con degeneración acotada y ancho de árbol ilimitado, como los grafos de cuadrícula . [24]

La conjetura de Burr–Erdős relaciona la degeneración de un grafo G con el número de Ramsey de G , el menor n tal que cualquier coloración de dos aristas de un grafo completo de n -vértices debe contener una copia monocromática de G . Específicamente, la conjetura es que para cualquier valor fijo de k , el número de Ramsey de grafos k -degenerados crece linealmente en el número de vértices de los grafos. [25] La conjetura fue probada por Lee (2017).

Cualquier grafo -vértice con degeneración tiene como máximo camarillas máximas siempre que y , [26] por lo que se dice que la clase de grafos con degeneración acotada tiene pocas camarillas.

Grafos infinitos

Aunque los conceptos de degeneración y número colorante se consideran con frecuencia en el contexto de grafos finitos, la motivación original de Erdős y Hajnal (1966) fue la teoría de grafos infinitos. Para un grafo infinito G , se puede definir el número colorante de manera análoga a la definición para grafos finitos, como el número cardinal α más pequeño tal que existe un buen ordenamiento de los vértices de G en el que cada vértice tiene menos de α vecinos que están antes en el ordenamiento. La desigualdad entre los números colorantes y cromáticos se mantiene también en este entorno infinito; Erdős y Hajnal (1966) afirman que, en el momento de la publicación de su artículo, ya era bien conocida.

La degeneración de subconjuntos aleatorios de redes infinitas se ha estudiado bajo el nombre de percolación bootstrap .

Véase también

Notas

  1. ^ Bader y Hogue (2003).
  2. ^ Freuder (1982).
  3. ^ Kirousis y Thilikos (1996).
  4. ^ Erdős y Hajnal (1966).
  5. ^ Iraní (1994).
  6. ^ Matula y Beck (1983).
  7. ^ Lick y White (1970).
  8. ^ Barabási y Albert (1999).
  9. ^ Jensen & Toft (2011), p. 78: "Es fácil ver que col( G ) = Δ( G ) + 1 si y solo si G tiene un componente Δ( G )-regular". En la notación utilizada por Jensen y Toft, col( G ) es la degeneración más uno, y Δ( G ) es el grado máximo del vértice.
  10. ^ Matula (1968); Lick & White (1970), Proposición 1, página 1084.
  11. ^ Chrobak y Eppstein (1991).
  12. ^ Seidman (1983).
  13. ↑ Bollobás (1984); Łuczak (1991);Dorogovtsev, Goltsev y Mendes (2006).
  14. ^ Bader y Hogue (2003); Altaf-Ul-Amin et al. (2003); Wuchty y Almaas (2005).
  15. ^ Gaertler y Patrignani (2004); Álvarez-Hamelín et al. (2006).
  16. ^ García-Algarra et al. (2017).
  17. ^ Balogh y otros (2012).
  18. ^ Kirkpatrick y otros (2002).
  19. ^ Adler (1991).
  20. ^ Chrobak y Eppstein (1991); Gabow y Westermann (1992); Venkateswaran (2004); Asahiro et al. (2006); Kowalik (2006).
  21. ^ Dean, Hutchinson y Scheinerman (1991).
  22. ^ Erdős y Hajnal (1966); Székeres y Wilf (1968).
  23. ^ Moody y White (2003).
  24. ^ Robertson y Seymour (1984).
  25. ^ Burr y Erdős (1975).
  26. ^ Eppstein, D., Löffler, M. y Strash, D. (2010). Listado de todas las camarillas máximas en grafos dispersos en tiempo casi óptimo. En O. Cheong, K.-Y. Chwa y K. Park (Eds.), Algorithms and Computation (Vol. 6506, págs. 403–414). Berlín, Heidelberg: Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36

Referencias