stringtranslate.com

Degeneración (teoría de grafos)

Un gráfico de 2 degeneraciones: 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 un grado como máximo dos. Su 2 núcleos, el subgrafo que queda después de eliminar repetidamente vértices de grado menor que dos, está sombreado.

En teoría de grafos , un gráfico k -degenerado es un gráfico no dirigido en el que cada subgrafo tiene un vértice de grado como máximo k : es decir, algún vértice en el subgrafo toca k o menos de los bordes del subgrafo. La degeneración de un gráfico es el valor más pequeño de k para el cual es k -degenerado. La degeneración de un gráfico es una medida de qué tan escaso es y está dentro de un factor constante de otras medidas de escasez, como la arboricidad de un gráfico.

La degeneración también se conoce como número k -core , [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 (llamado así en honor a Szekeres y Wilf  (1968). )). Los gráficos k -degenerados también se han llamado gráficos k -inductivos . [5] La degeneración de un gráfico se puede calcular 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 han sido (repetidamente) eliminados se denominan k -núcleos del gráfico y la degeneración de un gráfico es el valor más grande k tal que tenga un k - centro.

Ejemplos

Todo bosque finito tiene un vértice aislado (incidente sin bordes) o un vértice de hoja (incidente exactamente con un borde); por lo tanto, los árboles y los bosques son gráficos 1-degenerados. Cada gráfico 1-degenerado es un bosque.

Todo gráfico plano finito tiene un vértice de grado cinco o menos; por lo tanto, cada gráfico plano tiene 5 degeneraciones y la degeneración de cualquier gráfico plano es como máximo cinco. De manera similar, cada gráfico plano externo tiene una degeneración como máximo de dos, [7] y las redes apolíneas tienen una degeneración de 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 agrega al gráfico tiene m vértices previamente agregados. De ello se deduce que cualquier subgrafo de una red formada de esta manera tiene un vértice de grado como máximo m (el último vértice del subgrafo que se ha agregado al gráfico) y las redes de Barabási-Albert son automáticamente m -degeneradas.

Cada k -gráfico regular tiene degeneración exactamente  k . Más fuertemente, la degeneración de un gráfico es igual a su grado máximo de vértice si y sólo si al menos uno de los componentes conectados del gráfico es regular de grado máximo. Para todos los demás gráficos, la degeneración es estrictamente menor que el grado máximo. [9]

Definiciones y equivalencias

El número de coloración de un gráfico 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 que cada vértice tiene menos de κ vecinos que se encuentran antes en el ordenamiento. Cabe distinguir 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 que tengan el mismo color; el orden 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 gráfico G fue definida por Lick y White (1970) como el mínimo k 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 permiten 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 gráfico finito la degeneración es sólo uno menos que el número colorante. [10] Porque, si un gráfico tiene un orden con un número de coloración κ, entonces en cada subgrafo H el vértice que pertenece a H y está último en el orden 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 un número de color k + 1 encontrando repetidamente 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 formulación equivalente es que G es k -degenerado (o tiene un número de coloración como máximo k  + 1) si y sólo si los bordes de G pueden orientarse para formar un gráfico acíclico dirigido con un grado exterior como máximo k . [11] Tal orientación se puede formar orientando cada borde hacia el primero de sus dos puntos finales en un orden de números de colores. En la otra dirección, si se da una orientación con un grado exterior k ,  se puede obtener un orden con un número de color k + 1 como ordenamiento topológico del gráfico acíclico dirigido resultante.

k -Núcleos

Un k -núcleo de un gráfico G es un subgrafo conectado máximo de G en el que todos los vértices tienen un grado al menos k . De manera equivalente, es uno de los componentes conectados 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 degeneración al menos k , y la degeneración de G es la k más grande para la cual G tiene un k -núcleo.

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

El concepto de k -core se introdujo para estudiar la estructura de agrupamiento de las redes sociales [12] y 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] En Malliaros et al. se puede encontrar un estudio del tema, que cubre los conceptos principales, técnicas algorítmicas importantes y algunos dominios de aplicación. (2019).

La percolación Bootstrap es un proceso aleatorio estudiado como modelo epidémico [17] y como modelo de tolerancia a fallos para la informática 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 gráfico con un conjunto de vértices V y un conjunto de aristas E en tiempo y palabras de espacio, almacenando los vértices en una cola de cubos indexada en grados y eliminando repetidamente el vértice con el valor más pequeño. grado. La degeneración k viene 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 en 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 suma a L.

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

