Homomorfismo de grafos

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 14 de octubre de 2021; las comprobaciones requieren 2 ediciones .

Un homomorfismo de grafos es un mapeo entre dos grafos que no rompe la estructura. Más específicamente, es un mapeo entre un conjunto de vértices de dos gráficos que mapea vértices adyacentes a los adyacentes.

Los homomorfismos generalizan varias nociones de coloración de gráficos y permiten la expresión de clases importantes de problemas de satisfacción de restricciones , como algunos problemas de programación o problemas de asignación de radiofrecuencia [1] . El hecho de que los homomorfismos se puedan usar secuencialmente conduce a ricas estructuras algebraicas: ordenamiento previo de gráficos, red distributiva y categorías (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 generalmente prohibitiva, pero se conocen muchos casos especiales cuando la tarea es factible en tiempo polinomial . Los límites entre casos solucionables e insuperables se encuentran en un área de investigación activa [3] .

Definiciones

En este artículo, a menos que se indique lo contrario, los gráficos significan gráficos finitos no dirigidos con bucles permitidos , pero no se permiten múltiples bordes (paralelos). Un homomorfismo de gráfico [4] [5] [6] : f de gráfico a gráfico , que se escribe como ${\ estilo de visualización G = (V (G), E (G))}$ ${\ estilo de visualización H = (V (H), E (H))}$

f:G\a H

es una función de V ( G ) a V ( H ) que asigna los puntos finales de cada borde de G a los puntos finales de algún borde de H . Formalmente, se sigue de , para todos los pares de vértices u , v de V ( G ). Si hay algún homomorfismo de G a H , entonces se dice que el gráfico G es homomórfico al gráfico H , o que es H -coloreable . Esto a menudo se conoce como ${\ estilo de visualización \ {u, v \} \ en E (G)}$ ${\ estilo de visualización \ {f (u), f (v) \} \ en E (H)}$

{\ estilo de visualización G \ a H}

La definición anterior se extiende a grafos dirigidos. Entonces, para un homomorfismo, es un arco (borde dirigido) del gráfico H cuando ( u , v ) es un arco del gráfico G. ${\ estilo de visualización f: G \ a H, (f (u), f (v))}$

Hay un homomorfismo inyectivo de G a H (es decir, un mapa que nunca mapea diferentes vértices a uno solo) si y solo si G es un subgrafo de H. Si un homomorfismo 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 [7] . $f:G\a H$

Los mapeos de cobertura son un tipo común de homomorfismo que refleja la definición y muchas propiedades de una cobertura en topología [8] . Se definen como homomorfismos sobreyectivos que son localmente biyectivos, es decir, una biyección en una vecindad de cada vértice. Un ejemplo es una cubierta doble por un gráfico bipartito formado a partir de un gráfico dividiendo cada vértice v en y y reemplazando cada borde u , v por dos bordes y . La función que mapea v 0 y v 1 a v del gráfico original es un homomorfismo y un mapeo de cobertura. $v_{0}$ $v_{1}$ ${\ estilo de visualización u_ {0}, v_ {1}}$ ${\ Displaystyle v_ {0}, u_ {1}}$

El homeomorfismo de grafos es un concepto separado, no directamente relacionado con los homomorfismos. En términos generales, requiere inyectividad, pero permite que los bordes se asignen a rutas (en lugar de solo bordes). Los menores gráficos siguen siendo un concepto más débil.

Núcleos y retractos

Dos gráficos G y H son homomórficamente equivalentes si y [4] [5] [6] . ${\ estilo de visualización G \ a H}$ ${\ estilo de visualización H \ a G}$

Una retracción es un homomorfismo r de G a un subgrafo H de G tal que r ( v )= v para todo vértice v de H . En este caso, el subgrafo H se llama un retracto del grafo G [9] .

Un kernel es un grafo que no tiene un homomorfismo para ningún subgrafo propio. De manera equivalente, un núcleo puede definirse como un gráfico que no es una retracción de ningún subgráfico adecuado [10] . Cualquier grafo G es homomórficamente equivalente a un núcleo único (salvo isomorfismo), que se denomina núcleo del grafo G [11] [12] . Tenga en cuenta que esto no es cierto para gráficos infinitos generales [13] . 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. Cualquier grafo dirigido y no dirigido contiene su kernel tanto como un retracto como un subgrafo generado [9] .

Por ejemplo, todos los gráficos completos K n y todos los ciclos impares ( gráficos de ciclo de longitud impar) son núcleos. Cualquier gráfico G de 3 colores que contenga un triángulo (es decir, que tenga un gráfico completo K 3 como subgráfico) es homeomórficamente equivalente a K 3 . Esto se debe a que, por un lado, una coloración en 3 de un gráfico G es lo mismo que un homomorfismo , como se explica a continuación. Por otro lado, cualquier subgrafo de G admite trivialmente un homomorfismo a G , de donde se sigue que . Esto también significa que K 3 es el núcleo de cualquier gráfico G . De manera similar, cualquier gráfico bipartito que tenga al menos una arista es equivalente a K 2 [14] . $G\to K_{3}$ $K_{3}\a G$

Relación con dibujos para colorear

Una coloración k para algún entero k es la asignación de uno de los k colores a cada vértice del grafo G para que los vértices extremos de cada arista tengan colores diferentes. k -Los colores del grafo G corresponden exactamente a los homomorfismos de G al grafo completo K k [15] [16] . Además, los vértices del gráfico K k corresponden a k colores y dos colores son adyacentes como vértices del gráfico K k si y sólo si son diferentes. Por lo tanto, la función define un homomorfismo en K k si y solo si los vértices adyacentes del gráfico G están coloreados en diferentes colores. En particular, un grafo G es k -coloreable si y sólo si es Kk -colorable [ 15] [16] .

Si hay dos homomorfismos y , entonces su superposición también es un homomorfismo [17] . En otras palabras, si el gráfico H se puede colorear con k colores y hay un homomorfismo G en H , entonces G también se puede colorear con k colores. Por lo tanto, se sigue de , donde significa el número cromático de la gráfica (el menor número de colores k , en los que se puede colorear la gráfica) [18] . ${\ estilo de visualización G \ a H}$ ${\ Displaystyle H \ a K_ {k}}$ ${\displaystyle G\to K_{k))$ ${\ estilo de visualización G \ a H}$ ${\ estilo de visualización \ chi (G) \ leqslant \ chi (H)}$ $\ chi$

Opciones

Los homomorfismos generales también se pueden considerar como un tipo de coloración: si los vértices de un gráfico fijo H son colores permitidos , y los bordes del gráfico H describen qué colores son compatibles , entonces el color H del gráfico G es la asignación de colores a los vértices del gráfico G para que los vértices adyacentes reciban colores compatibles. Muchas nociones de coloración de gráficos encajan en este esquema y pueden expresarse como homomorfismos de gráficos en diferentes familias de gráficos. Los colores de ciclo se pueden definir usando homomorfismos para completar el ciclo de gráficos , refinando la noción habitual de coloración [19] [20] . Las coloraciones fraccionarias y plegadas en b se pueden definir usando homomorfismos para gráficos de Kneser [21] [22] Las coloraciones T corresponden a homomorfismos para algunos gráficos infinitos [23] . { Una coloración dirigida de un gráfico dirigido es un homomorfismo para cualquier gráfico dirigido [24] . La coloración L(2,1) es un homomorfismo localmente inyectivo en el complemento de un camino , lo que significa que debe ser inyectivo en una vecindad de cada vértice [25] .

Orientaciones sin caminos largos

Otra conexión interesante se refiere a la orientación de los gráficos. Una orientación de un gráfico no dirigido G es cualquier gráfico dirigido obtenido eligiendo entre dos orientaciones posibles para cada borde. Un ejemplo de la orientación de un grafo completo K k es un torneo transitivo con vértices 1,2,…, k y arcos de i a j cuando i < j . Un homomorfismo entre las orientaciones de los gráficos G y H da un homomorfismo entre los gráficos no dirigidos G y H si simplemente ignoramos las orientaciones. Por otro lado, dado un homomorfismo entre grafos no dirigidos, cualquier orientación de H se puede mapear a una orientación del gráfico de G , por lo que tiene un homomorfismo en . Por lo tanto, un grafo G es k -coloreable (tiene un homomorfismo en K k ) si y sólo si alguna orientación de G tiene un homomorfismo en [26] . ${\vec{T}}_{k}$ ${\ estilo de visualización G \ a H}$ ${\ vec {H}}$ ${\ estilo de visualización {\ vec {G}}}$ ${\ estilo de visualización {\ vec {G}}}$ ${\ vec {H}}$ ${\vec{T}}_{k}$

El teorema del folklore dice que para cualquier k un grafo dirigido G tiene un homomorfismo en si y sólo si no admite el homomorfismo de [27] . Aquí , es un camino orientado con vértices 1, 2, …, n y arcos de i a i + 1 para i =1, 2, …, n − 1. Por lo tanto, el gráfico es k -coloreable si y solo si tiene la orientación , que no admite un homomorfismo de . Esta afirmación puede reforzarse ligeramente para decir que un gráfico es k -coloreable si y solo si alguna orientación no contiene un camino dirigido de longitud k (no como un subgrafo). Este es el teorema de Gallai-Hasse-Roy-Vitaver . ${\vec{T}}_{k}$ ${\vec{P}}_{k+1}$ ${\vec{P}}_{n}$ ${\vec{P}}_{k+1}$ ${\vec{P}}_{k+1}$

Relación con problemas de satisfacción de restricciones

Ejemplos

Algunos problemas de programación se pueden modelar como una cuestión de encontrar homomorfismos de gráficos [15] [28] . Como ejemplo, uno podría tratar de programar sesiones de práctica para que dos cursos a los que asista el mismo estudiante no estén demasiado cerca en el tiempo. Los cursos forman un grafo G , con aristas entre dos cursos, si son atendidos por el mismo estudiante. El tiempo posible de realizar cursos forma un gráfico H con bordes entre dos ventanas de tiempo, si la distancia en el tiempo entre ellas es lo suficientemente grande. Por ejemplo, si se quiere tener un horario semanal cíclico de modo que cada estudiante venga a practicar cada dos días, entonces la columna H sería el complemento de la columna C 7 . Un homomorfismo gráfico de G a H es entonces la asignación de cursos en ventanas de tiempo [15] . Para agregar un requisito, digamos, que ningún estudiante tenga una clase tanto el viernes como el lunes, es suficiente eliminar un borde del gráfico H .

Un problema simple de distribución de frecuencias se puede formular de la siguiente manera. Hay varios transmisores de red inalámbrica . Debe seleccionar en cada uno de ellos el canal de frecuencia a través del cual transmitirá los datos. Para evitar interferencias , los transmisores geográficamente cercanos deben tener canales con frecuencias suficientemente diferentes. Si esta condición se limita a un umbral simple para los conceptos "geográficamente cerca" y "suficientemente lejos", la elección válida de canales corresponde nuevamente a un homomorfismo de grafo. Aquí, el gráfico G será un conjunto de transmisores con bordes entre ellos si están geográficamente cerca, y el gráfico H será un conjunto de canales con bordes entre canales si las frecuencias son suficientemente diferentes. Aunque este modelo está muy simplificado, permite cierta flexibilidad: para un par de transmisores que no están cerca, pero que pueden interferir entre sí debido a las características geográficas, se puede agregar un arco en G. Y el arco entre transmisores que no funcionan al mismo tiempo se puede eliminar del gráfico. De manera similar, un borde entre un par de canales que están muy separados pero tienen interferencia armónica se puede eliminar del gráfico H [29] .

En cada caso, estos modelos simplificados muestran muchas características que deberían resolverse en la práctica [30] . Los problemas de satisfacción de restricciones , que generalizan problemas de homomorfismo de grafos, pueden expresar tipos adicionales de condiciones (como preferencias individuales o restricciones en el número de asignaciones coincidentes). Esto hace que los modelos sean más realistas y prácticos.

Punto de vista formal

Los gráficos dirigidos y dirigidos pueden considerarse instancias frecuentes de un concepto más general llamado estructuras relacionales que se definen como un conjunto con una tupla de relaciones en él). Los grafos dirigidos son estructuras con una relación binaria (adyacencia) en un dominio (un conjunto de vértices) [31] [3] . Desde este punto de vista, los homomorfismos de tales estructuras son exactamente homomorfismos de grafos. En el caso general, la cuestión de encontrar un homomorfismo de una estructura 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 problemas de satisfacción de restricciones más complejos. Muchos métodos algorítmicos para encontrar homomorfismos de gráficos, como backtracking , propagación de restricciones y búsqueda local son aplicables a todos los problemas de satisfacción de restricciones [3] .

Para los gráficos G y H , la cuestión de si el gráfico G tiene un homomorfismo con respecto al gráfico H corresponde a un caso particular del problema de satisfacción de restricciones con un solo tipo de restricción [3] . En este problema , las variables serán los vértices de la gráfica G , y el rango de cada variable será el conjunto de vértices de la gráfica H. La solución es una función que asigna un elemento del rango a cada variable, de modo que la función f asigna V ( G ) a V ( H ). Cada arista o arco [32] ( u , v ) del gráfico G corresponde entonces a la restricción (( u , v ), E( H )). Esta restricción expresa que la solución debe mapear el arco ( u , v ) al par ( f ( u ), f ( v )), que es la relación E ( H ), es decir, al arco de la gráfica H . La solución al problema es una solución que satisface todas las restricciones, es decir, es exactamente un homomorfismo de G a H.

Estructura de los homomorfismos

Las superposiciones de homomorfismos son homomorfismos [17] . En particular, una relación sobre grafos es transitiva (y, trivialmente, reflexiva), por lo que esta relación es un preorden sobre grafos [33] . Denotaremos la clase de equivalencia de homomorfismo de un grafo G por [ G ]. Una clase de equivalencia se puede representar mediante un solo kernel en [ G ]. La relación está parcialmente ordenada sobre estas clases de equivalencia. Define un conjunto parcialmente ordenado [34] . $\a$ $\a$

Sea G < H lo que significa que hay un homomorfismo de G a H pero no homomorfismo de H a G . La relación es de orden denso , lo que significa que para todos los gráficos (no dirigidos) G , H tales que G < H , existe un gráfico K tal que G < K < H (esto es válido en todos los casos excepto en los casos triviales o ) [35] [36] [37] . Por ejemplo, entre dos gráficos completos cualesquiera (excepto ) hay infinitos gráficos completos cíclicos correspondientes a números racionales [38] [39] . $\a$ ${\displaystyle G=K_{0))$ $K_1$ ${\displaystyle K_{0},K_{1))$

Un conjunto parcialmente ordenado de clases de equivalencia de grafos por homomorfismo es una red distributiva , con la unión de [ G ] y [ H ] definida como la unión disjunta (clase de equivalencia) y la intersección de [ G ] y [ H ] definidos como producto tensorial (no importa la elección de los gráficos G y H como representantes de las clases de equivalencia [ G ] y [ H ]) [40] [41] . Los elementos de esta red que son irreducibles en la unión son grafos exactamente conexos . Esto se puede demostrar utilizando el hecho de que un homomorfismo asigna un gráfico conexo a un componente conexo del gráfico de destino [42] [43] . Los elementos irreducibles de intersección de esta red son exactamente gráficos multiplicativos . Estos son gráficos K tales que el producto tiene un homomorfismo en K solo si uno de los gráficos G o H tiene tal homomorfismo. El descubrimiento de los gráficos multiplicativos es el núcleo de la conjetura de Hedetniemi [44] [45] . $[G\taza H]$ ${\ estilo de visualización [G \ veces H]}$ $G\veces H$

Los homomorfismos de gráficos también forman una categoría con gráficos como objetos y homomorfismos como flechas [46] . El objeto inicial es un gráfico vacío, mientras que el objeto terminal es un gráfico con un vértice y un bucle en ese vértice. El producto tensorial de gráficas es un producto en la teoría de categorías y una gráfica exponencial es un objeto exponencial para una categoría [45] [47] . Dado que estas dos operaciones siempre están definidas, la categoría de grafos es una categoría cerrada cartesiana . Por las mismas razones, la red de clases de equivalencia de grafos por homomorfismos es, de hecho, un álgebra de Heyting [45] [47] .

Para grafos dirigidos, se aplican las mismas definiciones. En particular, se ordena parcialmente sobre las clases de equivalencia de grafos dirigidos. Este orden difiere del orden de las clases de equivalencia de grafos no dirigidos, pero lo contiene como un suborden. Esto se debe a que cualquier gráfico no dirigido puede considerarse como dirigido, en el que cualquier arco ( u , v ) aparece junto con un arco inverso ( v , u ), y esto no cambia la definición de homomorfismo. El orden de los grafos dirigidos es nuevamente un retículo distributivo y un álgebra de Heyting con las operaciones de unión e intersección definidas como antes. Sin embargo, este orden no es estricto. También hay una categoría con gráficos dirigidos como objetos y homomorfismos como flechas, que es nuevamente una categoría cartesiana cerrada [48] [47] . $\a$ $\a$ $\a$

Gráficos incomparables

Hay muchos grafos incomparables según el preorden de los homomorfismos, es decir, pares de grafos tales que no hay homomorfismos entre uno y otro [49] . Una de las formas de construir tales gráficos es considerar la circunferencia impar del gráfico G , es decir, la longitud de su ciclo más corto de longitud impar. Una circunferencia impar es, de manera equivalente, el número impar más pequeño g para el cual existe un homomorfismo de un gráfico de ciclo con g vértices a G . Por ello, si , entonces el perímetro impar de la gráfica G es mayor o igual que el perímetro impar de la gráfica H [50] . ${\ estilo de visualización G \ a H}$

Por otro lado, si , entonces el número cromático de la gráfica G es menor o igual que el número cromático de la gráfica H. Por tanto, si un grafo G tiene un perímetro impar estrictamente mayor que H y un número cromático estrictamente mayor que [49]incomparablesHyG, entoncesH [51] , por lo que es incompatible con el triángulo K 3 . ${\ estilo de visualización G \ a H}$

Ejemplos de gráficos con valores arbitrariamente grandes de circunferencia impar y número cromático son los gráficos de Kneser [52] y los mychelskianos generalizados [53] . Una secuencia de tales gráficos con un aumento simultáneo en los valores de ambos parámetros da un número infinito de gráficos incomparables ( una anticadena en el preorden de los homomorfismos) [54] . Otras propiedades, como la densidad del preorden de los homomorfismos, pueden demostrarse utilizando dichas familias [55] . También es posible construir gráficos con valores grandes de número cromático y circunferencia, en lugar de solo circunferencias impares, pero más difícil (ver Gráfico de circunferencia y coloreado ).

Es mucho más fácil encontrar pares incomparables entre grafos dirigidos. Por ejemplo, considere gráficos de ciclos dirigidos 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 un homomorfismo de a entonces y sólo cuando n es múltiplo de k . En particular, los gráficos de ciclo dirigido con n primo son todos incomparables [56] . ${\vec{C}}_{n}$ ${\vec{C}}_{n}$ ${\vec {C}}_{k}(n,k\geqslant 3)$ ${\vec{C}}_{n}$

Complejidad computacional

En el problema de homomorfismo de grafos, una instancia del problema consiste en un par de grafos ( G , H ), y la solución es un homomorfismo de G a H. El problema de solucionabilidad general , que pregunta si hay una solución a este problema, es NP-completo [57] . Sin embargo, las restricciones de gráficos conducen a una serie de problemas diferentes, algunos de los cuales son más fáciles de resolver. Los métodos que usan restricciones en el gráfico de la izquierda G son muy diferentes de los métodos usados en el gráfico de la derecha H , pero en cada caso la dicotomía (límites estrictos entre casos simples y complejos) es conocida o asumida.

Homomorfismos a un grafo fijo

El problema del homomorfismo con un gráfico fijo H en el lado derecho de cada caso se denomina problema de coloración de H. Cuando H es un grafo completo K k , se trata de un problema de coloreado de grafo k que se puede resolver en tiempo polinomial para k =0, 1, 2 y es NP-completo en caso contrario [58] . En particular, la posibilidad de una coloración K 2 de un grafo G es equivalente al grafo bipartito G , que puede verificarse en tiempo lineal. De manera más general, cuando H es un grafo bipartito, la posibilidad de coloración de H es equivalente a la posibilidad de coloración de K 2 (o K 0 / K 1 -coloreable cuando H está vacío o no tiene aristas), y por lo tanto es igualmente fácil de resolver [59] . Pavol Hell y Jaroslav Neshetril demostraron que ningún otro caso es fácil para grafos no dirigidos:

Teorema de Hell-Neshetril (1990): un problema de coloración de H está en la clase P si H es bipartito y NP-duro en caso contrario [60] [61] .

El teorema también se conoce como el teorema de la dicotomía para el homomorfismo gráfico (no dirigido), ya que divide los problemas de coloración H en problemas NP-completos y problemas de clase P sin casos intermedios . Para grafos dirigidos, la situación es más complicada y, de hecho, es equivalente a la pregunta más general de describir la complejidad de satisfacer restricciones [62] . Resulta que los problemas de coloración de H para grafos dirigidos son tan generales y tan diversos como los problemas de satisfacción de restricciones con cualquier otro tipo de restricciones [63] [64] . Formalmente, un lenguaje de restricciones (finito) Γ es un dominio finito y un conjunto finito de relaciones en ese dominio. CSP( Γ ) es un problema de satisfacción de restricciones donde las instancias pueden usar solo restricciones de Γ .

Teorema (Feder, Vardy 1998): Para cualquier lenguaje de restricciones Γ , CSP( Γ ) es equivalente después de la reducción polinomial a algún problema de coloración de H para algún grafo dirigido H [64] .

Intuitivamente, esto significa que cualquier técnica algorítmica o resultado de complejidad aplicable a problemas de coloración H para grafos dirigidos H también se aplica a problemas generales de satisfacción de restricciones. En particular, uno podría preguntarse si el teorema de Hell-Neshetril se puede extender a grafos dirigidos. Según el teorema anterior, esto es equivalente a la conjetura de Feder-Vardi sobre la dicotomía de los problemas de satisfacción de restricciones, que establece que para cualquier lenguaje de restricciones Γ , CSP( Γ ) es NP-completo o pertenece a la clase P [57] .

Homomorfismos de una familia fija de grafos

El problema del homomorfismo con un gráfico G fijo en el lado izquierdo se puede resolver mediante una búsqueda exhaustiva en el tiempo | V ( H )| O(| V ( G )|) , es decir, polinomio en el tamaño del gráfico de entrada H [65] . En otras palabras, el problema es trivial en P para grafos G de tamaño acotado. Entonces, una pregunta interesante es qué otras propiedades del gráfico G además del tamaño hacen posibles los algoritmos polinómicos.

La propiedad clave resulta ser treewidth , una medida de cuán similar es un gráfico a un árbol. Para un gráfico G con ancho de árbol como máximo k y un gráfico H , el problema del homomorfismo se puede resolver en el tiempo | V ( H )| O( k ) por métodos de programación dinámica estándar . De hecho, basta con suponer que el núcleo de G tiene un ancho de árbol como máximo k . Esto es cierto incluso si no se conoce el núcleo [66] [67] .

Indicador en el algoritmo con tiempo de ejecución| V ( H )| O( k ) no puede reducirse significativamente; no existe un algoritmo que se ejecute en el tiempo | V ( H )| o(tw( G ) /log tw( G )) si la hipótesis del tiempo exponencial ( ETH ) es verdadera, incluso si la entrada está limitada por cualquier clase de gráficos de ancho de árbol ilimitado [68] . ETH es una suposición no comprobada, similar a la suposición P ≠ NP , pero más estricta. Bajo las mismas suposiciones, no hay otras propiedades que puedan usarse para derivar algoritmos de tiempo polinomial. Esto se formaliza mediante el teorema:

Teorema (Martin Grohe): Para una clase computable de grafos , el problema de homomorfismo para c pertenece a P si y solo si los grafos tienen núcleos de ancho de árbol acotado (en el supuesto ETH) [67] .

{\ matemáticas {G}}

{\ estilo de visualización (G, H)}

G\in {\mathcal {G}}

{\ matemáticas {G}}

Uno puede preguntarse si el problema se puede resolver con una dependencia arbitrariamente alta de G , pero con una dependencia polinomial fija del tamaño del gráfico H. La respuesta es sí si restringimos el grafo G a una clase con núcleos de ancho de árbol acotado, y no para todas las demás clases [67] . En el lenguaje de la complejidad parametrizada , esta afirmación dice formalmente que el problema del homomorfismo con graph , parametrizado por el tamaño (número de aristas) de G , muestra una dicotomía. Es decidible de parámetro fijo si los gráficos en la clase tienen núcleos de ancho de árbol acotado, y W[1]-completo de lo contrario. ${\ matemáticas {G}}$ ${\ matemáticas {G}}$

La misma afirmación es válida para problemas más generales de satisfacción de restricciones (o, en otras palabras, para estructuras relacionales). La única suposición requerida es que las restricciones pueden involucrar solo un número limitado de variables. El parámetro es entonces el ancho del árbol del gráfico de restricción principal [68] .

Véase también

Hipótesis Sidorenko

Notas

↑ Infierno, Nešetřil, 2004 , p. 27
↑ Infierno, Nešetřil, 2004 , p. 109.
↑ 1 2 3 4 Infierno, Nešetřil, 2008 .
↑ 12 Cameron , 2006 .
↑ 1 2 Geňa, Tardif, 1997 .
↑ 1 2 Infierno, Nešetřil, 2004 .
↑ Gena, Tardif, 1997 , Observación 2.3.
↑ Godsil, Royle, 2001 , pág. 115.
↑ 1 2 Infierno, Nešetřil, 2004 , p. 19
↑ Infierno, Nešetřil, 2004 , Proposición 1.31.
↑ Cameron, 2006 , Proposición 2.3.
↑ Infierno, Nešetřil, 2004 , Corolario 1.32.
↑ Infierno, Nešetřil, 2004 , p. 34.
↑ Cameron, 2006 , pág. 4 (Proposición 2.5).
↑ 1 2 3 4 Cameron, 2006 , pág. una.
↑ 1 2 Hell, Nešetřil, 2004 , Proposición 1.7.
↑ 1 2 Infierno, Nešetřil, 2004 , §1.7.
↑ Infierno, Nešetřil, 2004 , Corolario 1.8.
↑ Infierno, Nešetřil, 2004 , §6.1.
↑ Gena, Tardif, 1997 , §4.4.
↑ Infierno, Nešetřil, 2004 , §6.2.
↑ Gena, Tardif, 1997 , §4.5.
↑ Infierno, Nešetřil, 2004 , §6.3.
↑ Infierno, Nešetřil, 2004 , §6.4.
↑ * Fiala J., Kratochvíl J. Cubiertas parciales de grafos // Discusiones Mathematicae Graph Theory. - 2002. - T. 22 , núm. 1 . — S. 89–99 . -doi : 10.7151 / dmgt.1159 .
↑ Infierno, Nešetřil, 2004 , p. 13–14.
↑ Infierno, Nešetřil, 2004 , Proposición 1.20.
↑ Infierno, Nešetřil, 2004 , §1.8.
↑ Infierno, Nešetřil, 2004 , p. 30–31.
↑ Infierno, Nešetřil, 2004 , p. 31–32.
↑ Infierno, Nešetřil, 2004 , p. 28. Tenga en cuenta que las estructuras relacionales en el artículo se denominan sistemas relacionales .
↑ Recuerda que, por lo general, los bordes de un gráfico dirigido se denominan arcos.
↑ Infierno, Nešetřil, 2004 , §3.1.
↑ Infierno, Nešetřil, 2004 , Teorema 3.1.
↑ Infierno, Nešetřil, 2004 , Teorema 3.30.
↑ Geňa, Tardif, 1997 , Teorema 2.33.
↑ Welzl, 1982 , pág. 29–41.
↑ Infierno, Nešetřil, 2004 , p. 192.
↑ Gena, Tardif, 1997 , p. 127.
↑ Hell, Nešetřil, 2004 , Proposición 3.2, la distributividad se establece en la Proposición 2.4.
↑ Geňa, Tardif, 1997 , Teorema 2.37.
↑ Kwuida, Lehtonen, 2011 , pág. 251–265.
↑ Gray, 2014 , Lema 3.7.
↑ Tardif, 2008 , pág. 46–57.
↑ 1 2 3 Dwight, Sauer, 1996 , pág. 125–139.
↑ Infierno, Nešetřil, 2004 , p. 125.
↑ 1 2 3 Gray, 2014 .
↑ Marrón, Morris, Shrimpton, Wensley, 2008 .
↑ 1 2 Infierno, Nešetřil, 2004 , p. 7.
↑ Gena, Tardif, 1997 , Observación 2.6.
↑ Weisstein, Eric W. Grötzsch Gráfico en el sitio web Wolfram MathWorld .
↑ Gena, Tardif, 1997 , Proposición 3.14.
↑ Gyárfás, Jensen, Stiebitz, 2004 , p. 1–14.
↑ Hell, Nešetřil, 2004 , Proposición 3.4.
↑ Infierno, Nešetřil, 2004 , p. 96.
↑ Infierno, Nešetřil, 2004 , p. 35.
↑ 1 2 Bodirsky, 2007 , §1.3.
↑ Infierno, Nešetřil, 2004 , §5.1.
↑ Infierno, Nešetřil, 2004 , Proposición 5.1.
↑ Infierno, Nešetřil, 2004 , §5.2.
↑ Infierno, Nešetřil, 1990 , p. 92–110.
↑ Infierno, Nešetřil, 2004 , §5.3.
↑ Infierno, Nešetřil, 2004 , Teorema 5.14.
↑ 1 2 Feder, Vardi, 1998 , p. 57–104.
↑ Cygan, Fomin, Golovnev et al., 2016 , pág. 1643-1649
↑ Dalmau, Kolaitis, Vardi, 2002 , p. 310–326.
↑ 1 2 3 Grohe, 2007 .
↑ 12 Marx , 2010 , pág. 85–112.

Literatura

Welzl E. Las familias de colores son densas // Theoret. computar ciencia . - 1982. - T. 17 . — págs. 29–41 . - doi : 10.1016/0304-3975(82)90129-3 .
Pavol Hell, Jaroslav Nesetzil. Sobre la complejidad de la coloración H // JCTB . - 1990. - T. 48 , núm. 1 . — S. 92–110 . -doi : 10.1016 / 0095-8956(90)90132-J .
Gyárfás A., Jensen T., Stiebitz M. Sobre gráficos con clases de color fuertemente independientes // J. Graph Theory . - 2004. - T. 46 , núm. 1 . — P. 1–14 . -doi : 10.1002/ jgt.10165 .

Leonard Kwuida, Erkko Lehtonen. Sobre el Homomorfismo Orden de Posets Etiquetados // Orden . - Springer, 2011. - T. 28 , núm. 2 . — S. 251–265 . -doi : 10.1007 / s11083-010-9169-x . -arXiv : 0911.0200 . _
La conjetura de Tardif C. Hedetniemi, 40 años después // Graph Theory Notes of New York. - 2008. - T. 54 . — págs. 46–57 .
Dwight D., Sauer N. Celosías que surgen en las investigaciones categoriales de la conjetura de Hedetniemi // Matemáticas discretas. . - 1996. - T. 152 , núm. 1-3 . — S. 125–139 . - doi : 10.1016/0012-365X(94)00298-W .
daniel marx. ¿Puedes vencer a Treewidth? // Teoría de la Computación . - 2010. - T. 6 . — S. 85–112 . -doi : 10.4086 / toc.2010.v006a005 .
Cygan M., Fomin FV, Golovnev A., Kulikov AS, Mihajlin I., Pachocki J., Socała A. Límites estrechos para el homomorfismo de grafos y el isomorfismo de subgrafos. - SIAM , 2016. - ISBN 978-1-611974-33-1 .
Víctor Dalmau, Phokion G. Kolaitis, Moshe Y. Vardi. Satisfacción de restricciones, ancho de árbol acotado y lógica de variables finitas. - 2002. - S. 310-326. -doi : 10.1007/ 3-540-46135-3_21 .
Martín Grohe. La complejidad del homomorfismo y los problemas de satisfacción de restricciones vistos desde el otro lado // J. ACM . - 2007. - T. 54 , núm. 1 . -doi : 10.1145/ 1206035.1206036 .
Tomás Feder, Moshe Y. Vardi . La estructura computacional del SNP monádico monótono y la satisfacción de restricciones: un estudio a través del registro de datos y la teoría de grupos // SIAM J. Comput. . - 1998. - T. 28 , núm. 1 . — págs. 57–104 . -doi : 10.1137/ S0097539794266766 .

Libros generales

Pedro Cameron. Graficar homomorfismos, notas del grupo de estudio de combinatoria . — 2006.
Pavol Hell, Jaroslav Nesetzil. Grafos y Homomorfismos . - Oxford University Press, 2004. - V. 28 . — ISBN 0-19-852817-5 .
Geňa H., Tardif C. Homomorfismos de gráficos: estructura y simetría // Simetría de gráficos: métodos algebraicos y aplicaciones . - Springer, 1997. - S. 107-166. -doi : 10.1007 / 978-94-015-8937-6_4 .
Chris Godsil, Gordon Royle. 6. Homomorfismos // Teoría Algebraica de Grafos. - Springer-Verlag New York, 2001. - T. 207. - (Textos de Grado en Matemáticas). — ISBN 978-1-4613-0163-9 . -doi : 10.1007 / 978-1-4613-0163-9 .

En álgebra universal y sujeto a restricciones

Bodirsky M. Graph Homomorphisms and Universal Algebra, Course Notes . — 2007.
Pavol Hell, Jaroslav Nesetzil. Coloración, satisfacción de restricciones y complejidad // Computer Science Review. - 2008. - Vol. 2 , número. 2 . — S. 143–163 . -doi : 10.1016/ j.cosrev.2008.10.003 .

En teoría reticular y teoría de categorías

Brown R., Morris I., Shrimpton J., Wensley CD Gráficos de morfismos de gráficos // Electronic Journal of Combinatorics . - 2008. - T. 15 , núm. 1 . - S. A1 .
Gray CT La red de dígrafos . — 2014. ( Becas de investigación de vacaciones de AMSI , informe de investigación estudiantil supervisado por Brian Davey y Jane Pitkethly, Universidad La Trobe ).