Equivalencia homomórfica

En 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 grafo y un homomorfismo de grafo . Un ejemplo de uso de esta noción es que dos núcleos cualesquiera de un grafo son homomórficamente equivalentes. ${\displaystyle f\colon G\to H}$ ${\displaystyle g\colon H\to G}$

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 instancia y un homomorfismo de instancia . ${\displaystyle f\colon I\to J}$ ${\displaystyle g\colon J\to I}$

Decidir si dos gráficos 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]

Referencias

1. Flum, J.; Grohe, M. (1 de mayo de 2006). Teoría de la complejidad parametrizada . Springer Science & Business Media. pág. 330. ISBN 978-3-540-29953-0.
2. Adamek y Rosicky, "Categorías localmente presentables y accesibles".