¿Cuáles son las diferencias clave entre estos tres términos isomorfismo, automorfismo y homomorfismo en lenguaje simple y laico y por qué hacemos isomorfismo, automorfismo y homomorfismo?
fuente
¿Cuáles son las diferencias clave entre estos tres términos isomorfismo, automorfismo y homomorfismo en lenguaje simple y laico y por qué hacemos isomorfismo, automorfismo y homomorfismo?
El isomorfismo formaliza la noción de gráficos iguales . Por ejemplo, en esta figura, ve tres gráficos isomórficos
No es difícil encontrar tal biyección para cada par de gráficos en la imagen.
y como pueden ver los gráficos "se ven" bastante simétricos. Eso es precisamente porque tiene "muchos" automorfismos del tipo descrito.
Los homomorfismos de grafos generalmente no son estudiados por laicos y tienen más o menos propósitos teóricos. Por ejemplo, están estrechamente relacionados con la noción de coloración de vértices. Ver también Conjetura de Hadwiger
Ahora un isomorfismo gráfico es un homomorfismo biyectivo, lo que significa que es inverso también es un homomorfismo. Si dos gráficos son isomorfos, entonces son esencialmente el mismo gráfico, solo con un re-etiquetado de los vértices. El problema de determinar si dos gráficas son isomorfas entre sí es un problema importante en la teoría de la complejidad.
Finalmente, un automorfismo es isomorfismo de un gráfico a sí mismo.
fuente