En el estudio de algoritmos de gráficos , una representación gráfica implícita (o más simplemente, 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 función computable .
La noción de un 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 para cualquier vértice especificado. [1] Este tipo de representación de gráfico implícito es análoga a una lista de adyacencia , en el sentido de que proporciona un acceso fácil 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 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 ha indicado 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 grafo 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 grafo, y debe encontrarse un segundo vértice de grado impar. Por el lema del apretón de manos , existe un vértice de este tipo; 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 grafos dirigidos implícitos que ha atraído la atención en la teoría de juegos algorítmicos 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 deterministas acotadas en el espacio, 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 ) -bit), 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 polinómica). 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 los bordes 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 que son más fuertes que las separaciones 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 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 grafos, JH Muller definió una estructura local o esquema de etiquetado de adyacencia para un grafo G en una familia dada F de grafos como una 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 individual G ) que toma como entrada dos identificadores de vértice 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:
No todas las familias de grafos 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 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 dada F 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 sin 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 grafos de O ( n log n ) n -vértices pero no tiene un esquema de etiquetado de adyacencia, porque uno podría transformar cualquier grafo dado en un grafo más grande en esta familia agregando un nuevo vértice aislado para 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 grafos de O ( n log n ) n -vértices son juntos suficientes para garantizar la existencia de un esquema de etiquetado de adyacencia; esta pregunta, que Spinrad reformuló como una conjetura, permanece abierta. [8] [10] Entre las familias de grafos que satisfacen las condiciones de la conjetura y para las cuales no hay un esquema de etiquetado de adyacencia conocido están la familia de grafos de disco y grafos de intersección de segmentos de línea.
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, consistiendo el grafo en todos los identificadores de vértices posibles. Por el contrario, 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 de grafos implícitos, es importante que las etiquetas usen la menor cantidad de bits posible, porque la cantidad de bits en las etiquetas se traduce directamente en la cantidad 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 que 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 casi cúbico de vértices. [14] Este límite fue mejorado por Gavoille y Labourel, quienes demostraron que los grafos planares y las familias de grafos menores cerrados 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. [15] El límite para los grafos planares fue mejorado 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. [16] 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 un grafo universal con n 1+o(1) vértices. [17]
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 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 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 grafo implícito de este tipo debe operar sobre él solo a través de la prueba de adyacencia implícita, sin referencia a cómo se implementa la prueba.
Una propiedad de grafo es la cuestión de si un grafo pertenece a una familia dada de grafos; la respuesta debe permanecer invariable 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 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. [18] La conjetura completa de Aanderaa–Karp–Rosenberg es que cualquier algoritmo determinista para una propiedad de grafo monótona (una que sigue siendo verdadera si se agregan más aristas a un grafo con la propiedad) debe, en algunos casos, probar cada par posible de vértices. 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 [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 evasividad, es posible distinguir en tiempo constante los grafos acíclicos dirigidos 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 vecindades [20] .
El cubo de Rubik 3×3×3 estándar contiene 4,3252 × 10
19
estados y es demasiado grande para realizar una búsqueda exhaustiva.
{{citation}}: Mantenimiento de CS1: falta la ubicación del editor ( enlace ).