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 asigna vértices adyacentes a vértices adyacentes.
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, una red distributiva 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]
En este artículo, a menos que se indique lo contrario, los gráficos son finitos, no dirigidos y se permiten bucles , pero no se permiten aristas múltiples (bordes paralelos). Un homomorfismo gráfico [4] f de un gráfico a un gráfico , escrito
es una función desde hasta que conserva los bordes. Formalmente, implica , para todos los pares de vértices en . 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
La definición anterior se extiende a los 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 ) sea un arco de G .
Hay un homomorfismo inyectivo de G a H (es decir, uno que asigna distintos vértices en G a distintos vértices en H ) si y sólo si G es isomorfo a un subgrafo de H. Si un homomorfismo f : G → H es una biyección , y su función inversa f −1 también es un homomorfismo de grafos, entonces f es un isomorfismo de grafos. [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 doble cobertura 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 . La función que mapea v 0 y v 1 en la portada con v en el gráfico original es un homomorfismo y un mapa de cobertura.
El homeomorfismo de grafos es una noción diferente, que no está directamente relacionada con los homomorfismos. En términos generales, requiere inyectividad, pero permite asignar bordes a rutas (no solo a bordes). Los gráficos menores son una noción aún más relajada.
Dos gráficos G y H son homomórficamente equivalentes 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 tomando la mitad izquierda (respectivamente derecha) del gráfico de dominio y mapeándolo a solo un vértice en la izquierda (resp. .derecha) la mitad del gráfico de la imagen.
Una retracción es un homomorfismo r de un gráfico 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 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 subgrafo adecuado. [ 8] Cada gráfico G es homomórficamente equivalente a un núcleo único (hasta el isomorfismo), llamado 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. Todo grafo y todo grafo dirigido contiene su núcleo como retracto y como subgrafo inducido . [7]
Por ejemplo, todos los gráficos completos K n y todos los ciclos impares ( gráficos de ciclos 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 subgrafo) es homomórficamente equivalente a K 3 . Esto se debe a que, por un lado, una coloración triple 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 manera similar, todo gráfico bipartito que tenga al menos una arista es equivalente a K 2 . [11]
Una k -coloración , para algún número entero k , es una asignación de uno de k colores a cada vértice de un gráfico G de modo que los puntos finales de cada arista obtengan colores diferentes. Las k -coloraciones de G corresponden exactamente a homomorfismos de G al gráfico completo K k . [12] En efecto, los vértices de K k corresponden a los k colores, y dos colores son adyacentes como vértices de K k si y sólo si son diferentes. Por lo tanto, una función define un homomorfismo para K k si y sólo si asigna vértices adyacentes de G a diferentes colores (es decir, es una k -coloración). En particular, G es k -coloreable si y sólo si es K k -coloreable. [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 un gráfico 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]
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 una coloración H de G es una asignación de colores a los vértices de G tal que los vértices adyacentes obtengan colores compatibles. Muchas nociones de coloración de gráficos encajan en este patrón y pueden expresarse como homomorfismos de gráficos en diferentes familias de gráficos.Las coloraciones circulares se pueden definir utilizando homomorfismos en gráficos circulares completos , refinando la noción habitual de coloraciones. [15] La coloración fraccionaria y b -fold se puede definir utilizando homomorfismos en gráficos de Kneser . [16] Las coloraciones 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]
Otra conexión interesante tiene que ver con 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 orientaciones posibles para cada arista. Un ejemplo de 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 popular establece que para todo k , un gráfico dirigido G tiene un homomorfismo para T → k si y sólo si no admite ningún homomorfismo del camino dirigido P → k +1 . [21] Aquí P → n es el gráfico dirigido con vértices 1, 2,…, n y aristas de i a i + 1, para i = 1, 2,…, n − 1. Por lo tanto, un gráfico es k -colorable si y sólo si tiene una orientación que no admite homomorfismo de P → k +1 . Esta afirmación se puede reforzar ligeramente para decir que un gráfico es k -colorable si y sólo si alguna orientación no contiene un camino dirigido de longitud k (no P → k +1 como subgrafo). Este es el teorema de Gallai-Hasse-Roy-Vitaver .
Algunos problemas de programación se pueden modelar como una pregunta sobre cómo encontrar homomorfismos de gráficos. [22] [23] Como ejemplo, es posible que desee asignar cursos de taller a franjas horarias en un calendario para que dos cursos a los que asista 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 cualesquiera a los que asiste algún estudiante en común. Los intervalos de tiempo forman un gráfico H , con un borde entre dos intervalos cualesquiera que estén lo suficientemente distantes en el tiempo. Por ejemplo, si uno desea un cronograma semanal cíclico, de modo que cada estudiante reciba sus cursos de taller en días no consecutivos, entonces H sería el gráfico complementario de C 7 . Un homomorfismo gráfico de G a H es entonces un cronograma que asigna cursos a franjas horarias, como se especifica. [22] Para agregar un requisito que diga que, por ejemplo, ningún estudiante tiene cursos tanto el viernes como el lunes, basta con eliminar el margen correspondiente de H .
Un problema simple de asignación de frecuencias 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 utilizar canales con frecuencias alejadas. Si esta condición se aproxima con un umbral único para definir "geográficamente cerca" y "lejos", entonces una elección de canal válida nuevamente corresponde a un homomorfismo de gráfico. Se debe pasar de la gráfica de transmisores G , con aristas entre pares geográficamente cercanas, a la gráfica de canales H , con aristas entre canales muy alejadas. Si bien este modelo es bastante simplificado, admite cierta flexibilidad: se pueden agregar a los bordes de G pares de transmisores que no están cerca pero que podrían interferir debido a características geográficas . Aquellos que no se comuniquen al mismo tiempo podrán ser eliminados del mismo. De manera similar, los pares de canales que están muy separados pero que exhiben interferencia armónica se pueden eliminar del conjunto de bordes de H. [24]
En cada caso, estos modelos simplificados muestran muchas de las cuestiones que deben abordarse en la práctica. [25] Los problemas de satisfacción de restricciones , que generalizan problemas de homomorfismo de gráficos, 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 se hagan más realistas y prácticos.
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 única relación binaria (adyacencia) en el dominio (el conjunto de vértices). [26] [3] Según este punto de vista, los homomorfismos de tales estructuras son exactamente homomorfismos de 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 ofrece un primer paso concreto que ayuda a comprender 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 con respecto a H corresponde a una instancia de CSP con un solo tipo de restricción, [3] como sigue. Las variables son los vértices de G y el dominio de 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 arista o arco ( u , v ) de G corresponde entonces a la restricción (( u , v ), E( H )). Esta es una restricció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 al CSP es una evaluación que respeta todas las restricciones, por lo que es exactamente un homomorfismo de G a H.
Las composiciones de homomorfismos son homomorfismos. [13] En particular, la relación → en gráficos es transitiva (y reflexiva, trivialmente), por lo que es un preorden en gráficos. [27] Sea la clase de equivalencia de un gráfico G bajo equivalencia homomórfica [ G ]. La clase de equivalencia también se puede representar mediante el núcleo único en [ G ]. La relación → es un orden parcial sobre esas clases de equivalencia; define un poset . [28]
Sea G < H denota que hay un homomorfismo de G a H , pero no hay 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 en los casos triviales G = K 0 o K 1 ). [29] [30] Por ejemplo, entre dos gráficos completos cualesquiera (excepto K 0 , K 1 , K 2 ) 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 la reunión 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 irreductibles por unión de esta red son gráficos exactamente conectados . Esto se puede demostrar utilizando el hecho de que un homomorfismo asigna un gráfico conectado a un componente conectado del gráfico objetivo. [33] [34] Los elementos irreducibles por 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 sólo cuando uno de G o H también lo tiene. Identificar gráficas multiplicativas es el núcleo 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 gráficos es el producto teórico de categorías y el gráfico 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 cartesiana cerrada . 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 sobre 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 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 nuevamente es una categoría cartesiana cerrada . [39] [38]
Hay muchos gráficos incomparables con respecto al preorden de homomorfismo, es decir, pares de gráficos tales 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 es, de manera equivalente, el número impar más pequeño g para el cual 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 o igual que la circunferencia impar de H . [41]
Por otro lado, si G → H , entonces el número cromático de G es menor o igual que el número cromático 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 circunferencia 4 y 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, proporciona infinitos gráficos incomparables (una anticadena en el preorden del homomorfismo). [45] Otras propiedades, como la densidad del preorden del homomorfismo, se pueden demostrar utilizando dichas familias. [46] También son posibles construcciones de gráficos con valores grandes de número cromático y circunferencia, no solo circunferencias impares, pero son más complicadas (consulte Circunferencia y coloración de gráficos ).
Entre grafos 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 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 sólo si n es múltiplo de k . En particular, los gráficos de ciclo dirigido C → n con n primo son todos incomparables. [47]
En el problema de homomorfismo de grafos, una instancia es un par de grafos ( G , H ) y una solución es un homomorfismo de G a H. El problema de decisión general , que pregunta si existe 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 para restringir el lado izquierdo G son muy diferentes a los del lado derecho H , pero en cada caso se conoce o se conjetura una dicotomía (un límite claro entre los casos fáciles y difíciles).
El problema de homomorfismo con un gráfico fijo H en el lado derecho de cada instancia también se llama problema de coloración H. Cuando H es el gráfico completo K k , este es el problema de coloración del gráfico k , que se puede resolver en tiempo polinómico para k = 0, 1, 2 y, en caso contrario , NP-completo . [49] En particular, la colorabilidad K 2 de un gráfico G es equivalente a que G sea bipartito , lo que se puede probar en tiempo lineal. De manera más general, siempre que H es un gráfico bipartito, la colorabilidad H es equivalente a la colorabilidad K 2 (o la colorabilidad 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 grafos no dirigidos, ningún otro caso es manejable:
Esto también se conoce como teorema de dicotomía para 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 grafos 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 (o plantilla ) de restricción (finito ) Γ es un dominio finito y un conjunto finito de relaciones sobre este dominio. CSP( Γ ) es el problema de satisfacción de restricciones donde a las instancias solo se les permite usar restricciones en Γ .
Intuitivamente, esto significa que cada técnica algorítmica o resultado de complejidad que se aplica a los problemas de coloración H para gráficos dirigidos H se aplica igual de bien a los CSP generales. En particular, cabe preguntarse si el teorema de Hell-Nešetřil puede extenderse a grafos 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) sobre la dicotomía CSP, que establece que para cada lenguaje de restricción Γ , CSP( Γ ) es NP-completo o en P. [48] Esta conjetura fue demostrada de forma independiente en 2017 por Dmitry Zhuk y Andrei Bulatov, lo que lleva al siguiente corolario:
El problema de homomorfismo con un único 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 )|) , entonces polinomio en el tamaño del gráfico de entrada H . [56] En otras palabras, el problema es trivial 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, basta con suponer que el núcleo de G tiene un ancho de árbol como máximo k . Esto es válido incluso si se desconoce el núcleo. [57] [58]
El exponente en el | V ( H )| El algoritmo de tiempo O( k ) no se puede reducir significativamente: ningún algoritmo con tiempo de ejecución | V ( H )| o(tw( G ) /log tw( G )) existe, suponiendo 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] La ETH es una suposición no probada similar a P ≠ NP , pero más fuerte. Bajo el mismo supuesto, esencialmente no existen otras propiedades que puedan usarse para obtener algoritmos de tiempo polinomial. Esto se formaliza de la siguiente manera:
Uno puede preguntarse si el problema es al menos solucionable en un tiempo arbitrariamente altamente dependiente de G , pero con una dependencia polinómica fija 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 de homomorfismo en parametrizado por el tamaño (número de aristas) de G exhibe una dicotomía. Es manejable con parámetros fijos si los gráficos tienen núcleos de ancho de árbol acotado y W[1] -completo en caso contrario.
Las mismas afirmaciones se aplican de manera más general a los problemas de satisfacción de restricciones (o, en otras palabras, a las estructuras relacionales). El único supuesto necesario es que las restricciones pueden involucrar sólo un número acotado de variables (todas las relaciones son de alguna aridad acotada, 2 en el caso de las gráficas). El parámetro relevante es entonces el ancho del árbol del gráfico de restricción primaria . [59]
