En el campo matemático de la teoría de grafos , un homomorfismo de grafos es una aplicación entre dos grafos que respeta su estructura. Más concretamente, es una función entre los conjuntos de vértices de dos grafos que aplica vértices adyacentes a vértices adyacentes.
Los homomorfismos generalizan varias nociones de coloración de grafos 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 los homomorfismos puedan ser compuestos conduce a ricas estructuras algebraicas: un preorden en grafos, una red distributiva y una categoría (una para grafos no dirigidos y otra para grafos dirigidos). [2] La complejidad computacional de encontrar un homomorfismo entre grafos dados es prohibitiva en general, pero se sabe mucho sobre casos especiales que se pueden resolver en tiempo polinomial . Los límites entre casos manejables e intratables han sido un área activa de investigación. [3]
En este artículo, a menos que se indique lo contrario, los grafos son grafos finitos, no dirigidos con bucles permitidos, pero no se permiten aristas múltiples (aristas paralelas). Un homomorfismo de grafos [4] f de un grafo a un grafo , escrito
es una función de a que conserva las aristas. 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 -coloreable . Esto a menudo se denota simplemente como
La definición anterior se extiende a los grafos dirigidos. Entonces, para un homomorfismo f : G → H , ( f ( u ), f ( v )) es un arco (arista dirigida) de H siempre que ( u , v ) sea un arco de G .
Existe un homomorfismo inyectivo de G a H (es decir, uno que asigna vértices distintos en G a vértices distintos en H ) si y solo 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 grafo, entonces f es un isomorfismo de grafo. [5]
Los mapas de recubrimiento son un tipo especial de homomorfismos que reflejan la definición y muchas propiedades de los mapas de recubrimiento 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 el doble recubrimiento bipartito , formado a partir de un grafo 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 asigna v 0 y v 1 en el recubrimiento a v en el grafo original es un homomorfismo y un mapa de recubrimiento.
El homeomorfismo de grafos es un concepto diferente, no relacionado directamente con los homomorfismos. En términos generales, requiere inyectividad, pero permite mapear aristas a caminos (no solo a aristas). Los menores de grafos son un concepto aún más relajado.
Dos grafos G y H son homomórficamente equivalentes si G → H y H → G . [4] Las funciones no son necesariamente sobreyectivas ni inyectivas. Por ejemplo, los grafos bipartitos completos K 2,2 y K 3,3 son homomórficamente equivalentes: cada función puede definirse como la que toma la mitad izquierda (o derecha) del grafo del dominio y la asigna a un solo vértice en la mitad izquierda (o derecha) del grafo de la imagen.
Una retracción es un homomorfismo r de un grafo 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 denomina retracción de G . [7]
Un núcleo es un grafo sin homomorfismo con ningún subgrafo propio. De manera equivalente, un núcleo se puede definir como un grafo que no se retrae con ningún subgrafo propio. [8] Cada grafo G es homomórficamente equivalente a un núcleo único (salvo isomorfismo), llamado el núcleo de G . [9] Cabe destacar que esto no es cierto en general para grafos infinitos. [10] Sin embargo, las mismas definiciones se aplican a los grafos dirigidos y un grafo dirigido también es equivalente a un núcleo único. Cada grafo y cada grafo dirigido contiene su núcleo como una retracción y como un subgrafo inducido . [7]
Por ejemplo, todos los grafos completos K n y todos los ciclos impares ( grafos de ciclo de longitud impar) son núcleos. Todo grafo 3-coloreable G que contiene un triángulo (es decir, tiene el grafo completo K 3 como subgrafo) es homomórficamente equivalente a K 3 . Esto se debe a que, por un lado, una 3-coloración 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 grafo G de ese tipo . De manera similar, todo grafo bipartito que tenga al menos una arista es equivalente a K 2 . [11]
Una k -coloración , para algún entero k , es una asignación de uno de k colores a cada vértice de un grafo 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 grafo 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 colores diferentes (es decir, es una k -coloración). En particular, G es k -coloreable si y solo 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 grafo 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ático de un grafo (el menor k para el cual es k -coloreable). [14]
Los homomorfismos generales también pueden considerarse como un tipo de coloración: si los vértices de un grafo fijo H son los colores disponibles y las aristas 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 modo que los vértices adyacentes obtengan colores compatibles. Muchas nociones de coloración de grafos encajan en este patrón y pueden expresarse como homomorfismos de grafos en diferentes familias de grafos. Las coloraciones circulares pueden definirse utilizando homomorfismos en grafos circulares completos , refinando la noción habitual de coloraciones. [15] La coloración fraccionaria y b -fold puede definirse utilizando homomorfismos en grafos de Kneser . [16] Las coloraciones T corresponden a homomorfismos en ciertos grafos infinitos. [17] Una coloración orientada de un grafo dirigido es un homomorfismo en cualquier grafo 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 se refiere a las orientaciones de los grafos. Una orientación de un grafo no dirigido G es cualquier grafo dirigido obtenido eligiendo una de las dos orientaciones posibles para cada arista. Un ejemplo de una orientación del grafo 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 grafos G y H produce un homomorfismo entre los grafos no dirigidos G y H , simplemente ignorando las orientaciones. Por otro lado, dado un homomorfismo G → H entre grafos no dirigidos, cualquier orientación H → de H puede retrotraerse a una orientación G → de G de modo que G → tenga un homomorfismo con H → . Por lo tanto, un grafo G es k -coloreable (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 grafo dirigido G tiene un homomorfismo a T → k si y solo si no admite homomorfismo desde el camino dirigido P → k +1 . [21] Aquí P → n es el grafo dirigido con vértices 1, 2, …, n y aristas desde i hasta i + 1, para i = 1, 2, …, n − 1. Por lo tanto, un grafo es k -coloreable si y solo si tiene una orientación que no admite homomorfismo desde P → k +1 . Esta afirmación se puede reforzar ligeramente para decir que un grafo es k -coloreable si y solo si alguna orientación no contiene un camino dirigido de longitud k (ningún P → k +1 como subgrafo). Este es el teorema de Gallai–Hasse–Roy–Vitaver .
Algunos problemas de programación pueden modelarse 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 de modo 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 grafo G , con una arista entre dos cursos cualesquiera a los que asista algún estudiante en común. Las franjas horarias forman un grafo H , con una arista entre dos franjas horarias cualesquiera que estén lo suficientemente distantes en el tiempo. Por ejemplo, si uno quiere un programa cíclico, semanal, de modo que cada estudiante obtenga sus cursos de taller en días no consecutivos, entonces H sería el grafo complementario de C 7 . Un homomorfismo de grafo de G a H es entonces un programa 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 la arista correspondiente de H .
Un problema simple de asignación de frecuencias puede especificarse de la siguiente manera: una cantidad de transmisores en una red inalámbrica debe 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 que estén muy separadas. Si esta condición se aproxima con un único umbral para definir 'geográficamente cerca' y 'muy separado', entonces una elección de canal válida corresponde nuevamente a un homomorfismo de grafo. Debería ir del grafo de transmisores G , con bordes entre pares que están geográficamente cerca, al grafo de canales H , con bordes entre canales que están muy separados. Si bien este modelo es bastante simplificado, admite cierta flexibilidad: los pares de transmisores que no están cerca pero que podrían interferir debido a características geográficas pueden agregarse a los bordes de G . Aquellos que no se comunican al mismo tiempo pueden eliminarse de él. De manera similar, los pares de canales que están muy separados pero que exhiben interferencia armónica pueden eliminarse del conjunto de bordes de H . [24]
En cada caso, estos modelos simplificados muestran muchos de los problemas que deben abordarse en la práctica. [25] Los problemas de satisfacción de restricciones , que generalizan los 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.
Los grafos y los grafos dirigidos pueden considerarse un caso especial de la noción mucho más general llamada estructuras relacionales (definidas como un conjunto con una tupla de relaciones en él). Los grafos dirigidos son estructuras con una única relación binaria (adyacencia) en el dominio (el conjunto de vértices). [26] [3] Desde 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 de restricciones (CSP). El caso de los grafos proporciona un primer paso concreto que ayuda a comprender los CSP más complicados. Muchos métodos algorítmicos para encontrar homomorfismos de grafos, como el backtracking , la propagación de restricciones y la búsqueda local , se aplican a todos los CSP. [3]
Para los grafos 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 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 es 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 mapear 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 para el 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 grafos es transitiva (y reflexiva, trivialmente), por lo que es un preorden en grafos. [27] Sea la clase de equivalencia de un grafo G bajo equivalencia homomórfica [ G ]. La clase de equivalencia también puede representarse por el núcleo único en [ G ]. La relación → es un orden parcial en esas clases de equivalencia; define un conjunto parcial . [28]
Sea G < H que hay un homomorfismo de G a H , pero no de H a G . La relación → es de orden denso , lo que significa que para todos los grafos (no dirigidos) G , H tales que G < H , hay un grafo K tal que G < K < H (esto se cumple excepto para los casos triviales G = K 0 o K 1 ). [29] [30] Por ejemplo, entre dos grafos completos cualesquiera (excepto K 0 , K 1 , K 2 ) hay infinitos grafos completos circulares , correspondientes a números racionales entre números naturales. [31]
El conjunto de clases de equivalencia de grafos 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 tensorial [ G × H ] (la elección de los grafos G y H que representan las clases de equivalencia [ G ] y [ H ] no importa). [32] Los elementos irreducibles por unión de esta red son grafos exactamente conexos . Esto se puede demostrar usando el hecho de que un homomorfismo mapea un grafo conexo en un componente conexo del grafo objetivo. [33] [34] Los elementos irreducibles por encuentro de esta red son exactamente los grafos multiplicativos . Estos son los grafos 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áficos multiplicativos es el núcleo de la conjetura de Hedetniemi . [35] [36]
Los homomorfismos de grafos también forman una categoría , con grafos como objetos y homomorfismos como flechas. [37] El objeto inicial es el grafo vacío, mientras que el objeto terminal es el grafo con un vértice y un bucle en ese vértice. El producto tensorial de grafos es el producto de la categoría teórica y el grafo exponencial es el objeto exponencial para esta categoría. [36] [38] Dado que estas dos operaciones siempre están definidas, la categoría de grafos es una categoría cartesiana cerrada . Por la misma razón, la red de clases de equivalencia de grafos bajo homomorfismos es de hecho un álgebra de Heyting . [36] [38]
Para los grafos dirigidos se aplican las mismas definiciones. En particular, → es un orden parcial en clases de equivalencia de grafos dirigidos. Es distinto del orden → en clases de equivalencia de grafos no dirigidos, pero lo contiene como un suborden. Esto se debe a que cada grafo no dirigido puede considerarse como un grafo 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 grafos 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 grafos dirigidos como objetos y homomorfismos como flechas, que nuevamente es una categoría cartesiana cerrada . [39] [38]
Existen muchos grafos incomparables con respecto al preorden de homomorfismo, es decir, pares de grafos tales que ninguno admite un homomorfismo en el otro. [40] Una forma de construirlos es considerar la circunferencia impar de un grafo G , la longitud de su ciclo de longitud impar más corto. La circunferencia impar es, equivalentemente, el número impar más pequeño g para el cual existe un homomorfismo desde el grafo del ciclo en g vértices hasta 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 otra parte, 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 grafo de Grötzsch es 4-cromático y libre de triángulos (tiene una circunferencia 4 y una circunferencia impar 5), [42] por lo que es incomparable con el grafo triangular K 3 .
Ejemplos de grafos con valores arbitrariamente grandes de circunferencia impar y número cromático son los grafos de Kneser [43] y los mycielskianos generalizados . [44] Una secuencia de tales grafos, con valores simultáneamente crecientes de ambos parámetros, da infinitos grafos incomparables (una anticadena en el preorden del homomorfismo). [45] Otras propiedades, como la densidad del preorden del homomorfismo, se pueden demostrar utilizando tales familias. [46] Las construcciones de grafos con valores grandes 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 grafos ).
Entre los grafos dirigidos, es mucho más fácil encontrar pares incomparables. Por ejemplo, considere los grafos de ciclo dirigidos 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. Existe 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 grafos de ciclo dirigidos C → n con n primo son todos incomparables. [47]
En el problema del 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 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 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 grafo fijo H en el lado derecho de cada instancia también se denomina problema de coloración de H. Cuando H es el grafo completo K k , este es el problema de coloración de grafos 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 -colorabilidad de un grafo G es equivalente a que G sea bipartito , lo que se puede probar en tiempo lineal. De manera más general, siempre que H sea un grafo bipartito, la H -colorabilidad es equivalente a la K 2 -colorabilidad (o K 0 / K 1 -colorabilidad cuando H está vacío/sin aristas), por lo tanto, 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 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 P, sin casos intermedios . Para 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 grafos dirigidos son tan generales y diversos como los CSP con cualquier otro tipo de restricciones. [54] [55] Formalmente, un lenguaje de restricciones (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 solo se permite a las instancias usar restricciones en Γ .
Intuitivamente, esto significa que cada técnica algorítmica o resultado de complejidad que se aplica a problemas de coloración H para grafos dirigidos H se aplica igualmente a CSP generales. En particular, uno puede preguntarse si el teorema de Hell–Nešetřil se puede extender a grafos dirigidos. Por 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 en 2017 de forma independiente por Dmitry Zhuk y Andrei Bulatov, lo que llevó al siguiente corolario:
El problema del homomorfismo con un único grafo fijo G en el lado izquierdo de las instancias de entrada se puede resolver por fuerza bruta en el tiempo | V ( H )| O(| V ( G )|) , por lo que es polinomial en el tamaño del grafo de entrada H . [56] En otras palabras, el problema es trivialmente en P para grafos 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 treewidth , una medida de cuán parecido a un árbol es el grafo. Para un grafo G con un ancho de árbol como máximo k y un grafo H , el problema del homomorfismo se puede resolver en tiempo | V ( H )| O( k ) con un enfoque de programación dinámica estándar . De hecho, es suficiente suponer que el núcleo de G tiene un ancho de árbol como máximo k . Esto se cumple incluso si no se conoce el núcleo. [57] [58]
El exponente en el algoritmo de tiempo | V ( H )| O( k ) no se puede reducir significativamente: no existe ningún algoritmo con tiempo de ejecución | V ( H )| o(tw( G ) /log tw( G )) , suponiendo la hipótesis de 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 la misma suposición, esencialmente tampoco hay otras propiedades que se puedan usar para obtener algoritmos de tiempo polinomial. Esto se formaliza de la siguiente manera:
Se puede preguntar 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 grafos 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 en parametrizado por el tamaño (número de aristas) de G exhibe una dicotomía. Es manejable con parámetros fijos si los grafos en tienen 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, en otras palabras, para las estructuras relacionales). La única suposición necesaria es que las restricciones pueden involucrar solo un número limitado de variables (todas las relaciones tienen cierta aridad limitada, 2 en el caso de los grafos). El parámetro relevante es entonces el ancho del árbol del grafo de restricción primaria . [59]
