Hispanopedia Wiki
Articulo de referencia

Grafo implícito

En el estudio de los algoritmos de grafos , una representación implícita de un grafo (o simplemente grafo implícito ) es un grafo cuyos vértices o aristas no están representados...

Hispanopedia WikiContenido en espanolLectura gratuita

En el estudio de los algoritmos de grafos , una representación implícita de un grafo (o simplemente grafo implícito ) es un grafo cuyos vértices o aristas no están representados como objetos explícitos en la memoria de una computadora, sino que se determinan algorítmicamente a partir de alguna otra entrada, por ejemplo, una función computable .

Cada vértice del grafo implícito está definido por una casilla en el tablero, y cada arista es un movimiento en el recorrido del caballo .

Representaciones de los barrios

La noción de grafo implícito es común en varios algoritmos de búsqueda que se describen en términos de grafos. En este contexto, un grafo implícito puede definirse como un conjunto de reglas para definir todos los vecinos de cualquier vértice especificado. [ 1 ] Este tipo de representación de grafo implícito es análoga a una lista de adyacencia , ya que proporciona un acceso sencillo a los vecinos de cada vértice. Por ejemplo, al buscar una solución para un rompecabezas como el Cubo de Rubik , se puede definir un grafo implícito en el que cada vértice representa uno de los posibles estados del cubo, y cada arista representa un movimiento de un estado a otro. Es sencillo generar los vecinos de cualquier vértice probando todos los movimientos posibles en el rompecabezas y determinando los estados alcanzados por cada uno de estos movimientos; sin embargo, es necesaria una representación implícita, ya que el espacio de estados del Cubo de Rubik es demasiado grande para permitir que un algoritmo enumere todos sus estados. [ 2 ]

En la teoría de la complejidad computacional , se han definido varias clases de complejidad en relación con los grafos implícitos, definidos como se indicó anteriormente por una regla o algoritmo para listar los vecinos de un vértice. Por ejemplo, PPA es la clase de problemas en los que se da como entrada un grafo implícito no dirigido (en el que los vértices son cadenas binarias de n bits, con un algoritmo de tiempo polinomial para listar los vecinos de cualquier vértice) y un vértice de grado impar en el grafo, y se debe encontrar un segundo vértice de grado impar. Por el lema del apretón de manos , tal vértice existe; encontrarlo es un problema en NP , pero los problemas que se pueden definir de esta manera no necesariamente son NP-completos , ya que se desconoce si PPA  =  NP. PPAD es una clase análoga definida en grafos dirigidos implícitos que ha atraído la atención en la teoría de juegos algorítmica porque contiene el problema de calcular un equilibrio de Nash . [ 3 ] El problema de probar la alcanzabilidad de un vértice a otro en un grafo implícito también puede usarse para caracterizar clases de complejidad no determinista con espacio limitado, incluyendo NL (la clase de problemas que pueden caracterizarse por la alcanzabilidad en grafos dirigidos implícitos cuyos vértices son cadenas de bits de O(log n ) bits), SL (la clase análoga para grafos no dirigidos) y PSPACE (la clase de problemas que pueden caracterizarse por la alcanzabilidad en grafos implícitos con cadenas de bits de longitud polinomial). En este contexto de teoría de la complejidad, los vértices de un grafo implícito pueden representar los estados de una máquina de Turing no determinista , y las aristas pueden representar posibles transiciones de estado, pero los grafos implícitos también pueden usarse para representar muchos otros tipos de estructura combinatoria. [ 4 ] PLS , otra clase de complejidad, captura la complejidad de encontrar óptimos locales en un grafo implícito. [ 5 ]

Los modelos de grafos implícitos también se han utilizado como una forma de relativización para demostrar separaciones entre clases de complejidad más fuertes que las conocidas para modelos no relativizados. Por ejemplo, Childs et al. utilizaron representaciones de vecindad de grafos implícitos para definir un problema de recorrido de grafos que puede resolverse en tiempo polinomial en una computadora cuántica , pero que requiere tiempo exponencial para resolverse en cualquier computadora clásica. [ 6 ]

Esquemas de etiquetado de adyacencia

