Equivalencia homomórfica

En la teoría de grafos , una rama de las matemáticas , dos grafos G y H se denominan homomórficamente equivalentes si existe un homomorfismo de grafos.${\displaystyle f\colon G\to H}$y un homomorfismo de grafos${\displaystyle g\colon H\to G}$Un ejemplo de uso de esta noción es que cualesquiera dos núcleos de un grafo son homomórficamente equivalentes.

La equivalencia homomórfica también aparece en la teoría de bases de datos . Dado un esquema de base de datos , dos instancias I y J en él se denominan homomórficamente equivalentes si existe un homomorfismo de instancias.${\displaystyle f\colon I\to J}$y un homomorfismo de instancia${\displaystyle g\colon J\to I}$.

Decidir si dos grafos son homomórficamente equivalentes es NP-completo . ^{[ 1 ]}

De hecho, para cualquier categoría C , se puede definir la equivalencia homomórfica. Se utiliza en la teoría de categorías accesibles , donde la "universalidad débil" es lo mejor que se puede esperar en términos de clases de inyectividad; véase ^{[ 2 ].}