Diferencia entre el homomorfismo gráfico y el isomorfismo gráfico

Question

Aún no entiendo en qué se diferencian el isomorfismo gráfico y el homomorfismo.

¿Alguien puede mostrarme dos gráficos que sean homomórficos, pero no isomórficos?

También, Wikipedia dice que cuando la función y la función inversa son ambas homomórficas, dos gráficos son isomórficos. ¿Cómo es eso?

Answer 1

Un homomorfismo puede ser de un gráfico más grande a uno más pequeño. Aquí hay un ejemplo concreto:

                     a  
                    / \  
                   /   \                        0   
                  b     c                      / \  
                  |     |                     /   \  
                  d-----e                    1-----2  
                     G                          H

El mapa $h:V(G) \to V(H)$ dado por $h(a)=h(d)=0$ , $h(b)=h(c)=1$ y $h(e)=2$ es un homomorfismo gráfico: envía bordes $ab,db$ y $ac$ a $01$ , $ce$ a $12$ y $de$ a $02$ . Claramente, sin embargo, $G$ y $H$ no son isomórficas, ya que ni siquiera tienen el mismo número de vértices.

Obsérvese que, en general, si $h:G \to V$ es un isomorfismo gráfico, entonces $h(u)h(v)$ es una ventaja de $H$ si y sólo si $uv$ es una ventaja de $G$ . Si $h$ es simplemente un homomorfismo gráfico, sin embargo, $h(u)h(v)$ puede ser una ventaja de $H$ incluso si $uv$ no es una ventaja de $G$ . Por lo tanto, si $K$ es el gráfico que se muestra a continuación, el mapa que toma $a,b,c,d$ y $e$ a $0,1,2,3$ y $4$ respectivamente, es un homomorfismo pero no un isomorfismo.

                         0  
                        / \  
                       /   \   
                      1-----2  
                      |     |  
                      3-----4  
                         K

Answer 2

Parece que hay diferentes nociones de estructura que preservan los mapas entre los gráficos. Está claro que un isomorfismo entre gráficos es una bijección entre los conjuntos de vértices que preserva tanto los bordes como los no bordes.

Para lo siguiente estoy hablando de gráficos no dirigidos sin bordes dobles o bucles.

La noción habitual de homomorfismo es un mapa que conserva los bordes, pero no necesariamente los no bordes. De ello se deduce que un homomorfismo puede mapear dos vértices diferentes a un solo vértice si los dos vértices del dominio no forman un borde. Por ejemplo, el gráfico con dos vértices y sin borde puede ser mapeado homomórficamente al gráfico que tiene un solo vértice.

Los mapas que conservan tanto los bordes como los no bordes (en el sentido de que dos vértices diferentes que no forman un borde son mapeados a dos vértices diferentes que no forman un borde) son sólo incrustaciones de gráficos. Son 1-1 pero no necesariamente sobre.

Otra noción interesante de mapa que preserva la estructura entre los gráficos sería la de un mapa modular, un mapa que preserva tanto los bordes como los no bordes, a menos que se identifiquen dos vértices distintos. Los mapas modulares se muestran en descomposiciones modulares de gráficos.

Answer 3

Considere los siguientes dos gráficos:

  0 --- 1
                 0 --- 1
  2 --- 3
     G              H

Tenga en cuenta que la función $f : \{ 0,1,2,3 \} \to \{ 0,1 \}$ definido por $f (0) = f(2) = 0$ y $f(2) = f(3) = 1$ es un homomorfismo gráfico de $G$ en $H$ . Los únicos bordes de $G$ son $\{0,1\}$ y $\{2,3\}$ y claramente $\{f(0),f(1)\} = \{0,1\} = \{f(2),f(3)\}$ son bordes (¡el mismo borde!) de $H$ .

Tenga en cuenta que la función $g: \{ 0,1 \} \to \{ 0,1,2,3 \}$ definido por $g(0) = 0$ y $g(1) = 1$ es también un homomorfismo gráfico de $H$ en $G$ . El único borde de $H$ es $\{0,1\}$ y claramente $\{g(0),g(1)\} = \{0,1\}$ es una ventaja de $G$ .

Por lo tanto $G$ y $H$ son homomórficamente equivalentes, tal como se definen en la Página de Wikipedia . De hecho, $H$ es sólo una retracción de $G$ con la función $f$ por encima de una retracción. Sin embargo, no son isomórficas, ya que sus conjuntos subyacentes tienen diferentes tamaños.