En el contexto de las representaciones eficientes de grafos, JH Muller definió una estructura local o esquema de etiquetado de adyacencia para un grafo G en una familia F de grafos dada como la asignación de un identificador de O (log n ) bits a cada vértice de G , junto con un algoritmo (que puede depender de F pero es independiente del grafo G individual ) que toma como entrada dos identificadores de vértice y determina si son o no los extremos de una arista en G. Es decir, este tipo de representación implícita es análoga a una matriz de adyacencia : es sencillo comprobar si dos vértices son adyacentes, pero encontrar los vecinos de cualquier vértice puede implicar recorrer todos los vértices y comprobar cuáles son vecinos. [ 7 ]

Las familias de grafos con esquemas de etiquetado de adyacencia incluyen:

Grafos de grado acotado
Si cada vértice en G tiene como máximo d vecinos, se pueden numerar los vértices de G del 1 al n y el identificador de un vértice debe ser la ( d + 1) -tupla formada por su propio número y los números de sus vecinos. Dos vértices son adyacentes cuando los primeros números de sus identificadores aparecen posteriormente en el identificador del otro vértice. De forma más general, se puede utilizar el mismo enfoque para proporcionar una representación implícita de grafos con arboricidad acotada o degeneración acotada , incluidos los grafos planares y los grafos de cualquier familia de grafos cerrados en menores . [ 8 ] [ 9 ]
gráficos de intersección
Un grafo de intervalos es el grafo de intersección de un conjunto de segmentos de línea en la recta real . Se le puede asignar un esquema de etiquetado de adyacencia en el que los puntos que son extremos de los segmentos de línea se numeran del 1 al 2n y cada vértice del grafo se representa mediante los números de los dos extremos de su intervalo correspondiente. Con esta representación, se puede comprobar si dos vértices son adyacentes comparando los números que los representan y verificando que estos números definen intervalos superpuestos. El mismo enfoque funciona para otros grafos de intersección geométricos, incluidos los grafos de boxicidad acotada y los grafos circulares , y subfamilias de estas familias, como los grafos hereditarios de distancia y los cografos . [ 8 ] [ 10 ] Sin embargo, una representación de grafo de intersección geométrico no siempre implica la existencia de un esquema de etiquetado de adyacencia, ya que puede requerir más de un número logarítmico de bits para especificar cada objeto geométrico. Por ejemplo, representar un grafo como un grafo de disco unitario puede requerir exponencialmente muchos bits para las coordenadas de los centros de los discos. [ 11 ]
Gráficos de comparabilidad de baja dimensión
El grafo de comparabilidad para un conjunto parcialmente ordenado tiene un vértice por cada elemento del conjunto y una arista entre dos elementos del conjunto que están relacionados por el orden parcial. La dimensión de orden de un orden parcial es el número mínimo de órdenes lineales cuya intersección es el orden parcial dado. Si un orden parcial tiene una dimensión de orden acotada, entonces se puede definir un esquema de etiquetado de adyacencia para los vértices en su grafo de comparabilidad etiquetando cada vértice con su posición en cada uno de los órdenes lineales definitorios y determinando que dos vértices son adyacentes si cada par correspondiente de números en sus etiquetas tiene la misma relación de orden que cada otro par. En particular, esto permite un esquema de etiquetado de adyacencia para los grafos de comparabilidad cordales , que provienen de órdenes parciales de dimensión como máximo cuatro. [ 12 ] [ 13 ]

La conjetura del grafo implícito

