[manooooh]

Hola!

Tenemos 2 grafos. Comprobamos que son isomorfos a través de sus matrices de adyacencia. Y coinciden.

Ahora queremos averiguar si existe otro isomorfismo. Para saber si existe otro isomorfismo distinto (ordenamiento de vértices tal que las matrices sigan siendo iguales), ¿es necesario que dos filas sean iguales (o dos columnas, ya que la matriz de adyacencia es siempre simétrica)? En ese caso tendríamos otro isomorfismo (otra función biyectiva).

¿Y también es suficiente?

O sea mi pregunta viene a raíz de un ejercicio que daban 2 grafos y pedía elegir una opción y decía "Existe un isomorfismo" o "Existe más de un isomorfismo". Y pensando un poco me di cuenta que si la matriz tenía dos filas (columnas) iguales, al intercambiarlas de lugar (tanto las filas como las columnas), la matriz seguía siendo la misma, por ende encontramos otro isomorfismo. Pero no sé si 1) Esto está bien pensado, 2) Alcanza para decir que es otro isomorfismo, 3) Existe otra manera sencilla de decir si el isomorfismo es único o no.

¿Pueden contestarme 1), 2) y 3), por favor?

Gracias!!
Saludos

[Luis Fuentes]

Hola

Tenemos 2 grafos. Comprobamos que son isomorfos a través de sus matrices de adyacencia. Y coinciden.

Ahora queremos averiguar si existe otro isomorfismo.

Vaya por delante que analizar si tienes dos isomorfismos de grafos distintos entre dos grafos equivale a estudiar si cualquiera de ellos tiene automorfismos. Ya que si tienes:

\( f_1:V\to V',\quad f_2:V\to V' \)

isomorfismos de grados, \( f_1^{-1}\circ f_2 \) es un automofismo del primero. Y recíprocamente si tienes el isomorfismo \( f_1:V\to V' \) y un automorfismo \( g:V\to V \) no trivial, entonces \( f_1\circ g \) es otro isomorfismo entre los dos grafos.

Para saber si existe otro isomorfismo distinto (ordenamiento de vértices tal que las matrices sigan siendo iguales), ¿es necesario que dos filas sean iguales (o dos columnas, ya que la matriz de adyacencia es siempre simétrica)? En ese caso tendríamos otro isomorfismo (otra función biyectiva).

No, no es necesario. Por ejemplo si tienes el grafo \( \{1,2,3,4\} \) con aristas \( 1-2 \) y \( 3-4 \), sus matriz de adyacencia es:

\( \begin{pmatrix}0&1&0&0\\ 1&0&0&0\\ 0&0&0&1\\ 0&0&1&0 \\\end{pmatrix} \)

no tiene pares de filas iguales. Pero si tiene automorfismo: puedes intercambiar los vértices \( 1,2 \) ó los vértices \( 3,4 \); o llevar el par \( 1,2 \) en el par \( 3,4 \).

¿Y también es suficiente?

Suficiente si. Desde luego si tienes dos filas iguales puedes intercambiarlas y tienes un automorfismo no trivial.

O sea mi pregunta viene a raíz de un ejercicio que daban 2 grafos y pedía elegir una opción y decía "Existe un isomorfismo" o "Existe más de un isomorfismo". Y pensando un poco me di cuenta que si la matriz tenía dos filas (columnas) iguales, al intercambiarlas de lugar (tanto las filas como las columnas), la matriz seguía siendo la misma, por ende encontramos otro isomorfismo. Pero no sé si 1) Esto está bien pensado, 2) Alcanza para decir que es otro isomorfismo, 3) Existe otra manera sencilla de decir si el isomorfismo es único o no.

Analizar los automorfismos de grafos es un problema de la misma complejidad que analizar si dos grafos son isomorfos (si no me equivoco sobre esto último ya habías preguntando antes en el foro):

https://en.wikipedia.org/wiki/Graph_automorphism

Saludos.

[manooooh]

Hola, gracias por tu respuesta!

No, no es necesario. Por ejemplo si tienes el grafo \( \{1,2,3,4\} \) con aristas \( 1-2 \) y \( 3-4 \), sus matriz de adyacencia es:

\( \begin{pmatrix}0&1&0&0\\ 1&0&0&0\\ 0&0&0&1\\ 0&0&1&0 \\\end{pmatrix} \)

no tiene pares de filas iguales. Pero si tiene automorfismo: puedes intercambiar los vértices \( 1,2 \) ó los vértices \( 3,4 \); o llevar el par \( 1,2 \) en el par \( 3,4 \).

Ouch. Pensaba que sí.

El ejercicio tenía la siguiente matriz de adyacencia de un grafo \( G_1 \) (que a su vez era isomorfo a otro \( G_2 \)):

\(
\begin{pmatrix}
0&1&1&0&0&0&1&0\\
1&0&0&1&0&0&0&1\\
1&0&0&1&1&0&0&0\\
0&1&1&0&0&1&0&0\\
0&0&1&0&0&1&1&0\\
0&0&0&1&1&0&0&1\\
1&0&0&0&1&0&0&1\\
0&1&0&0&0&1&1&0
\end{pmatrix}
 \)

Como ves, es una matriz muy grande. Pide decir si hay un único isomorfismo o más de uno.

No hay dos filas iguales. Yo pensaba que entonces era único. Pero ahora comprobamos que no alcanza para decir que es único. ¿Cómo justificarías si existe otro, sabiendo que es un examen?

Quizás haya un método visual a través del grafo, o alguna propiedad que se me escape.

Saludos

[Luis Fuentes]

Hola

No hay dos filas iguales. Yo pensaba que entonces era único. Pero ahora comprobamos que no alcanza para decir que es único. ¿Cómo justificarías si existe otro, sabiendo que es un examen?

Quizás haya un método visual a través del grafo, o alguna propiedad que se me escape.

No creo que haya un método sencillo que funcione siempre; si revisas la Wikipedia allí se citan algortimos y software para ayudar, pero no es algo para hacer a mano.

Un primer criterio grueso es fijarse en el grado del los vértices: un automorfismo debe de mantener el grado de los vértices, es decir, llevar un vértice en otro del mismo grado. Digo grueso porque eso es una condición necesaria para que exista un automorfismo, pero obviamente no suficiente.

Yo creo que un dibujo ayuda. En tu caso la matriz que indicas corresponde a un cubo:



De ahí es evidente que hay automorfismos no triviales sin más que considerar los movimientos rígidos de un cubo: simetrías y giros.

Saludos.