¿Cómo hallar un isomorfismo mediante matrices?

Question

Estoy buscando una forma fácil de dar un isomorfismo entre dos grafos ya que nunca lo veo con mis pares de ojos y he encontrado la siguiente respuesta: Este

Intenté aplicarlo en una situación en la que los vértices tienen el mismo grado y las cosas se complicaron y fue más difícil aplicarlo cuando los vértices tienen grados diferentes. Aquí es donde traté de aplicarlo y me dieron una respuesta, pero estoy seguro de que mi respuesta es incorrecta, ya que se basa sólo en la comparación de las dos matrices y diciendo lo que yo pensaba que la respuesta era. Así que mi respuesta es: $ k=8, a=2, b=1, e=7,\ h=6, g=4, d=3, f=9, i=10, c=5 $

¿Hay alguna forma de hacerlo mejor o alguien puede dar una explicación de cómo se puede aplicar la forma matricial para dar el isomorfismo en este caso?

Answer 1

Puede que me equivoque pero por el ejemplo de la matriz que encontraste, puedo decir que el uso de matrices no es para encontrar el isomorfismo directamente sino para comprobar (podemos decir probar también) si el isomorfismo que encontramos es correcto o no. Porque en tu ejemplo, fíjate que él/ella ya conoce el isomorfismo entre grafos como "(A B C D E F G) = (7 4 3 6 5 2 1)".

En el caso del gráfico de Petersen (el gráfico de la izquierda), en realidad se puede encontrar un isomorfismo si se es más sistemático. En primer lugar, digamos $G$ es el gráfico de Petersen (a la izquierda) y $H$ es el gráfico de la derecha.

Existe un isomorfismo de grafos $\theta: G \rightarrow H$ sólo si para cualquier vértice adyacente $x,y \in V(G)$ , $\theta(x)$ y $\theta(y)$ es adyacente en $H$ y para cualquier vértice no adyacente $u,t \in V(G)$ , $\theta(u)$ y $\theta(t)$ no son adyacentes en $H$ .

Escribo las definiciones porque tu respuesta no es correcta y puedes observarla utilizando la definición. Por ejemplo, mapeas $b \rightarrow 1$ y $g \rightarrow 4$ . En $H$ Obsérvese que los vértices $1$ y $4$ son adyacentes pero en $G$ vértices $b$ y $g$ no son adyacentes. Así que tu mapeo no da un isomorfismo. En vez de intentarlo al azar, puedes usar la simetría de los grafos.

Empecemos por el vértice $a$ y digamos $\theta(a) = 2$ es decir $a \rightarrow 2$ (Después de este ejemplo, utilizaré siempre $\theta$ representación). A continuación, observe que los vértices $b$ , $d$ y $f$ son adyacentes a $a$ . Digamos que $\theta(b) = 1$ , $\theta(f) = 3$ y $\theta(d) = 5$ . A partir de aquí, te sugiero que elijas tu siguiente vértice de uno de los vértices que ya has mapeado. Así que vamos a elegir el vértice $d$ y encontrar sus vértices adyacentes. Estos son $a$ , $g$ y $h$ . Ya hemos trazado $a$ por lo que para $g$ y $h$ sólo tenemos dos opciones (porque en $H$ , $5$ es adyacente a $2$ , $7$ y $8$ y hemos mapeado $2$ ya). Digamos que $\theta(g) = 7$ y $\theta(h) = 8$ .

Ahora para el resto, recuerde que tenemos $b \rightarrow 1$ y $h \rightarrow 8$ . Obsérvese que sólo hay un vértice adyacente a ambos $b$ y $h$ en $G$ (o $1$ y $8$ en $H$ ) y que es $c$ en $G$ (o $10$ en $H$ ). Así que podemos asignar $\theta(c) = 10$ . Después de esta parte, por un método similar, se pueden encontrar otros mapeos como los siguientes (con los 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 demostrar que $\theta$ es un isomorfismo usando las matrices. Acabo de construir dos tablas como matrices y las voy a poner porque cómo se construyen las matrices ya se ha explicado en el ejemplo que has encontrado. En este caso, primera matriz tendrá indexación como $a,b,c,d,e,f,g,h,i,k$ y la segunda matriz tendrá la indexación que encontramos en el isomorfismo, es decir, $2,1,10,5,9,3,7,8,4,6$ . Según esta indexación, las matrices serán como las siguientes y son las mismas si las reconstruyes desde el principio:

Como son iguales, podemos concluir que $\theta: G \rightarrow H$ es un isomorfismo de grafos.

Answer 2

El mapeo que propones 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$ .

Normalmente, la mejor manera de saber si dos grafos son isomorfos es encontrar propiedades estructurales de los grafos. Informalmente, una propiedad estructural es aquella que puede definirse independientemente de las etiquetas de los vértices. Por ejemplo, si un grafo contiene un ciclo de longitud $k$ y el otro no, los grafos no pueden ser isomorfos. Si no puedes encontrar una propiedad estructural en un grafo que no esté presente en el otro, entonces puedes intentar descubrir un isomorfismo alineando las características estructurales de los dos grafos.

Ahora centrémonos en sus gráficos. Llama al gráfico de la izquierda $X$ y el de la derecha $Y$ . En primer lugar, observamos que en ambos grafos, cada vértice tiene grado exactamente $3$ (es decir, los gráficos son $3$ -regular), pero esto no nos ayuda a distinguir los gráficos.

Mirando a $X$ vemos que hay dos subgrafos cíclicos $A = \{a f, k, i, b\}$ y $B = \{d, h, c, e, g\}$ que contiene $5$ vértices cada uno. Ahora, $A$ tiene la propiedad de que cada vértice de $A$ está conectado exactamente con otros dos vértices de $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, los grafos no son isomorfos. Si existen, intentaremos utilizarlos para encontrar un isomorfismo.

Mirando a $H$ por un momento, descubrimos los subgrafos cíclicos $A' = \{2, 3, 9, 10, 1\}$ y $B' = \{5, 7, 4, 6, 8\}$ . Si suponemos que $A$ mapas a $A'$ entonces supongamos que nuestro mapeo $\phi$ envía $a$ a $2$ . Entonces $\phi(d) = 5$ . Continuando, obtenemos el mapeo $\phi$ definido por \begin{align} 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 \end{align}

Está claro que $\phi$ es una biyección, por lo que podemos verificar que $\phi$ es un isomorfismo comprobando que

1. cuando se limita a $A$ es un isomorfismo de $A'$ ,
2. cuando se limita a $B$ es un isomorfismo de $B'$ y
3. que mapea los bordes entre $A$ y $B$ a los bordes entre $A'$ y $B'$ .

Es un poco tedioso, pero no difícil, comprobar que se cumplen estas tres propiedades. Si se desea, puede hacerse calculando la matriz de adyacencia de la imagen de $X$ en $\phi$ y observando y es igual a la matriz de adyacencia de $Y$ .