No todas las familias de grafos tienen estructuras locales. Para algunas familias, un argumento de conteo simple demuestra que no existen esquemas de etiquetado de adyacencia: solo se pueden usar O ( n log n ) bits para representar un grafo completo, por lo que una representación de este tipo solo puede existir cuando el número de grafos de n vértices en la familia F dada es como máximo 2 O ( n log n ) . Las familias de grafos que tienen un número mayor de grafos que este, como los grafos bipartitos o los grafos libres de triángulos , no tienen esquemas de etiquetado de adyacencia. [ 8 ] [ 10 ] Sin embargo, incluso las familias de grafos en las que el número de grafos en la familia es pequeño podrían no tener un esquema de etiquetado de adyacencia; Por ejemplo, la familia de grafos con menos aristas que vértices tiene 2 O ( n log n ) grafos de n vértices pero no tiene un esquema de etiquetado de adyacencia, porque se podría transformar cualquier grafo dado en un grafo más grande de esta familia agregando un nuevo vértice aislado por cada arista, sin cambiar su etiquetabilidad. [ 7 ] [ 10 ] Kannan et al. preguntaron si tener una caracterización de subgrafo prohibido y tener como máximo 2 O ( n log n ) grafos de n vértices son suficientes juntos para garantizar la existencia de un esquema de etiquetado de adyacencia; esta pregunta, que Spinrad reformuló como una conjetura. Trabajos recientes han refutado esta conjetura al proporcionar una familia de grafos con una caracterización de subgrafo prohibido y una tasa de crecimiento suficientemente lenta pero sin esquema de etiquetado de adyacencia. [ 14 ] Entre las familias de grafos que satisfacen las condiciones de la conjetura y para las cuales no se conoce ningún esquema de etiquetado de adyacencia se encuentran la familia de grafos de disco y los grafos de intersección de segmentos de línea.

Esquemas de etiquetado y grafos universales inducidos

Si una familia de grafos F tiene un esquema de etiquetado de adyacencia, entonces los grafos de n vértices en F pueden representarse como subgrafos inducidos de un grafo universal inducido común de tamaño polinomial, el cual consta de todos los identificadores de vértices posibles. A la inversa, si se puede construir un grafo universal inducido de este tipo, entonces las identidades de sus vértices pueden usarse como etiquetas en un esquema de etiquetado de adyacencia. [ 8 ] Para esta aplicación de representaciones implícitas de grafos, es importante que las etiquetas usen la menor cantidad de bits posible, ya que el número de bits en las etiquetas se traduce directamente en el número de vértices en el grafo universal inducido. Alstrup y Rauhe demostraron que cualquier árbol tiene un esquema de etiquetado de adyacencia con log 2 n + O ( log * n ) bits por etiqueta, de lo cual se deduce que cualquier grafo con arboricidad k tiene un esquema con k log 2 n + O ( log * n ) bits por etiqueta y un grafo universal con n k 2 O ( log * n ) vértices. En particular, los grafos planares tienen arboricidad como máximo tres, por lo que tienen grafos universales con un número de vértices casi cúbico. [ 15 ] Esta cota fue mejorada por Gavoille y Labourel, quienes demostraron que los grafos planares y las familias de grafos cerrados menores tienen un esquema de etiquetado con 2 log 2 n + O (log log n ) bits por etiqueta, y que los grafos de ancho de árbol acotado tienen un esquema de etiquetado con log 2 n + O (log log n ) bits por etiqueta. [ 16 ] La cota para grafos planares fue mejorada nuevamente por Bonamy, Gavoille y Piliczuk, quienes demostraron que los grafos planares tienen un esquema de etiquetado con (4/3+o(1))log 2 n bits por etiqueta. [ 17 ] Finalmente, Dujmović et al. demostraron que los grafos planares tienen un esquema de etiquetado con (1+o(1))log 2 n bits por etiqueta, lo que da como resultado un grafo universal con n 1+o(1) vértices. [ 18 ]

Evasividad

La conjetura de Aanderaa-Karp-Rosenberg se refiere a grafos implícitos dados como un conjunto de vértices etiquetados con una regla de caja negra para determinar si dos vértices cualesquiera son adyacentes. Esta definición difiere de un esquema de etiquetado de adyacencia en que la regla puede ser específica para un grafo en particular, en lugar de ser una regla genérica que se aplica a todos los grafos de una familia. Debido a esta diferencia, cada grafo tiene una representación implícita. Por ejemplo, la regla podría consistir en buscar el par de vértices en una matriz de adyacencia separada. Sin embargo, un algoritmo que recibe como entrada un grafo implícito de este tipo debe operar sobre él únicamente a través de la prueba de adyacencia implícita, sin referencia a cómo se implementa dicha prueba.

