Este team de redactores ha estado horas buscando la solución a tus preguntas, te compartimos la resolución por esto deseamos serte de mucha ayuda.
Solución:
Puede que me equivoque, pero a partir del ejemplo de matriz que encontró, puedo decir que usar matrices no es para encontrar el isomorfismo directamente, sino para verificar (también podemos decir probar) si el isomorfismo que encontramos es correcto o no. Porque en su ejemplo, observe que él/ella ya conoce el isomorfismo entre los gráficos como “(ABCDEFG) = (7 4 3 6 5 2 1)”.
En el caso del gráfico de Petersen (el gráfico de la izquierda), en realidad puedes encontrar un isomorfismo si puedes ser más sistemático. En primer lugar, digamos que $G$ es el gráfico de Petersen (a la izquierda) y $H$ es el gráfico de la derecha.
Existe un isomorfismo de gráfico $theta: G rightarrow H$ si y solo si para cualquier vértice adyacente $x,y in V(G)$, $theta(x)$ y $theta(y)$ es adyacentes en $H$ y para cualquier vértice no adyacente $u,t in V(G)$, $theta(u)$ y $theta(t)$ no son adyacentes en $H$.
Estoy escribiendo las definiciones porque tu respuesta no es correcta y puedes observarla usando la definición. Por ejemplo, asigne $b rightarrow 1$ y $g rightarrow 4$. En $H$, observe que los vértices $1$ y $4$ son adyacentes pero en $G$, los vértices $b$ y $g$ no son adyacentes. Entonces su mapeo no da un isomorfismo. En lugar de intentarlo al azar, puedes usar la simetría de los gráficos.
Comencemos con el vértice $a$ y digamos $theta(a) = 2$, eso es $a rightarrow 2$ (Después de este ejemplo, siempre usaré la representación $theta$). Luego observe que los vértices $b$, $d$ y $f$ son adyacentes a $a$. Digamos $theta(b) = 1$, $theta(f) = 3$ y $theta(d) = 5$. Desde aquí, te sugiero que elijas tu próximo vértice de uno de los vértices que ya has mapeado. Así que elijamos el vértice $d$ y encontremos sus vértices adyacentes. Esos son $a$, $g$ y $h$. Ya hemos asignado $a$, por lo que para $g$ y $h$, solo tenemos dos opciones (porque en $H$, $5$ está junto a $2$, $7$ y $8$ y ya hemos asignado $2$ ). Así que digamos $theta(g) = 7$ y $theta(h) = 8$.
Ahora para el resto, recuerda que tenemos $b rightarrow 1$ y $h rightarrow 8$. Observe que solo hay un vértice adyacente a $b$ y $h$ en $G$ (o $1$ y $8$ en $H$) y ese es $c$ en $G$ (o $10$ en $H ps Entonces podemos mapear $theta(c) = 10$. Después de esta parte, por un método similar, puedes encontrar otras asignaciones como la siguiente (con las anteriores): $$theta(a) = 2, theta(b) = 1, theta(c) = 10 , theta(d) = 5, theta(e) = 9, theta(f) = 3, theta(g) = 7, theta(h) = 8, theta( i) = 4, theta(k) = 6$$
Ahora podemos probar que $theta$ es un isomorfismo usando las matrices. Acabo de construir dos tablas como matrices y las pondré porque ya se ha explicado cómo se construyen las matrices en el ejemplo que ha encontrado. En este caso, la primera matriz tendrá una indexación como $a,b,c,d,e,f,g,h,i,k$ y la segunda matriz tendrá una indexación como la que encontramos en el isomorfismo, es decir, $2,1 ,10,5,9,3,7,8,4,6$. De acuerdo con estas indexaciones, las matrices serán las siguientes y son las mismas si las reconstruyes desde el principio:
Como son lo mismo, podemos concluir que $theta: G rightarrow H$ es un isomorfismo gráfico.
Su mapeo propuesto no es un isomorfismo porque envía $b$ a $1$ y $c$ a $5$ y hay un borde entre $b$ y $c$ pero no hay un borde entre $1$ y $5$.
Por lo general, la mejor manera de saber si dos gráficos son isomorfos es encontrando las propiedades estructurales de los gráficos. Informalmente, una propiedad estructural es aquella que se puede definir independientemente de las etiquetas de los vértices. Por ejemplo, si un gráfico contiene un ciclo de longitud $k$ y el otro no, los gráficos no pueden ser isomorfos. Si no puede encontrar una propiedad estructural en un gráfico que no esté presente en el otro, puede intentar descubrir un isomorfismo alineando las características estructurales de los dos gráficos.
Ahora concentrémonos en tus gráficos. Llame al gráfico de la izquierda $X$ y al de la derecha $Y$. Primero, observamos que en ambos gráficos, cada vértice tiene un grado exactamente $3$ (es decir, los gráficos son $3$-regulares), pero esto no nos ayuda a distinguir los gráficos.
Mirando $X$, vemos que hay dos subgrafos cíclicos $A = af, k, i, b$ y $B = d, h, c, e, g$ que contienen $5$ vértices cada uno. Ahora, $A$ tiene la propiedad de que cada vértice en $A$ está conectado con exactamente otros dos vértices en $A$ y exactamente uno en $B$. Una afirmación similar es válida para $B$.
Nuestro objetivo es encontrar análogos de $A$ y $B$ en $H$. Si no existe ninguno, entonces los gráficos no son isomorfos. Si existen, intentaremos usarlos para encontrar un isomorfismo.
Mirando $H$ por un momento, descubrimos los subgrafos cíclicos $A’ = 2, 3, 9, 10, 1$ y $B’ = 5, 7, 4, 6, 8 ps Si asumimos que $A$ se asigna a $A’$, entonces suponga que nuestra asignación $phi$ envía $a$ a $2$. Entonces $phi(d) = 5$. Continuando más, obtenemos el mapeo $phi$ definido por beginalign a & mapsto 2 \ f & mapsto 3 \ k & mapsto 9 \ i & mapsto 10 \ b & mapsto 1 \ d & mapsto 5 \ h & mapsto 7 \ c & mapsto 4 \ e & mapsto 6 \ g & mapsto 8 endalign
Está claro que $phi$ es una biyección, por lo que podemos verificar que $phi$ es un isomorfismo comprobando que
- cuando se restringe a $A$, es un isomorfismo a $A’$,
- cuando se restringe a $B$, es un isomorfismo a $B’$ y
- que asigna los bordes entre $A$ y $B$ a los bordes entre $A’$ y $B’$.
Es un poco tedioso, pero no difícil, verificar que se cumplan las tres propiedades. Si lo desea, esto se puede hacer calculando la matriz de adyacencia de la imagen de $X$ bajo $phi$ y observando que es igual a la matriz de adyacencia de $Y$.
Valoraciones y reseñas
Puedes añadir valor a nuestro contenido colaborando tu veteranía en las críticas.