En el campo matemático de la teoría de grafos , un homomorfismo de grafos es un mapeo entre dos grafos 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.
![Grafique el homomorfismo de J5 a C5](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/a/aa/Graph_homomorphism_into_C5.svg/260px-Graph_homomorphism_into_C5.svg.png)
También es una retracción sobre el subgrafo en los cinco vértices centrales. Así, J 5 es de hecho homomórficamente equivalente al núcleo C 5 .
Los homomorfismos generalizan varias nociones de coloración 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 frecuencia . [1] El hecho de que los homomorfismos se puedan componer conduce a ricas estructuras algebraicas: un preorden en gráficos, un retículo distributivo y una categoría (una para gráficos no dirigidos y otra 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 en tiempo polinomial . Los límites entre casos tratables e intratables han sido un área activa de investigación. [3]
Definiciones
En este artículo, a menos que se indique lo contrario, los gráficos son finitos, gráficos no dirigidos con bucles permitidos, pero no permitidos varios bordes (bordes paralelos). Un homomorfismo gráfico [4] f de un gráfico G = ( V ( G ), E ( G )) a un gráfico 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 se dice que G es homomórfico a H o H -colorable . Esto a menudo se denota simplemente como:
- G → H .
La definición anterior se extiende a gráficos 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 también es un homomorfismo de grafo, entonces f es un isomorfismo de grafo . [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 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 cubierta doble bipartita , formada a partir de un gráfico dividiendo cada vértice v en v 0 y v 1 y reemplazando cada arista u , v con aristas u 0 , v 1 y v 0 , u 1 . El mapeo de funciones v 0 y v 1 en la cobertura av en el gráfico original es un homomorfismo y un mapa de cobertura.
El homeomorfismo gráfico es una noción diferente, no relacionada directamente con los homomorfismos. En términos generales, requiere inyectividad, pero permite mapear bordes a caminos (no solo a bordes). Los gráficos menores son una noción aún más relajada.
Núcleos y retracciones
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/9/9e/Complete_graph_K7.svg/180px-Complete_graph_K7.svg.png)
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 puede definirse tomando la mitad izquierda (o derecha) del gráfico de dominio y mapeando solo un vértice en 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 con ningún subgrafo adecuado. De manera equivalente, un núcleo se puede definir como un gráfico que no se retrae a ningún subgráfico adecuado. [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 gráficos 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 subgráfico 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 coloraciones que contiene un triángulo (es decir, tiene el gráfico completo K 3 como 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 de este tipo . De manera similar, todo gráfico bipartito que tenga al menos un borde es equivalente a K 2 . [11]
Conexión a los colorantes
Un k- colorear , para algún número entero k , es una asignación de uno de los k colores a cada vértice de un gráfico G de manera que los extremos de cada borde obtengan colores diferentes. Los k- colorantes 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 k si y solo si asigna vértices adyacentes de G a diferentes colores (es decir, es un k- colorante). 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 también es un homomorfismo. [13] En otras palabras, si una gráfica H se puede colorear con k colores, y hay un homomorfismo de G a H , entonces G también se puede colorear con k . Por lo tanto, G → H implica χ ( G ) ≤ χ ( H ), donde χ denota el número cromático de un gráfico (el mínimo k para el cual es k -colorable). [14]
Variantes
Los homomorfismos generales también se pueden considerar 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 una coloración H de G es una asignación de colores a los vértices de G de manera que los vértices adyacentes obtengan colores compatibles. Muchas nociones de coloración de gráficos encajan en este patrón y se pueden expresar como homomorfismos de gráficos en diferentes familias de gráficos. Los colorantes circulares se pueden definir utilizando homomorfismos en gráficos circulares completos , refinando la noción habitual de colorantes. [15] La coloración fraccionada y b- pliegue se puede definir usando homomorfismos en gráficos de Kneser . [16] T-coloreaciones 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
Otra conexión interesante se refiere a las orientaciones de los gráficos. Una orientación de un gráfico no dirigido G es cualquier gráfico dirigido obtenido eligiendo una de las dos posibles orientaciones para cada borde. Un ejemplo de una orientación del gráfico completo K k es el torneo transitivo T → k con vértices 1,2,…, k y arcos de i a j siempre que i < j . Un homomorfismo entre las orientaciones de los gráficos G y H produce un homomorfismo entre los gráficos no dirigidos G y H , simplemente ignorando 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 de modo que G → tenga un homomorfismo con H → . Por lo tanto, un gráfico G es k -colorable (tiene un homomorfismo con K k ) si y solo si alguna orientación de G tiene un homomorfismo con T → k . [20]
Un teorema del folclore establece que para todo k , un grafo dirigido G tiene un homomorfismo a T → k si y solo si no admite homomorfismo de la trayectoria dirigida P → k +1 . [21] Aquí P → n es la gráfica dirigida con vértices 1, 2,…, ny aristas de i a i + 1, para i = 1, 2,…, n - 1. Por lo tanto, una gráfica es k -colorable si y solo si tiene una orientación que no admite homomorfismo de P → k +1 . Esta afirmación puede reforzarse ligeramente para decir que una gráfica es k -colorable si y solo si alguna orientación no contiene una trayectoria dirigida de longitud k (no P → k +1 como subgrafia). Este es el teorema de Gallai-Hasse-Roy-Vitaver .
Conexión con problemas de satisfacción de restricciones
Ejemplos de
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/7/76/Graph_of_non-adjacent_weekdays.svg/220px-Graph_of_non-adjacent_weekdays.svg.png)
Algunos problemas de programación se pueden modelar como una pregunta sobre cómo encontrar homomorfismos de grafos. [22] [23] Como ejemplo, uno podría querer asignar cursos de taller a franjas horarias en un calendario para que dos cursos a los que asiste el mismo estudiante no estén demasiado cerca 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. Los intervalos de tiempo forman un gráfico H , con un borde entre dos intervalos que estén lo suficientemente distantes en el tiempo. Por ejemplo, si uno quiere un horario semanal cíclico, de modo que cada estudiante obtenga sus cursos de taller en días no consecutivos, entonces H sería el gráfico de complemento de C 7 . Un homomorfismo gráfico de G a H es entonces un horario que asigna cursos a franjas horarias, según 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 de asignación de frecuencia simple se puede especificar de la siguiente manera: varios transmisores en una red inalámbrica deben elegir un canal de frecuencia en el que transmitirán datos. Para evitar interferencias , los transmisores que están geográficamente cerca deben usar canales con frecuencias muy alejadas. Si esta condición se aproxima con un solo umbral para definir "geográficamente cerca" y "lejos", entonces una elección de canal válida nuevamente corresponde a un homomorfismo gráfico. Debe ir desde el gráfico de transmisores G , con bordes entre pares que están geográficamente cerca, al gráfico de canales H , con bordes entre canales que están alejados. 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 se pueden eliminar de él. 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 problemas de homomorfismo de grafos, pueden expresar varios tipos adicionales de condiciones (como preferencias individuales o límites en el número de asignaciones coincidentes). Esto permite que los modelos sean más realistas y prácticos.
Vista formal
Los gráficos y los gráficos dirigidos pueden verse 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 sola relación binaria (adyacencia) en el dominio (el conjunto de vértices). [26] [3] Bajo este punto de vista, los homomorfismos de tales estructuras son exactamente homomorfismos de grafos. En general, la cuestión de encontrar un homomorfismo de una estructura relacional a otra es un problema de satisfacción con restricciones (CSP). El caso de los gráficos da 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 retroceso , propagación de restricciones y 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 con H corresponde a una instancia de CSP con un solo 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 que una función f de V ( G ) a V ( H ). Cada borde o arco ( u , v ) de G 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
Las composiciones de homomorfismos son homomorfismos. [13] En particular, la relación → en los gráficos es transitiva (y reflexiva, trivialmente), por lo que es un preorden en los gráficos. [27] Sea [ G ] la clase de equivalencia de un gráfico G bajo equivalencia homomórfica . La clase de equivalencia también se puede representar mediante 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 es válido excepto para los casos triviales G = K 0 o K 1 ). [29] [30] Por ejemplo, entre dos gráficos completos cualesquiera (excepto K 0 , K 1 ) hay infinitos gráficos completos circulares , correspondientes a números racionales entre números naturales. [31]
El poset de clases de equivalencia de gráficos de bajo homomorfismos es un retículo distributivo , con el se unen de [ G ] y [ H ] se define como (la clase de equivalencia de) la unión de la desunión [ G ∪ H ], y el se reúnen de [ G ] y [ H ] definido como el producto tensorial [ G × H ] (la elección de los gráficos G y H que representan las clases de equivalencia [ G ] y [ H ] no importa). [32] Los elementos de unión irreductibles de esta red son gráficos conectados exactamente . Esto se puede demostrar 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 encuentro de esta red son exactamente las gráficas multiplicativas . Estos son los gráficos K tales que un producto G × H tiene un homomorfismo con K solo cuando uno de G o H también lo tiene. La identificación de gráficas multiplicativas se encuentra en el corazón de la conjetura de Hedetniemi . [35] [36]
Los homomorfismos de gráficos también forman una categoría , con los gráficos como objetos y los 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 las gráficas es el producto de la teoría de categorías y la gráfica exponencial es el objeto exponencial para esta categoría. [36] [38] Dado que estas dos operaciones siempre están definidas, la categoría de gráficos es una categoría cerrada cartesiana . 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 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 en el que cada arco ( u , v ) aparece junto con su arco inverso ( v , u ), y esto no cambia la definición de homomorfismo. El orden → para las gráficas dirigidas es nuevamente un retículo distributivo y un álgebra de Heyting, con las operaciones de unión y encuentro 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 es nuevamente una categoría cerrada cartesiana . [39] [38]
Gráficos incomparables
![](http://wikiimg.tojsiabtv.com/wikipedia/commons/thumb/b/ba/Groetzsch-graph.svg/180px-Groetzsch-graph.svg.png)
Hay muchos gráficos incomparables con respecto al preorden de homomorfismo, es decir, pares de gráficos de manera 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 de longitud impar más corto. 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 no tiene triángulos (tiene una circunferencia 4 y una circunferencia impar 5), [42] por lo que es incomparable con el gráfico triangular 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 los Mycielskianos generalizados . [44] Una secuencia de tales gráficos, con valores crecientes simultáneamente de ambos parámetros, da un número infinito de gráficos incomparables (un antichain en el preorden de homomorfismo). [45] Otras propiedades, como la densidad del preorden de homomorfismo, pueden probarse utilizando estas 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, pero más complicadas (ver Circunferencia y coloración de gráficos ).
Entre gráficos dirigidos, es mucho más fácil encontrar pares incomparables. Por ejemplo, considere las gráficas de ciclo dirigido C → n , con vértices 1, 2,…, n y aristas de i a i + 1 (para i = 1, 2,…, n - 1) y de n a 1. Hay 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 ciclos dirigidos C → n con n primos son todos incomparables. [47]
Complejidad computacional
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 se conjetura una dicotomía (un límite definido entre casos fáciles y difíciles).
Homomorfismos a un gráfico fijo
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 la gráfica completa K k , este es el problema de colorear la gráfica k , que se puede resolver en tiempo polinomial para k = 0, 1, 2 y NP-completo en caso contrario. [49] En particular, la K 2 -colorability de un gráfico G es equivalente a que G sea bipartito , que puede probarse en tiempo lineal. De manera más general, siempre que H es un gráfico bipartito, la capacidad de coloración de H es equivalente a la capacidad de coloración de K 2 (o la capacidad de coloración de K 0 / K 1 cuando H está vacío / sin bordes), por lo que 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 de Hell-Nešetřil (1990): El problema de la coloración de H está en P cuando H es bipartito y NP-completo en caso contrario. [51] [52]
Esto también se conoce como el teorema de dicotomía para homomorfismos de grafos (no dirigidos), ya que divide los problemas de coloración H en problemas NP-completos o problemas 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 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 en reducciones de tiempo polinómico 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 problemas de coloración H para gráficos dirigidos H se aplica igualmente a los CSP generales. En particular, uno puede preguntarse si el teorema de Hell-Nešetřil se puede extender a gráficos dirigidos. Según el teorema anterior, esto es equivalente a la conjetura de Feder-Vardi (también conocida como conjetura de CSP, conjetura de dicotomía) sobre la dicotomía de 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, lo que lleva al siguiente corolario:
- Corolario (Bulatov 2017; Zhuk 2017): El problema de colorear H en gráficos dirigidos, para una H fija , está en P o NP-completo.
Homomorfismos de una familia fija de gráficos
El problema de homomorfismo con un solo gráfico fijo G en el lado izquierdo de las instancias de entrada se puede resolver mediante 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 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 polinomiales.
La propiedad crucial resulta ser el ancho del árbol , una medida de qué tan parecido a un árbol es el gráfico. Para un gráfico G de ancho de árbol como máximo k y un gráfico H , el problema de homomorfismo se puede resolver en el tiempo | V ( H ) | O ( k ) con un enfoque de programación dinámica estándar . De hecho, es suficiente asumir 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 hay esencialmente otras propiedades que puedan usarse para obtener algoritmos de tiempo polinomial. Este se formaliza de la siguiente manera:
- Teorema ( Grohe ): para una clase computable de gráficos , el problema del homomorfismo por ejemplo con está en P si y solo si los gráficos en tienen núcleos de ancho de árbol limitado (asumiendo 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 cualquier otra clase. [58] En el lenguaje de la complejidad parametrizada , esto establece formalmente que el problema del homomorfismo enparametrizado por el tamaño (número de bordes) de G presenta una dicotomía. Es tratable con parámetros fijos si los gráficos entienen núcleos de ancho de árbol acotado, y W [1] -completo en caso contrario.
Las mismas afirmaciones son válidas de manera más general para los problemas de satisfacción de restricciones (o para las estructuras relacionales, en otras palabras). La única suposición necesaria es que las restricciones pueden involucrar sólo un número limitado de variables (todas las relaciones son de alguna aridad limitada, 2 en el caso de los gráficos). El parámetro relevante es entonces el ancho de árbol del gráfico de restricción principal . [59]
Ver también
- Glosario de términos de la teoría de grafos
- Homomorfismo , para la misma noción sobre diferentes estructuras algebraicas.
- Reescritura de gráficos
- Gráficos medianos , definibles como retracciones de hipercubos
- La conjetura de Sidorenko
Notas
- ^ Infierno y Nešetřil , 2004 , p. 27.
- ^ Infierno y Nešetřil , 2004 , p. 109.
- ↑ a b c d Hell y Nešetřil, 2008 .
- ^ a b Para las introducciones, consulte (en orden de longitud creciente): Cameron (2006) ; Geňa y Tardif (1997) ; Hell y Nešetřil (2004) .
- ^ Geňa y Tardif 1997 , observación 2.3.
- ^ Godsil y Royle 2001 , p. 115.
- ↑ a b Hell & Nešetřil , 2004 , p. 19.
- ^ Hell & Nešetřil 2004 , Proposición 1.31.
- ^ Cameron 2006 , Proposición 2.3; Hell & Nešetřil 2004 , Corolario 1.32.
- ^ Infierno y Nešetřil , 2004 , p. 34.
- ^ Cameron , 2006 , p. 4, Proposición 2.5.
- ↑ a b Cameron , 2006 , p. 1; Hell & Nešetřil 2004 , Proposición 1.7.
- ↑ a b Hell & Nešetřil , 2004 , §1.7.
- ↑ Hell & Nešetřil 2004 , Corolario 1.8.
- ^ Infierno y Nešetřil 2004 , §6.1; Geňa y Tardif 1997 , §4.4.
- ^ Infierno y Nešetřil 2004 , §6.2; Geňa y Tardif 1997 , §4.5.
- ^ Infierno y Nešetřil 2004 , §6.3.
- ^ Infierno y Nešetřil 2004 , §6.4.
- ^ Fiala, J .; Kratochvíl, J. (2002), "Cubiertas parciales de gráficos", Discussiones Mathematicae Graph Theory , 22 (1): 89–99, doi : 10.7151 / dmgt.1159 , S2CID 17507393
- ^ Hell & Nešetřil 2004 , págs. 13-14.
- ^ Hell & Nešetřil 2004 , Proposición 1.20.
- ↑ a b Cameron , 2006 , p. 1.
- ^ Infierno y Nešetřil 2004 , §1.8.
- ^ Hell & Nešetřil 2004 , págs. 30–31.
- ^ Hell & Nešetřil 2004 , págs. 31–32.
- ^ Infierno y Nešetřil , 2004 , p. 28, tenga en cuenta que las estructuras relacionales se denominanallí sistemas relacionales .
- ^ Infierno y Nešetřil 2004 , §3.1.
- ^ Infierno y Nešetřil 2004 , Teorema 3.1.
- ^ Infierno y Nešetřil 2004 , Teorema 3.30; Geňa y Tardif 1997 , Teorema 2.33.
- ^ Welzl, E. (1982), "Las familias de colores son densas", Informática teórica , 17 : 29–41, doi : 10.1016 / 0304-3975 (82) 90129-3
- ^ Infierno y Nešetřil , 2004 , p. 192; Geňa y Tardif 1997 , pág. 127.
- ^ Hell & Nešetřil 2004 , Proposición 3.2, la distributividad se establece en la Proposición 2.4; Geňa y Tardif 1997 , Teorema 2.37.
- ^ Kwuida, Léonard; Lehtonen, Erkko (2011), "On the Homomorphism Order of Labelled Posets", Order , 28 (2): 251-265, arXiv : 0911.0200 , doi : 10.1007 / s11083-010-9169-x , S2CID 14920600
- ^ Gray 2014 , Lema 3.7.
- ^ Tardif, C. (2008), "La conjetura de Hedetniemi, 40 años después" (PDF) , Graph Theory Notes of New York , 54 : 46–57, MR 2445666.
- ^ a b c Dwight, D .; Sauer, N. (1996), "Lattices surgen en investigaciones categóricas de la conjetura de Hedetniemi", Discrete Mathematics , 152 (1-3): 125-139, doi : 10.1016 / 0012-365X (94) 00298-W
- ^ Infierno y Nešetřil , 2004 , p. 125.
- ^ a b c Gris, 2014 .
- ^ Brown y col. 2008 .
- ↑ a b Hell & Nešetřil , 2004 , p. 7.
- ^ Geňa y Tardif 1997 , observación 2.6.
- ^ Weisstein, Eric W. "Grötzsch Graph" . MathWorld .
- ^ Geňa y Tardif 1997 , Proposición 3.14.
- ^ Gyárfás, A .; Jensen, T .; Stiebitz, M. (2004), "Sobre gráficos con clases de color fuertemente independientes", Journal of Graph Theory , 46 (1): 1-14, doi : 10.1002 / jgt.10165
- ^ Hell & Nešetřil 2004 , Proposición 3.4.
- ^ Infierno y Nešetřil , 2004 , p. 96.
- ^ Infierno y Nešetřil , 2004 , p. 35.
- ↑ a b Bodirsky , 2007 , §1.3.
- ^ Infierno y Nešetřil 2004 , §5.1.
- ^ Hell & Nešetřil 2004 , Proposición 5.1.
- ^ Infierno y Nešetřil 2004 , §5.2.
- ^ Infierno, Pavol ; Nešetřil, Jaroslav (1990), "Sobre la complejidad de la coloración H", Journal of Combinatorial Theory, Serie B , 48 (1): 92–110, doi : 10.1016 / 0095-8956 (90) 90132-J
- ^ Infierno y Nešetřil 2004 , §5.3.
- ^ Infierno y Nešetřil 2004 , Teorema 5.14.
- ^ a b Feder, Tomás; Vardi, Moshe Y. (1998), "The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory" , SIAM Journal on Computing , 28 (1): 57-104, doi : 10.1137 / S0097539794266766
- ^ Cygan, M .; Fomin, FV; Golovnev, A .; Kulikov, AS; Mihajlin, I .; Pachocki, J .; Socała, A. (2016). Límites estrechos para el homomorfismo del gráfico y el isomorfismo del subgráfico . 28 ° Simposio anual ACM-SIAM sobre algoritmos discretos (SODA 2016). SIAM . págs. 1643-1649. arXiv : 1507.03738 . Código bibliográfico : 2015arXiv150703738F . ISBN 978-1-611974-33-1.Mantenimiento de CS1: utiliza el parámetro de autores ( enlace )
- ^ Dalmau, Víctor; Kolaitis, Phokion G .; Vardi, Moshe Y. (2002). Satisfacción de restricciones, ancho de árbol limitado y lógicas de variables finitas . Octava Conferencia Internacional sobre Principios y Práctica de la Programación de Restricciones (CP 2002). págs. 310–326. doi : 10.1007 / 3-540-46135-3_21 .
- ^ a b c Grohe, Martin (2007), "La complejidad del homomorfismo y los problemas de satisfacción de restricciones vistos desde el otro lado", Revista de la ACM , 54 (1): 1 – es, doi : 10.1145 / 1206035.1206036 , S2CID 11797906
- ^ a b Marx, Dániel (2010), "Can You Beat Treewidth?", Theory of Computing , 6 : 85-112, doi : 10.4086 / toc.2010.v006a005
Referencias
Libros y exposiciones generales
- Cameron, P. (2006), Graph Homomorphisms, Combinatorics Study Group Notes (PDF)
- Infierno, Pavol ; Nešetřil, Jaroslav (2004), Gráficos y homomorfismos , Oxford Lecture Series in Mathematics and Its Applications, 28 , Oxford University Press, ISBN 0-19-852817-5
- Geňa, H .; Tardif, C. (1997), "Graph homomorfisms: estructura y simetría", Graph Symmetry: Algebraic Methods and Applications (PDF) , Springer, pp. 107-166, doi : 10.1007 / 978-94-015-8937-6_4
- Godsil, C .; Royle, G. (2001), "6. Homomorfismos", Teoría de grafos algebraicos , Textos de posgrado en matemáticas, 207 , Springer – Verlag Nueva York, doi : 10.1007 / 978-1-4613-0163-9 , ISBN 978-1-4613-0163-9
En satisfacción de restricciones y álgebra universal
- Bodirsky, M. (2007), Homomorfismos de gráficos y álgebra universal, Notas del curso (PDF)
- Infierno, Pavol ; Nešetřil, Jaroslav (2008), "Coloración, satisfacción de restricciones y complejidad" (PDF) , Computer Science Review , 2 (3): 143–163, doi : 10.1016 / j.cosrev.2008.10.003
En teoría de celosía y teoría de categorías
- Brown, R .; Morris, I .; Shrimpton, J .; Wensley, CD (2008), "Gráficos de morfismos de gráficos" , Electronic Journal of Combinatorics , 15 (1): A1, doi : 10.37236 / 919
- Gray, CT (2014), The Digraph Lattice (PDF)( Becas de investigación de vacaciones de AMSI , informe de investigación de estudiantes supervisado por Brian Davey y Jane Pitkethly, La Trobe University ).