Una propiedad de grafo es la cuestión de si un grafo pertenece a una familia de grafos dada; la respuesta debe permanecer invariante bajo cualquier cambio de nombre de los vértices. En este contexto, la pregunta a determinar es cuántos pares de vértices deben probarse para la adyacencia, en el peor de los casos, antes de que la propiedad de interés pueda determinarse como verdadera o falsa para un grafo implícito dado. Rivest y Vuillemin demostraron que cualquier algoritmo determinista para cualquier propiedad de grafo no trivial debe probar un número cuadrático de pares de vértices. [ 19 ] La conjetura completa de Aanderaa-Karp-Rosenberg es que cualquier algoritmo determinista para una propiedad de grafo monótona (una que permanece verdadera si se agregan más aristas a un grafo con la propiedad) debe, en algunos casos, probar cada par de vértices posible. Se ha demostrado que varios casos de la conjetura son verdaderos —por ejemplo, se sabe que es verdadera para grafos con un número primo de vértices [ 20 ] —pero la conjetura completa permanece abierta. También se han estudiado variantes del problema para algoritmos aleatorios y algoritmos cuánticos.

Bender y Ron han demostrado que, en el mismo modelo utilizado para la conjetura de evasión, es posible distinguir en tiempo constante los grafos dirigidos acíclicos de los grafos que están muy lejos de ser acíclicos. Por el contrario, un tiempo tan rápido no es posible en los modelos de grafos implícitos basados ​​en vecindarios, [ 21 ]

Véase también

