En la disciplina matemática de la teoría de grafos , un conjunto de vértices de retroalimentación de un gráfico es un conjunto de vértices cuya eliminación deja un gráfico sin ciclos . En otras palabras, cada conjunto de vértices de retroalimentación contiene al menos un vértice de cualquier ciclo en el gráfico. El problema del conjunto de vértices de retroalimentación es un problema NP-completo en la teoría de la complejidad computacional . Fue uno de los primeros problemas que se demostró que era NP completo . Tiene amplias aplicaciones en sistemas operativos , sistemas de bases de datos y diseño de chips VLSI .
Definición [ editar ]
- INSTANCIA: An (no dirigida o dirigida) gráfico y un entero positivo .
- PREGUNTA: ¿Hay un subconjunto? con tal que con los vértices de eliminado es libre de ciclo ?
La gráfica que queda después de quitar desde es un bosque inducido (resp. un gráfico acíclico dirigido inducido en el caso de gráficos dirigidos ). Por lo tanto, encontrar un vértice de retroalimentación mínimo establecido en un gráfico es equivalente a encontrar un bosque inducido máximo (resp. Gráfico acíclico dirigido inducido máximo en el caso de gráficos dirigidos ).
![G [V \ setminus X]](https://wikimedia.org/api/rest_v1/media/math/render/svg/1166277c8d75dce9d8ea1f3ede58bd79c083211d)
NP-dureza [ editar ]
Karp (1972) demostró que el problema del conjunto de vértices de retroalimentación para gráficos dirigidos es NP-completo . El problema sigue siendo NP completo en gráficos dirigidos con máximo en grado y fuera de grado dos, y en gráficos planos dirigidos con máximo grado en grado y fuera de grado tres. [1] La reducción de Karp también implica la completitud NP del problema del conjunto de vértices de retroalimentación en gráficos no dirigidos, donde el problema se mantiene NP-duro en gráficos de grado máximo cuatro. El problema del conjunto de vértices de retroalimentación se puede resolver en tiempo polinómico en gráficos de grado máximo como máximo tres. [2]
Tenga en cuenta que el problema de eliminar la menor cantidad de bordes posible para que el gráfico no tenga ciclos es equivalente a encontrar un árbol de expansión , lo que se puede hacer en tiempo polinómico . Por el contrario, el problema de eliminar bordes de un gráfico dirigido para hacerlo acíclico , el problema del conjunto de arco de retroalimentación , es NP-completo. [3]
Algoritmos exactos [ editar ]
El problema de optimización de NP correspondiente de encontrar el tamaño de un conjunto mínimo de vértices de retroalimentación se puede resolver en el tiempo O (1.7347 n ), donde n es el número de vértices en el gráfico. [4] Este algoritmo realmente calcula un bosque inducido máximo, y cuando se obtiene dicho bosque, su complemento es un conjunto de vértices de retroalimentación mínimo. El número de conjuntos mínimos de vértices de retroalimentación en un gráfico está limitado por O (1.8638 n ). [5] El problema del conjunto de vértices de retroalimentación dirigida aún se puede resolver en el tiempo O * (1.9977 n ), donde n es el número de vértices en el gráfico dirigido dado.[6] Las versiones parametrizadas de los problemas dirigidos y no dirigidos son manejables con parámetros fijos . [7]
En gráficos no dirigidos de grado máximo tres, el problema del conjunto de vértices de retroalimentación puede resolverse en tiempo polinómico , transformándolo en una instancia del problema de paridad matroide para matroides lineales . [8]
Aproximación [ editar ]
El problema no dirigido es APX-complete , que se deriva directamente de la integridad de APX del problema de la cubierta del vértice , [9] , la existencia de una aproximación que preserva la reducción de L del problema de la cubierta del vértice y los algoritmos de aproximación existentes. [3] El algoritmo de aproximación más conocido en gráficos no dirigidos es por un factor de dos. [10] Si la versión dirigida es un tiempo polinómico aproximado dentro de una relación constante y, por lo tanto, APX-complete es una pregunta abierta.
Límites [ editar ]
De acuerdo con el teorema de Erd –s-Pósa , el tamaño de un conjunto mínimo de vértices de retroalimentación está dentro de un factor logarítmico del número máximo de ciclos de vértices disjuntos en el gráfico dado. [11]
Aplicaciones [ editar ]
En los sistemas operativos , los conjuntos de vértices de retroalimentación juegan un papel destacado en el estudio de la recuperación de punto muerto . En el gráfico de espera de un sistema operativo, cada ciclo dirigido corresponde a una situación de punto muerto. Para resolver todos los puntos muertos, algunos procesos bloqueados tienen que ser abortados. Un vértice de retroalimentación mínimo establecido en este gráfico corresponde a un número mínimo de procesos que uno necesita abortar. [12]
Además, el problema del conjunto de vértices de retroalimentación tiene aplicaciones en el diseño de chips VLSI .
En la teoría de gráficos , un gráfico dirigido puede contener ciclos dirigidos , un bucle de aristas unidireccional. En algunas aplicaciones, dichos ciclos no son deseables, y deseamos eliminarlos y obtener un gráfico acíclico dirigido (DAG). Una forma de hacer esto es simplemente soltar los bordes del gráfico para romper los ciclos. Un conjunto de arco de retroalimentación ( FAS ) o conjunto de bordes de retroalimentación es un conjunto de bordes que, cuando se eliminan del gráfico, dejan un DAG. Dicho de otra manera, es un conjunto que contiene al menos un borde de cada ciclo en el gráfico.
Estrechamente relacionado están el conjunto de vértices de retroalimentación , que es un conjunto de vértices que contiene al menos un vértice de cada ciclo en el gráfico dirigido, y el árbol de expansión mínima , que es la variante no dirigida del problema del conjunto de arco de retroalimentación.
Un conjunto de arco de retroalimentación mínimo (uno que no puede reducirse en tamaño eliminando bordes) tiene la propiedad adicional de que, si los bordes están invertidos en lugar de eliminarse, el gráfico permanece acíclico. Encontrar un pequeño conjunto de bordes con esta propiedad es un paso clave en el dibujo de gráficos en capas . [1] [2]
A veces es deseable dejar el menor número de bordes como sea posible, la obtención de un conjunto de arco de realimentación mínimo (MFAS), o dualmente un subgrafo máximo acíclico . Este es un problema informático difícil, para el cual se han ideado varias soluciones aproximadas.
Ejemplo [ editar ]
Como un ejemplo simple, considere la siguiente situación hipotética, donde para lograr algo, ciertas cosas deben lograrse antes que otras:
- Tu objetivo es conseguir el cortacésped.
- George dice que te dará un piano, pero solo a cambio de una cortadora de césped.
- Harry dice que te dará una cortadora de césped, pero solo a cambio de un microondas.
- Jane dice que te dará un microondas, pero solo a cambio de un piano.
Podemos expresar esto como un problema gráfico. Deje que cada vértice represente un elemento y agregue un borde de A a B si debe tener A para obtener B. Desafortunadamente, no tiene ninguno de los tres elementos, y debido a que este gráfico es cíclico, no puede obtener ninguno. de ellos tampoco.
Sin embargo, suponga que le ofrece a George $ 100 por su piano. Si él acepta, esto efectivamente elimina el borde del cortacésped al piano, porque ya no necesita el cortacésped para obtener el piano. En consecuencia, el ciclo se rompe y puede cambiar dos veces para obtener el cortacésped. Este borde constituye un conjunto de arco de retroalimentación.
Conjunto de arco de retroalimentación mínimo [ editar ]
Como en el ejemplo anterior, generalmente hay algún costo asociado con la eliminación de un borde. Por esta razón, nos gustaría eliminar la menor cantidad de bordes posible. Eliminar un borde es suficiente en un ciclo simple, pero en general determinar el número mínimo de bordes para eliminar es un problema difícil de NP llamado el conjunto de arco de retroalimentación mínimo o problema de subgrafo acíclico máximo.
Resultados teóricos [ editar ]
Este problema es particularmente difícil en los gráficos de k -edge-conectado para k grande , donde cada borde cae en muchos ciclos diferentes. La versión de decisión del problema, que es NP-complete , pregunta si todos los ciclos pueden romperse eliminando como máximo k bordes; Este fue uno de los 21 problemas NP-completos de Richard M. Karp , que se muestra al reducir el problema de la cubierta del vértice . [3] [4]
Aunque NP-complete, el problema del conjunto de arco de retroalimentación es manejable con parámetros fijos : existe un algoritmo para resolverlo cuyo tiempo de ejecución es un polinomio fijo en el tamaño del gráfico de entrada (independiente del número de bordes en el conjunto) pero exponencial en el número de aristas en el conjunto de arco de retroalimentación. [5] Alternativamente, un algoritmo manejable de parámetro fijo es dado por una técnica de programación dinámica que depende solo exponencialmente de la dimensión del espacio del ciclo del gráfico. [6]
El problema del conjunto de arco de retroalimentación mínimo es APX-hard , lo que significa que (suponiendo P ≠ NP ) hay un límite estricto en su calidad de aproximación, una constante c > 1 tal que cada algoritmo de aproximación de tiempo polinomial a veces devolverá un conjunto de bordes más grande que c veces el tamaño óptimo. La prueba implica reducciones de preservación de aproximación desde la cubierta del vértice al conjunto de vértices de retroalimentación , y desde el conjunto de vértices de retroalimentación al conjunto de arco de retroalimentación. [7] [8] [9]Más específicamente, debido a que la cubierta del vértice no tiene una aproximación mejor que 1.3606 a menos que P ≠ NP, lo mismo es cierto para el conjunto de arco de retroalimentación. Es decir, es posible tomar c = 1.3606 . [10] Si la conjetura de los juegos únicos es cierta, este umbral de inaproximabilidad podría aumentarse de manera arbitraria a cerca de 2. [11]
Por otro lado, el algoritmo de aproximación más conocido tiene la relación de aproximación no constante O (log n log log n ). [9] [12] Para el doble problema, de aproximar el número máximo de aristas en un subgrafo acíclico, es posible una aproximación algo mejor que 1/2. [13] [14] Determinar si el conjunto de arco de retroalimentación tiene un algoritmo de aproximación de relación constante, o si es necesaria una relación no constante, sigue siendo un problema abierto.
 | Problema no resuelto en matemáticas :
¿El problema del conjunto de arco de retroalimentación tiene un algoritmo de aproximación con una relación de aproximación constante?
(Más problemas no resueltos en matemáticas) |
Si los dígrafos de entrada están restringidos a torneos , el problema resultante se conoce como el problema de conjunto de arco de retroalimentación mínimo en los torneos (FAST). Este problema restringido admite un esquema de aproximación de tiempo polinomial , y esto aún es válido para una versión ponderada restringida del problema. [15] Karpinski & Schudy (2010) proporcionó un algoritmo subexponencial de parámetros fijos para el FAST ponderado . [dieciséis]
Por otro lado, si los bordes no están dirigidos , el problema de eliminar bordes para hacer que el gráfico esté libre de ciclos es equivalente a encontrar un árbol de expansión mínimo , que se puede hacer fácilmente en tiempo polinómico.
Aproximaciones [ editar ]
Se han desarrollado varios algoritmos de aproximación para el problema [17] , incluido el algoritmo aleatorio de Monte Carlo que resuelve el problema en tiempo polinómico con probabilidad arbitraria . [18] Un algoritmo particularmente simple es el siguiente:
- Arreglar una permutación arbitraria de los vértices; es decir, etiquete los vértices de 1 a n , eligiendo arbitrariamente qué vértice se le dará a cada etiqueta.
- Construya dos subgrafos L y R , que contengan los bordes ( u , v ) donde u < v , y aquellos donde u > v , respectivamente.
Ahora, tanto L como R son subgrafías acíclicas de G , y al menos una de ellas tiene al menos la mitad del tamaño de la subgrafía acíclica máxima.
En el campo matemático de la teoría de grafos , un homomorfismo de grafos es un mapeo entre dos gráficos que respeta su estructura. Más concretamente, es una función entre los conjuntos de vértices de dos gráficos que mapea vértices adyacentes a vértices adyacentes.
Los homomorfismos generalizan varias nociones de colores de gráficos y permiten la expresión de una clase importante de problemas de satisfacción de restricciones , como ciertos problemas de programación o asignación de frecuencias . [1] El hecho de que homomorfismos pueden conduce a estructuras algebraicas ricos compuestas: una orden previo en los gráficos, un retículo distributivo , y una categoría (uno para gráficos no dirigidos y uno para gráficos dirigidos). [2] La complejidad computacional de encontrar un homomorfismo entre gráficos dados es prohibitiva en general, pero se sabe mucho sobre casos especiales que se pueden resolver entiempo polinómico . Los límites entre los casos tratables y los intratables han sido un área activa de investigación.
Definiciones [ editar ]
En este artículo, a menos que se indique lo contrario, los gráficos son gráficos finitos, no dirigidos con bucles permitidos, pero no se permiten múltiples bordes (bordes paralelos). Un homomorfismo gráfico [4] f partir de un gráfico G = ( V ( G ), E ( G )) a una gráfica H = ( V ( H ), E ( H )), escrito
- f : G → H
es una función de V ( G ) a V ( H ) que mapea puntos finales de cada borde en G a los puntos finales de una ventaja en H . Formalmente, { u , v } ∈ E ( G ) implica { f ( u ), f ( v )} ∈ E ( H ), para todos los pares de vértices u , v en V ( G ). Si existe algún homomorfismo de G a H , entonces Gse dice que es homomórfico a H o H -colorable . Esto a menudo se denota simplemente:
- G → H .
La definición anterior se extiende a grafos dirigidos. Entonces, para un homomorfismo f : G → H , ( f ( u ), f ( v )) es un arco (borde dirigido) de H siempre que ( u , v ) es un arco de G .
Hay una inyectiva homomorfismo de G a H (es decir, uno que nunca mapas de vértices distintos a un vértice) si y sólo si G es un subgrafo de H . Si un homomorfismo f : G → H es una biyección (una correspondencia uno a uno entre los vértices de G y H ) cuya función inversa es también un homomorfismo gráfico, entonces f es un isomorfismo gráfico . [5]
Los mapas de cobertura son un tipo especial de homomorfismos que reflejan la definición y muchas propiedades de los mapas de cobertura en topología . [6] Se definen como homomorfismos sobreyectivos (es decir, algo que se asigna a cada vértice) que también son localmente biyectivos, es decir, una biyección en la vecindad de cada vértice. Un ejemplo es la doble cubierta bipartita , formada a partir de un gráfico dividiendo cada vértice v en v 0 y v 1 y reemplazando cada borde u , v con los bordes u 0 , v 1 yv 0 , u 1 . La función de mapeo v 0 y v 1 en la cubierta a v en el gráfico original es un homomorfismo y un mapa de cobertura.
Gráfico homeomorfismo es una noción diferente, no relacionados directamente con homomorfismos. En términos generales, requiere inyectividad, pero permite mapear los bordes a los caminos (no solo a los bordes). Los menores gráficos son una noción aún más relajada.
Núcleos y retracciones [ editar ]
Dos gráficos G y H son homomorphically equivalente si G → H y H → G . [4] Los mapas no son necesariamente sobreyectivos ni inyectivos. Por ejemplo, los gráficos bipartitos completos K 2,2 y K 3,3 son homomórficamente equivalentes: cada mapa se puede definir como tomar la mitad izquierda (resp. Derecha) del gráfico de dominio y mapear a un solo vértice a la izquierda (resp. derecha) la mitad del gráfico de la imagen.
A la retracción es un homomorfismo r de una gráfica G a un subgrafo H de G tal que r ( v ) = v para cada vértice v de H . En este caso el subgrafo H se llama una retracción de G . [7]
Un núcleo es un gráfico sin homomorfismo a cualquier subgrafo adecuada. De manera equivalente, un núcleo puede definirse como un gráfico que no se retrae a ningún subgráfico apropiado. [8] Cada gráfico G es homomorphically equivalente a un núcleo único (hasta el isomorfismo), llamado el núcleo de G . [9] En particular, esto no es cierto en general para grafos infinitos. [10] Sin embargo, las mismas definiciones se aplican a los gráficos dirigidos y un gráfico dirigido también es equivalente a un núcleo único. Cada gráfico y cada gráfico dirigido contiene su núcleo como retracción y como subgrafo inducido . [7]
Por ejemplo, todos los gráficos completos K n y todos los ciclos impares ( gráficos de ciclo de longitud impar) son núcleos. Cada gráfico G de 3 colores que contiene un triángulo (es decir, tiene el gráfico completo K 3 como un subgráfico) es homomórficamente equivalente a K 3 . Esto se debe a que, por un lado, una coloración 3 de G es lo mismo que un homomorfismo G → K 3 , como se explica a continuación. Por otro lado, cada subgrafo de G admite trivialmente un homomorfismo en G , lo que implica K 3 → G . Esto también significa que K 3 es el núcleo de cualquier gráfico G . Del mismo modo, cada gráfico bipartito que tiene al menos un borde es equivalente a K 2 . [11]
Conexión a colorantes [ editar ]
Una coloración k , para algunos enteros k , es una asignación de uno de los k colores a cada vértice de un gráfico G de manera que los puntos finales de cada borde obtienen colores diferentes. Los colores k de G corresponden exactamente a los homomorfismos de G al gráfico completo K k . [12] De hecho, los vértices de K k corresponden a los k colores, y dos colores son adyacentes como vértices de K k si y solo si son diferentes. Por lo tanto, una función define un homomorfismo a K ksi y sólo si los mapas de vértices adyacentes de G a diferentes colores (es decir, es un k -Coloreado). En particular, G es k -colorable si y sólo si es K k -colorable. [12]
Si hay dos homomorfismos G → H y H → K k , entonces su composición G → K k es también un homomorfismo. [13] En otras palabras, si un gráfico H puede ser coloreado con k colores, y hay un homomorfismo de G a H , entonces G también puede ser k- coloreado. Por lo tanto, G → H implica χ ( G ) ≤ χ ( H ), donde χ denota el número cromáticade un gráfico (el menor k para el cual es k -colorable). [14]
Variantes [ editar ]
Los homomorfismos generales también pueden considerarse como una especie de coloración: si los vértices de un gráfico fijo H son los colores disponibles y los bordes de H describen qué colores son compatibles , entonces un color H de G es una asignación de colores a vértices de G tal que los vértices adyacentes obtengan colores compatibles. Muchas nociones de coloración de gráficos se ajustan a este patrón y se pueden expresar como homomorfismos de gráficos en diferentes familias de gráficos. Los colores circulares se pueden definir usando homomorfismos en gráficos circulares completos , refinando la noción habitual de colores. [15] Fraccionaly la coloración del doble b se puede definir usando homomorfismos en gráficos Kneser . [16] Los colores T corresponden a homomorfismos en ciertos gráficos infinitos. [17] Una coloración orientada de un gráfico dirigido es un homomorfismo en cualquier gráfico orientado . [18] Una coloración L (2,1) es un homomorfismo en el complemento del gráfico de ruta que es localmente inyectivo, lo que significa que se requiere que sea inyectivo en la vecindad de cada vértice. [19]
Orientaciones sin caminos largos [ editar ]
Otra conexión interesante se refiere a las orientaciones de los gráficos. Una orientación de un gráfico G no dirigido es cualquier gráfico dirigido obtenido al elegir una de las dos orientaciones posibles para cada borde. Un ejemplo de una orientación de la gráfica completa K k es el transitivo torneo T → k con vértices 1,2, ..., k y arcos de i a j siempre que i < j . Un homomorfismo entre las orientaciones de gráficos G y H se obtiene un homomorfismo entre los gráficos no dirigidos G y H, simplemente haciendo caso omiso de las orientaciones. Por otro lado, dado un homomorfismo G → H entre gráficos no dirigidos, cualquier orientación H → de H puede retroceder a una orientación G → de G para que G → tenga un homomorfismo a H → . Por lo tanto, un gráfico G es k -colorable (tiene un homomorfismo de K k ) si y sólo si alguna orientación de G tiene un homomorfismo de T → k . [20]
Un teorema del folklore establece que para todo k , un gráfico dirigido G tiene un homomorfismo a T → k si y solo si no admite homomorfismo del camino dirigido P → k +1 . [21] Aquí P → n es el gráfico dirigido con vértices 1, 2, ..., n y bordes de i a i + 1, para i = 1, 2, ..., n - 1. Por lo tanto, un gráfico es k -colorable si y solo si tiene una orientación que no admite homomorfismo de P → k +1. Esta afirmación puede fortalecerse ligeramente para decir que una gráfica es k -colorable si y solo si alguna orientación no contiene una ruta dirigida de longitud k (no P → k +1 como un subgrafo). Este es el teorema de Gallai – Hasse – Roy – Vitaver .
La conexión a problemas de satisfacción de restricciones [ editar ]
Ejemplos [ editar ]
Algunos problemas de programación se pueden modelar como una pregunta sobre la búsqueda de homomorfismos gráficos. [22] [23] Como ejemplo, uno podría querer asignar cursos de taller a franjas horarias en un calendario para que dos cursos atendidos por el mismo estudiante no estén demasiado cerca el uno del otro en el tiempo. Los cursos forman un gráfico G , con una ventaja entre dos cursos a los que asiste algún estudiante común. Las franjas horarias forman un gráfico H , con un borde entre dos ranuras que están lo suficientemente distantes en el tiempo. Por ejemplo, si uno quiere un horario cíclico semanal, de modo que cada estudiante obtenga sus cursos de taller en días no consecutivos, entonces H sería el gráfico complementario de C 7. Un gráfico de homomorfismo de G a H es un cronograma que asigna cursos a franjas horarias, como se especifica. [22] Para añadir un requisito diciendo que, por ejemplo, ningún estudiante solo tiene cursos en tanto el viernes y el lunes, es suficiente para eliminar el borde correspondiente de H .
Un problema simple de asignación de frecuencia se puede especificar de la siguiente manera: varios transmisores en una red inalámbrica deben elegir un canal de frecuencia en el cual transmitirán datos. Para evitar interferencias , los transmisores que están geográficamente cercanos deben usar canales con frecuencias muy alejadas. Si esta condición se aproxima con un umbral único para definir 'geográficamente cercano' y 'muy separado', entonces una elección de canal válida corresponde nuevamente a un homomorfismo gráfico. Debe ir desde la gráfica de los transmisores G , con bordes entre pares que están geográficamente cercanos, hasta la gráfica de los canales H, con bordes entre canales que están muy separados. Si bien este modelo es más bien simplificada, lo hace admitir cierta flexibilidad: pares de transmisores que no están cerca, pero podría interferir debido a características geográficas puede añadido a los bordes de G . Aquellos que no se comunican al mismo tiempo pueden ser eliminados. Del mismo modo, los pares de canales que están muy separados, pero exhiben armónico interferencias pueden eliminarse del conjunto borde de H . [24]
En cada caso, estos modelos simplificados muestran muchos de los problemas que deben manejarse en la práctica. [25] Los problemas de satisfacción de restricciones , que generalizan los problemas de homomorfismo gráfico, pueden expresar varios tipos adicionales de condiciones (como preferencias individuales o límites en el número de tareas coincidentes). Esto permite que los modelos sean más realistas y prácticos.
Vista formal [ editar ]
Los gráficos y los gráficos dirigidos se pueden ver como un caso especial de la noción mucho más general llamada estructuras relacionales (definidas como un conjunto con una tupla de relaciones). Los gráficos dirigidos son estructuras con una única relación binaria (adyacencia) en el dominio (el conjunto de vértices). [26] [3] Según esta visión, los homomorfismos de tales estructuras son exactamente homomorfismos gráficos. En general, la cuestión de encontrar un homomorfismo de una estructura relacional a otra es un problema de satisfacción de restricciones (CSP). El caso de los gráficos proporciona un primer paso concreto que ayuda a comprender los CSP más complicados. Muchos métodos algorítmicos para encontrar homomorfismos de gráficos, como el retroceso ,La propagación de restricciones y la búsqueda local se aplican a todos los CSP. [3]
Para los gráficos G y H , la cuestión de si G tiene un homomorfismo a H corresponde a una instancia de CSP con sólo un tipo de restricción, [3] como sigue. Las variables de son los vértices de G y el dominio para cada variable es el conjunto de vértices de H . Una evaluación es una función que asigna a cada variable un elemento del dominio, por lo tanto, una función f de V ( G ) a V ( H ). Cada borde o arco ( u , v ) de Gentonces corresponde a la restricción (( u , v ), E ( H )). Esta es una limitación que expresa que la evaluación debe asignar el arco ( u , v ) a un par ( f ( u ), f ( v )) que está en la relación E ( H ), es decir, a un arco de H . Una solución a la CSP es una evaluación que respete todas las restricciones, por lo que es exactamente un homomorfismo de G a H .
Estructura de los homomorfismos [ editar ]
Las composiciones de homomorfismos son homomorfismos. [13] En particular, la relación → en los gráficos es transitiva (y reflexiva, trivial), por lo que es un pedido anticipado en los gráficos. [27] Sea la clase de equivalencia de un gráfico G bajo equivalencia homomórfica ser [ G ]. La clase de equivalencia también puede ser representada por el núcleo único en [ G ]. La relación → es un orden parcial en esas clases de equivalencia; define un poset . [28]
Deje G < H significan que hay un homomorfismo de G a H , pero no homomorfismo de H a G . La relación → es un orden denso , lo que significa que para todos los gráficos (no dirigidos) G , H tales que G < H , hay un gráfico K tal que G < K < H (esto se cumple a excepción de los casos triviales G = K 0 o K 1 ). [29] [30] Por ejemplo, entre dos gráficos completos (excepto K 0 , K 1 ) hay infinitos gráficos circulares completos , correspondientes a números racionales entre números naturales. [31]
El conjunto de clases de equivalencia de gráficos bajo homomorfismos es una red distributiva , con la unión de [ G ] y [ H ] definida como (la clase de equivalencia de) la unión disjunta [ G ∪ H ], y el encuentro de [ G ] y [ H ] definido como el producto tensor [ G × H ] (la elección de los gráficos G y H que representan las clases de equivalencia [ G ] y [ H ] no importa). [32] La unión irreducibleLos elementos de esta red son gráficos conectados exactamente . Esto se puede mostrar usando el hecho de que un homomorfismo mapea un gráfico conectado en un componente conectado del gráfico objetivo. [33] [34] Los elementos irreductibles de este enrejado son exactamente los gráficos multiplicativos . Estas son las gráficas K de tal manera que un producto G × H tiene un homomorfismo con K solo cuando uno de G o H también lo tiene. Identificar gráficos multiplicativos se encuentra en el corazón de la conjetura de Hedetniemi . [35] [36]
Los homomorfismos gráficos también forman una categoría , con gráficos como objetos y homomorfismos como flechas. [37] El objeto inicial es el gráfico vacío, mientras que el objeto terminal es el gráfico con un vértice y un bucle en ese vértice. El producto tensorial de los gráficos es el producto teórico de categoría y el gráfico exponencial es el objeto exponencial para esta categoría. [36] [38] Desde estas dos operaciones siempre se definen, la categoría de los gráficos es una categoría cerrada cartesiano. Por la misma razón, la red de clases de equivalencia de gráficos bajo homomorfismos es, de hecho, un álgebra de Heyting . [36] [38]
Para los gráficos dirigidos se aplican las mismas definiciones. En particular → es un orden parcial en clases de equivalencia de gráficos dirigidos. Es distinto del orden → en clases de equivalencia de gráficos no dirigidos, pero lo contiene como un suborden. Esto se debe a que cada gráfico no dirigido puede considerarse como un gráfico dirigido donde cada arco ( u , v ) aparece junto con su arco inverso ( v , u ), y esto no cambia la definición de homomorfismo. El orden → para gráficos dirigidos es nuevamente una red distributiva y un álgebra de Heyting, con operaciones de unión y unión definidas como antes. Sin embargo, no es denso. También hay una categoría con gráficos dirigidos como objetos y homomorfismos como flechas, que nuevamente es unCategoría cerrada cartesiana . [39] [38]
Gráficos incomparables [ editar ]
Hay muchos gráficos incomparables con respecto al pedido anticipado de homomorfismo, es decir, pares de gráficos de modo que ninguno admite un homomorfismo en el otro. [40] Una forma de construirlos es considerar la circunferencia impar de un gráfico G , la longitud de su ciclo más corto de longitud impar. La circunferencia impar está, de manera equivalente, el más pequeño número impar g para el cual no existe un homomorfismo del gráfico de ciclo en g vértices a G . Por esta razón, si G → H , entonces la circunferencia impar de G es mayor que o igual a la circunferencia impar de H . [41]
Por otro lado, si G → H , entonces el número cromática de G es menor que o igual al número cromática de H . Por lo tanto, si G tiene una circunferencia impar estrictamente mayor que H y un número cromático estrictamente mayor que H , entonces G y H son incomparables. [40] Por ejemplo, el gráfico de Grötzsch es 4-cromático y sin triángulo (tiene circunferencia 4 y circunferencia impar 5), [42] por lo que es incomparable con el gráfico de triángulo K 3 .
Ejemplos de gráficos con valores arbitrariamente grandes de circunferencia impar y número cromático son los gráficos de Kneser [43] y Mycielskians generalizados . [44] Una secuencia de tales gráficos, con valores simultáneamente crecientes de ambos parámetros, proporciona infinitos gráficos incomparables (un antichain en el preorden de homomorfismo). [45] Otras propiedades, como la densidad del preorden de homomorfismo, pueden probarse utilizando tales familias. [46] Las construcciones de gráficos con grandes valores de número cromático y circunferencia, no solo circunferencia impar, también son posibles, sino más complicadas (ver Circunferencia y coloración de gráficos ).
Entre los gráficos dirigidos, es mucho más fácil encontrar pares incomparables. Por ejemplo, considere los gráficos de ciclo dirigido C → n , con vértices 1, 2, ..., n y bordes de i a i + 1 (para i = 1, 2, ..., n - 1) y de n a 1. Allí es un homomorfismo de C → n a C → k ( n , k ≥ 3) si y solo si n es un múltiplo de k . En particular, los gráficos de ciclo dirigido C → n con nlos primos son todos incomparables. [47]
Complejidad computacional [ editar ]
En el problema gráfico homomorfismo, una instancia es un par de gráficos ( G , H ) y una solución es un homomorfismo de G a H . El problema de decisión general , preguntando si hay alguna solución, es NP-completo . [48] Sin embargo, limitar las instancias permitidas da lugar a una variedad de problemas diferentes, algunos de los cuales son mucho más fáciles de resolver. Los métodos que se aplican cuando se restringe el lado izquierdo G son muy diferentes que para el lado derecho H , pero en cada caso se conoce o conjetura una dicotomía (un límite agudo entre casos fáciles y difíciles).
Homomorfismos a un gráfico fijo [ editar ]
El problema de homomorfismo con un gráfico fijo H en el lado derecho de cada instancia también se denomina problema de coloración H. Cuando H es el gráfico completo K k , este es el problema de color del gráfico k , que puede resolverse en tiempo polinómico para k = 0, 1, 2 y NP-completo de lo contrario. [49] En particular, K 2 -colorability de un gráfico G es equivalente a G ser bipartito , que puede ser probado en el tiempo lineal. Más generalmente, cuando H es un gráfico bipartito, H-la colorabilidad es equivalente a la coloración K 2 (o la coloración K 0 / K 1 cuando H está vacío / sin bordes), por lo tanto, es igualmente fácil de decidir. [50] Pavol Hell y Jaroslav Nešetřil demostraron que, para gráficos no dirigidos, ningún otro caso es manejable:
- Teorema del infierno-Nešetřil (1990): el problema de la coloración H está en P cuando H es bipartito y NP completa de lo contrario. [51] [52]
Esto también se conoce como el teorema de la dicotomía para los homomorfismos de gráficos (no dirigidos), ya que divide los problemas de coloración H en problemas NP completos o P, sin casos intermedios . Para los gráficos dirigidos, la situación es más complicada y, de hecho, equivalente a la cuestión mucho más general de caracterizar la complejidad de los problemas de satisfacción de restricciones . [53] Resulta que los problemas de coloración H para los gráficos dirigidos son tan generales y tan diversos como los CSP con cualquier otro tipo de restricciones. [54] [55] Formalmente, un lenguaje de restricción (finito) (o plantilla ) Γes un dominio finito y un conjunto finito de relaciones sobre este dominio. CSP ( Γ ) es el problema de satisfacción de restricciones donde las instancias solo pueden usar restricciones en Γ .
- Teorema (Feder, Vardi 1998): Para cada lenguaje de restricción Γ , el problema CSP ( Γ ) es equivalente bajo reducciones de tiempo polinomial a algún problema de coloración H , para algún gráfico H dirigido . [55]
Intuitivamente, esto significa que cada técnica algorítmica o resultado de complejidad que se aplica a los problemas de coloración H para los gráficos dirigidos H se aplica igualmente a los CSP generales. En particular, uno puede preguntarse si el teorema del Infierno-Nešetřil puede extenderse a gráficos dirigidos. Según el teorema anterior, esto es equivalente a la conjetura de Feder-Vardi (también conocida como conjetura CSP, conjetura de dicotomía) en la dicotomía CSP, que establece que para cada lenguaje de restricción Γ , CSP ( Γ ) es NP-completo o en P. [48] . Esta conjetura fue probada en 2017 de forma independiente por Dmitry Zhuk y Andrei Bulatov, liderando el siguiente corolario:
- Corolario (Bulatov 2017; Zhuk 2017): El problema de coloración H en gráficos dirigidos, para una H fija , está en P o NP completo.
Homomorfismos de una familia fija de gráficos [ editar ]
El problema del homomorfismo con un solo gráfico fijo G en el lado izquierdo de las instancias de entrada se puede resolver mediante la fuerza bruta en el tiempo | V ( H ) | O (| V ( G ) |) , por lo polinomio en el tamaño del gráfico de entrada H . [56] En otras palabras, el problema está trivialmente en P para los gráficos G de tamaño acotado. La pregunta interesante es, entonces, ¿qué otras propiedades de G , además del tamaño, hacen posibles los algoritmos polinómicos?
La propiedad crucial resulta ser el ancho del árbol , una medida de la forma en que se muestra el gráfico del árbol. Para un gráfico G de ancho de árbol como máximo ky un gráfico H , el problema del homomorfismo se puede resolver a tiempo | V ( H ) | O ( k ) con un enfoque estándar de programación dinámica . De hecho, es suficiente suponer que el núcleo de G tiene un ancho de árbol como máximo k . Esto es válido incluso si no se conoce el núcleo. [57] [58]
El exponente en el | V ( H ) | El algoritmo de tiempo O ( k ) no se puede reducir significativamente: no hay algoritmo con tiempo de ejecución | V ( H ) | o (tw ( G ) / log tw ( G )) existe, asumiendo la hipótesis del tiempo exponencial (ETH), incluso si las entradas están restringidas a cualquier clase de gráficos de ancho de árbol ilimitado. [59] El ETH es una suposición no probada similar a P ≠ NP , pero más fuerte. Bajo el mismo supuesto, tampoco existen esencialmente otras propiedades que puedan usarse para obtener algoritmos de tiempo polinomiales. Esto se formaliza de la siguiente manera:
- Teorema ( Grohe ): para una clase de gráficos computable, el problema del homomorfismo para instancias con está en P si y solo si los gráficos en tener núcleos de ancho de árbol acotado (suponiendo ETH). [58]
Uno puede preguntarse si el problema es al menos soluble en un tiempo arbitrariamente depende altamente G , pero con una dependencia polinomio fijo del tamaño de H . La respuesta es nuevamente positiva si limitamos G a una clase de gráficos con núcleos de ancho de árbol acotado, y negativa para todas las demás clases. [58] En el lenguaje de la complejidad parametrizada , esto establece formalmente que el problema del homomorfismo enparametrizado por el tamaño (número de aristas) de G exhibe una dicotomía. Es de parámetro fijo manejable si los gráficos entener núcleos de ancho de árbol limitado y W [1] -completar de lo contrario.
Las mismas declaraciones son más generales para problemas de satisfacción de restricciones (o para estructuras relacionales, en otras palabras). El único supuesto necesario es que las restricciones pueden involucrar solo un número limitado de variables (todas las relaciones son de cierta aridez limitada, 2 en el caso de los gráficos). El parámetro relevante es entonces el ancho del árbol del gráfico de restricción primario .
No hay comentarios:
Publicar un comentario