En el estudio de los algoritmos de gráficos , una representación gráfica implícita (o más simplemente un gráfico implícito ) es un gráfico cuyos vértices o aristas no se representan 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 computadora computable. función .
La noción de gráfico implícito es común en varios algoritmos de búsqueda que se describen en términos de gráficos. En este contexto, un gráfico 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 gráfica implícita es análoga a una lista de adyacencia , en el sentido de que proporciona fácil acceso a los vecinos de cada vértice. Por ejemplo, al buscar una solución a un rompecabezas como el cubo de Rubik , se puede definir un gráfico implícito en el que cada vértice represente uno de los posibles estados del cubo y cada arista represente 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 gráficos implícitos, definidos como anteriormente mediante una regla o algoritmo para enumerar los vecinos de un vértice. Por ejemplo, PPA es la clase de problemas en los que se da como entrada un gráfico implícito no dirigido (en el que los vértices son cadenas binarias de n bits, con un algoritmo de tiempo polinomial para enumerar los vecinos de cualquier vértice) y un vértice de grado impar. en el gráfico, y debe encontrar un segundo vértice de grado impar. Según el lema del apretón de manos , tal vértice existe; encontrar uno es un problema en NP , pero los problemas que se pueden definir de esta manera pueden no ser necesariamente NP-completos , ya que se desconoce si PPA = NP. PPAD es una clase análoga definida en gráficos dirigidos implícitos que ha atraído la atención en la teoría algorítmica de juegos porque contiene el problema de calcular un equilibrio de Nash . [3] El problema de probar la accesibilidad de un vértice a otro en un gráfico implícito también se puede utilizar para caracterizar clases de complejidad no deterministas limitadas por el espacio, incluido NL (la clase de problemas que puede caracterizarse por la accesibilidad en gráficos dirigidos implícitos cuyos vértices son O (log n ) cadenas de bits de bits), SL (la clase análoga para gráficos no dirigidos) y PSPACE (la clase de problemas que pueden caracterizarse por la accesibilidad en gráficos implícitos con cadenas de bits de longitud polinomial). En este contexto de teoría de la complejidad, los vértices de un gráfico implícito pueden representar los estados de una máquina de Turing no determinista , y los bordes pueden representar posibles transiciones de estado, pero los gráficos 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 gráfico implícito. [5]
Los modelos de gráficos implícitos también se han utilizado como una forma de relativización para demostrar separaciones entre clases de complejidad que son más fuertes que las separaciones conocidas para modelos no relativizados. Por ejemplo, Childs et al. utilizó representaciones de vecindad de gráficos implícitos para definir un problema de recorrido de gráficos que se puede resolver en tiempo polinomial en una computadora cuántica pero que requiere tiempo exponencial para resolverse en cualquier computadora clásica. [6]
En el contexto de representaciones eficientes de gráficos, JH Muller definió una estructura local o esquema de etiquetado de adyacencia para un gráfico G en una familia F dada de gráficos como una asignación de un identificador de bits O (log n ) a cada vértice de G. junto con un algoritmo (que puede depender de F pero es independiente del gráfico individual G ) que toma como entrada dos identificadores de vértices y determina si son o no los puntos finales de una arista en G . Es decir, este tipo de representación implícita es análoga a una matriz de adyacencia : es sencillo verificar si dos vértices son adyacentes, pero encontrar los vecinos de cualquier vértice puede implicar recorrer todos los vértices y probar cuáles son vecinos. [7]
Las familias de gráficos con esquemas de etiquetado de adyacencia incluyen:
¿Tiene cada familia hereditaria de grafos de crecimiento lento una representación implícita?
No todas las familias de gráficos tienen estructuras locales. Para algunas familias, un simple argumento de conteo demuestra que los esquemas de etiquetado de adyacencia no existen: solo se pueden usar O ( n log n ) bits para representar un gráfico completo, por lo que una representación de este tipo solo puede existir cuando el número de n -vértices Los gráficos de la familia dada F son como máximo 2 O ( n log n ) . Las familias de gráficos que tienen un número mayor de gráficos que este, como los gráficos bipartitos o los gráficos sin triángulos , no tienen esquemas de etiquetado de adyacencia. [8] [10] Sin embargo, incluso las familias de gráficos en las que el número de gráficos en la familia es pequeña podrían no tener un esquema de etiquetado de adyacencia; por ejemplo, la familia de gráficos con menos aristas que vértices tiene 2 O ( n log n ) n -gráficos de vértices pero no tiene un esquema de etiquetado de adyacencia, porque se podría transformar cualquier gráfico dado en un gráfico más grande en esta familia agregando un nuevo vértice aislado para cada arista, sin cambiar su etiquetabilidad. [7] [10] Kannan et al. se preguntó si tener una caracterización de subgrafo prohibida y tener como máximo 2 gráficos O ( n log n ) n -vértices son suficientes juntos para garantizar la existencia de un esquema de etiquetado de adyacencia; Esta cuestión, que Spinrad reiteró como una conjetura, sigue abierta. [8] [10] Entre las familias de gráficos 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 gráficos de disco y los gráficos de intersección de segmentos de línea.
Si una familia de gráficos F tiene un esquema de etiquetado de adyacencia, entonces los gráficos de n -vértices en F pueden representarse como subgrafos inducidos de un gráfico universal inducido común de tamaño polinómico, el gráfico que consta de todos los identificadores de vértices posibles. Por el contrario, si se puede construir un gráfico 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 gráficas implícitas, es importante que las etiquetas utilicen la menor cantidad de bits posible, porque el número de bits en las etiquetas se traduce directamente en el número de vértices en el gráfico 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 que se deduce que cualquier gráfico con arboricidad k tiene un esquema con k log 2 n + O ( log * n ) bits por etiqueta y un gráfico universal con n k 2 O ( log * n ) vértices. En particular, los gráficos planos tienen arboricidad como máximo tres, por lo que tienen gráficos universales con un número casi cúbico de vértices. [14] Este límite fue mejorado por Gavoille y Labourel, quienes demostraron que los gráficos planos y las familias de gráficos menores cerrados tienen un esquema de etiquetado con 2 log 2 n + O (log log n ) bits por etiqueta, y que los gráficos de ancho de árbol acotado tienen un esquema de etiquetado con log 2 n + O (log log n ) bits por etiqueta. [15] Bonamy, Gavoille y Piliczuk mejoraron nuevamente el límite para los gráficos planos, quienes demostraron que los gráficos planos tienen un esquema de etiquetado con (4/3+o(1))log 2 n bits por etiqueta. [16] Finalmente, Dujmović et al demostraron que los gráficos planos tienen un esquema de etiquetado con (1+o(1))log 2 n bits por etiqueta, lo que da un gráfico universal con n 1+o(1) vértices. [17]
La conjetura de Aanderaa-Karp-Rosenberg se refiere a gráficos implícitos dados como un conjunto de vértices etiquetados con una regla de caja negra para determinar si dos vértices son adyacentes. Esta definición difiere de un esquema de etiquetado de adyacencia en que la regla puede ser específica de un gráfico en particular en lugar de ser una regla genérica que se aplica a todos los gráficos de una familia. Debido a esta diferencia, cada gráfico tiene una representación implícita. Por ejemplo, la regla podría ser buscar el par de vértices en una matriz de adyacencia separada. Sin embargo, un algoritmo al que se le da como entrada un gráfico implícito de este tipo debe operar sobre él sólo a través de la prueba de adyacencia implícita, sin referencia a cómo se implementa la prueba.
Una propiedad de gráfico es la cuestión de si un gráfico pertenece a una familia de gráficos determinada; la respuesta debe permanecer invariante bajo cualquier reetiquetado de los vértices. En este contexto, la cuestión a determinar es cuántos pares de vértices deben probarse para determinar su adyacencia, en el peor de los casos, antes de que se pueda determinar si la propiedad de interés es verdadera o falsa para un gráfico implícito dado. Rivest y Vuillemin demostraron que cualquier algoritmo determinista para cualquier propiedad de un gráfico no trivial debe probar un número cuadrático de pares de vértices. [18] La conjetura completa de Aanderaa-Karp-Rosenberg es que cualquier algoritmo determinista para una propiedad de gráfico monótono (uno que sigue siendo cierto si se agregan más aristas a un gráfico con la propiedad) debe en algunos casos probar todos los pares posibles de vértices. Se ha demostrado que la conjetura es cierta en varios casos (por ejemplo, se sabe que es cierta para gráficos con un número primo de vértices [19] ), 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 la evasión, es posible distinguir en tiempo constante únicamente grafos acíclicos dirigidos de grafos que están muy lejos de ser acíclicos. Por el contrario, un tiempo tan rápido no es posible en modelos de gráficos implícitos basados en vecindad, [20]
El cubo de Rubik estándar de 3 × 3 × 3 contiene 4,3252 × 10
19
estados y es demasiado grande para realizar una búsqueda exhaustiva.
{{citation}}: Mantenimiento CS1: falta el editor de la ubicación ( enlace ).