Referencias

  1. ↑ Korf, Richard E. (2008), "Búsqueda implícita de grafos basada en disco en tiempo lineal", Journal of the ACM , 55 (6) 26: 1– 40, doi : 10.1145/1455248.1455250 , MR 2477486 , S2CID 13969607  .
  2. ↑ Korf, Richard E. (2008), "Minimizing disk I/O in two-bit wideth-first search" (PDF) , Proc. 23rd AAAI Conf. on Artificial Intelligence , pp. 317–324 , El cubo de Rubik estándar de 3×3×3 contiene 4,3252 × 10 19 estados y es demasiado grande para buscar exhaustivamente.   
  3. ↑ Papadimitriou, Christos (1994), "Sobre la complejidad del argumento de paridad y otras pruebas ineficientes de existencia" (PDF) , Journal of Computer and System Sciences , 48 ​​(3): 498–532 , doi : 10.1016/S0022-0000(05)80063-7 , archivado del original (PDF) el 4 de marzo de 2016 , recuperado el 12 de julio de 2011.
  4. ↑ Immerman, Neil (1999), "Ejercicio 3.7 (Todo es un grafo)" , Complejidad descriptiva , Textos de posgrado en informática, Springer-Verlag, pág. 48, ISBN  978-0-387-98600-5.
  5. ↑ Yannakakis, Mihalis (2009), "Equilibrios, puntos fijos y clases de complejidad", Computer Science Review , 3 (2): 71– 85, arXiv : 0802.2831 , doi : 10.1016/j.cosrev.2009.03.004.
  6. ↑ Childs, Andrew M.; Cleve, Richard; Deotto, Enrico; Farhi, Edward; Gutmann, Sam; Spielman, Daniel A. (2003), "Aceleración algorítmica exponencial mediante un paseo cuántico", Actas del Trigésimo Quinto Simposio Anual de la ACM sobre Teoría de la Computación , Nueva York: ACM, págs. 59–68 , arXiv : quant-ph/0209131 , doi : 10.1145/780542.780552 , ISBN  1-58113-674-9, MR 2121062 , S2CID 308884  .
  7. 1 2 Muller, John Harold (1988), Estructura local en clases de grafos , tesis doctoral, Instituto Tecnológico de Georgia.
  8. 1 2 3 4 Kannan, Sampath; Naor, Moni ; Rudich, Steven (1992), "Representación implícita de grafos", SIAM Journal on Discrete Mathematics , 5 (4): 596–603 , doi : 10.1137/0405049 , MR 1186827 .
  9. ↑ Chrobak, Marek; Eppstein, David (1991), "Orientaciones planares con bajo grado de salida y compactación de matrices de adyacencia" (PDF) , Theoretical Computer Science , 86 (2): 243–266 , doi : 10.1016/0304-3975(91)90020-3.
  10. 1 2 3 Spinrad, Jeremy P. (2003), "2. Representación gráfica implícita", Representaciones gráficas eficientes , American Mathematical Soc., págs. 17–30 , ISBN  0-8218-2815-0.
  11. ↑ Kang, Ross J.; Müller, Tobias (2011), Representaciones de grafos mediante esfera y producto escalar (PDF) , archivado del original (PDF) el 16 de marzo de 2012 , consultado el 12 de julio de 2011..
  12. ↑ Ma, Tze Heng; Spinrad, Jeremy P. (1991), "Órdenes parciales sin ciclos y grafos de comparabilidad de cuerdas", Order , 8 (1): 49– 61, doi : 10.1007/BF00385814 , MR 1129614 , S2CID 120479154  .
  13. ↑ Curtis, Andrew R.; Izurieta, Clemente; Joeris, Benson; Lundberg, Scott; McConnell, Ross M. (2010), "Una representación implícita de grafos de comparabilidad cordal en tiempo lineal", Discrete Applied Mathematics , 158 (8): 869–875 , doi : 10.1016/j.dam.2010.01.005 , MR 2602811 .
  14. ^ Hatami, Hamed; Hatami, Pooya (2022), "La conjetura del gráfico implícito es falsa", 63.º Simposio anual del IEEE sobre fundamentos de la informática, FOCS 2022, Denver, CO, EE. UU., 31 de octubre al 3 de noviembre de 2022 , IEEE, págs. 1134-1137 , arXiv : 2111.13198 , doi : 10.1109/FOCS54457.2022.00109 
  15. ↑ Alstrup, Stephen; Rauhe, Theis (2002), "Grafos inducidos universales pequeños y representaciones gráficas implícitas compactas" (PDF) , Actas del 43.er Simposio Anual IEEE sobre Fundamentos de la Informática , págs. 53–62 , doi : 10.1109/SFCS.2002.1181882 , ISBN  0-7695-1822-2, S2CID 1820524 , archivado del original (PDF) el 27-09-2011 , recuperado el 13-07-2011 .
  16. ↑ Arnaud, Labourel; Gavoille, Cyril (2007), "Representación implícita más corta para grafos planares y grafos de ancho de árbol acotado" (PDF) , Actas del 15.º Simposio Europeo anual sobre algoritmos , Lecture Notes in Computer Science, vol. 4698, pp. 582–593 , doi : 10.1007/978-3-540-75520-3_52 , ISBN   978-3-540-75519-7.
  17. ↑ Bonamy, Marthe; Gavoille, Cyril; Pilipczuk, Michał (2020), "Esquemas de etiquetado más cortos para grafos planares", Actas del Simposio ACM-SIAM de 2020 sobre algoritmos discretos , págs. 446–462 , arXiv : 1908.03341 , doi : 10.1007/978-3-540-75520-3_52 .
  18. ↑ Dujmović, Vida ; Espéret, Louis; Joret, Gwenaël; Gavoille, Cyril; Micek, Piotr; Morin, Pat (2020), "Etiquetado de adyacencia para gráficos planos (y más)", 61.º Simposio anual del IEEE sobre fundamentos de la informática , págs. 577– 588, arXiv : 2003.04280 , doi : 10.1007/978-3-540-75520-3_52 .
  19. ↑ Rivest, Ronald L. ; Vuillemin, Jean (1975), "Una generalización y demostración de la conjetura de Aanderaa-Rosenberg", Actas del 7.º Simposio ACM sobre Teoría de la Computación , Albuquerque, Nuevo México, Estados Unidos, págs. 6–11 , CiteSeerX 10.1.1.309.7236 , doi : 10.1145/800116.803747 , S2CID 16220596   {{citation}}: CS1 mantenimiento: falta el editor de ubicación ( enlace ) .
  20. ↑ Kahn, Jeff; Saks, Michael ; Sturtevant, Dean (1983), "Un enfoque topológico de la evasión", Simposio sobre Fundamentos de la Informática , Los Alamitos, CA, EE. UU.: IEEE Computer Society, págs. 31–33 , doi : 10.1109/SFCS.1983.4 , ISBN  0-8186-0508-1.
  21. ↑ Bender, Michael A.; Ron, Dana (2000), "Prueba de aciclicidad de grafos dirigidos en tiempo sublineal", Autómatas, lenguajes y programación (Ginebra, 2000) , Lecture Notes in Comput. Sci., vol. 1853, Berlín: Springer, pp. 809–820 , doi : 10.1007/3-540-45022-X_68 , ISBN   978-3-540-67715-4, MR 1795937 .