Si un gráfico G está orientado acíclicamente con un grado de salida k , entonces sus bordes pueden dividirse en k bosques eligiendo un bosque para cada borde de salida de cada nodo. Por tanto, la arboricidad de G es como máximo igual a su degeneración. En la otra dirección, un gráfico 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 gráfico que minimice el grado exterior pero que no sea necesario que sea acíclico. 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 exterior de k (al elegir una orientación exterior de 1 para cada pseudobosque). , por lo que el grado 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 tanto también de la degeneración. [21]

Un gráfico k -degenerado tiene un número cromático como máximo k  + 1; esto se demuestra mediante una simple inducción del número de vértices que es exactamente igual a la prueba del teorema de los seis colores para gráficas planas. Dado que el número cromático es un límite superior en el orden de la camarilla máxima , este último invariante también es, como máximo, degeneración más uno. Al utilizar un algoritmo de coloración codicioso en un orden con un número de coloración óptimo, se puede graficar el color en un gráfico k -degenerado utilizando como máximo k  + 1 colores. [22]

Un gráfico conectado a k vértices es un gráfico que no se puede dividir en más de un componente mediante la eliminación de menos de k vértices, o de manera equivalente, un gráfico en el que cada par de vértices se puede conectar mediante k caminos disjuntos de vértices. Dado que estos caminos deben salir de los dos vértices del par a través de bordes disjuntos, un gráfico conectado con k vértices debe tener una degeneración al menos k . Conceptos relacionados con k -cores pero basados ​​en la conectividad de vértices han sido estudiados en la teoría de redes sociales bajo el nombre de cohesión estructural . [23]

Si un gráfico tiene un ancho de árbol o un ancho de ruta como máximo k , entonces es un subgrafo de un gráfico 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 del árbol y como máximo igual al ancho de la ruta. Sin embargo, existen gráficos con degeneración limitada y ancho de árbol ilimitado, como los gráficos de cuadrícula . [24]

La conjetura de Burr-Erdős relaciona la degeneración de un gráfico G con el número de Ramsey de G , el mínimo n tal que cualquier coloración de dos aristas de un gráfico 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 k -gráficos degenerados crece linealmente en el número de vértices de los gráficos. [25] La conjetura fue probada por Lee (2017).

Cualquier gráfico de 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 gráficos con degeneración acotada tiene pocas camarillas.

graficos infinitos

Aunque los conceptos de degeneración y coloración del número se consideran frecuentemente en el contexto de los grafos finitos, la motivación original de Erdős y Hajnal (1966) fue la teoría de los grafos infinitos. Para un gráfico infinito G , se puede definir el número de coloración de manera análoga a la definición de gráficos finitos, como el número cardinal más pequeño α tal que exista un buen ordenamiento de los vértices de G en el que cada vértice tenga menos de α vecinos que sean anteriormente en el pedido. La desigualdad entre coloración y números cromáticos se mantiene también en este escenario infinito; Erdős y Hajnal (1966) afirman que, en el momento de la publicación de su artículo, ya era bien conocido.

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

Ver 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. ^ Lamer y blanco (1970).
  8. ^ Barabási y Albert (1999).
  9. ^ Jensen y Toft (2011), pág. 78: "Es fácil ver que col( G ) = Δ( G ) + 1 si y sólo si G tiene un componente regular Δ( G )". 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. ^ Mátula (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 col. (2012).
  18. ^ Kirkpatrick y col. (2002).
  19. ^ Adler (1991).
  20. ^ Chrobak y Eppstein (1991); Gabow y Westermann (1992); Venkateswaran (2004); Asahiro et al. (2006); Kowalik (2006).
  21. ^ Decano, Hutchinson y Scheinerman (1991).
  22. ^ Erdős y Hajnal (1966); Székeres y Wilf (1968).
  23. ^ De mal humor y blanco (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 gráficos dispersos en un tiempo casi óptimo. En O. Cheong, K.-Y. Chwa y K. Park (Eds.), Algoritmos y computación (Vol. 6506, págs. 403–414). Berlín, Heidelberg: Springer Berlín Heidelberg. https://doi.org/10.1007/978-3-642-17517-6_36

Referencias