¿Cómo saber si dos gráficos son isomorfos?

Question

Supongamos que se nos dan dos grafos en un número relativamente pequeño de vértices. Aquí tienes un ejemplo:

¿Estos dos grafos son isomorfos? (Es decir: ¿existe una biyección $f$ de $\{A,B,\dots,I\}$, el conjunto de vértices del primer grafo, a $\{1,2,\dots,9\}$, el conjunto de vértices del segundo grafo, tal que $vw$ es una arista del primer grafo si y solo si $f(v)f(w)$ es una arista del segundo grafo?)

• Si no, ¿cómo podemos saberlo?
• Si es así, ¿cómo podemos saberlo y cómo podemos encontrar un isomorfismo?

---

Esta pregunta surge con frecuencia, generalmente preguntando sobre ejemplos específicos de dos grafos que pueden o no ser isomorfos. A veces, el diabólico profesor de teoría de grafos incluso dará tres o más grafos y preguntará "¿Cuáles de estos son isomorfos?"

Hago esta pregunta para que podamos proporcionar una única respuesta canónica a preguntas de este tipo que valdría la pena vincular cuando surjan instancias específicas de esta pregunta. ¡Así que todas las mejoras y/o sugerencias son bienvenidas!

Answer 1

En general, es un problema difícil

No hay un algoritmo eficiente conocido que pueda garantizar decirte si dos gráficos son isomórficos. Por supuesto, podríamos probar todas las posibles permutaciones de los vértices, pero esto llevará mucho tiempo. Conocemos heurísticas: buenas cosas para intentar que funcionarán en muchos casos, pero a veces nos darán una respuesta inconclusa.

Pero podemos resolverlo a mano para ejemplos pequeños

En la práctica, cuando el número de vértices no es muy grande, a menudo podemos verificar el isomorfismo sin mucho trabajo. Hacemos esto seleccionando características distintivas de los vértices en cada gráfico. Luego tenemos menos biyecciones entre los conjuntos de vértices para verificar si los gráficos son isomórficos.

Una de las características distintivas más simples de un vértice es su grado: el número de aristas fuera de ese vértice. Por ejemplo, en el gráfico en cuestión, notamos que:

• Los vértices $\{A, B, E, F, H, I\}$ del primer gráfico tienen un grado de $3$, y los vértices $\{C, D, G\}$ tienen un grado de $4$.
• Los vértices $\{4, 5, 6, 7, 8, 9\}$ del segundo gráfico tienen un grado de $3$, y los vértices $\{1, 2, 3\}$ tienen un grado de $4$.

Entonces hemos reducido significativamente nuestro espacio de búsqueda de $9! = 362,880$ a $6! \cdot 3! = 4,320$ isomorfismos de gráficos: esa es la cantidad de biyecciones entre los conjuntos de vértices que envían $\{A, B, E, F, H, I\}$ a $\{4, 5, 6, 7, 8, 9\}$ y $\{C, D, G\}$ a $\{1, 2, 3\}$. (Y si el número de vértices de cada grado no coincidiera, sabríamos muy rápidamente que no hay isomorfismo de gráficos).

También podemos distinguir entre los vértices de cada grado. Por ejemplo, en el primer gráfico, $\{A, E, I\}$ son vértices de grado $3$ que son adyacentes a vértices de grado $4$; $\{B, F, H\}$, por otro lado, son vértices de grado $3$ cuyos vecinos tienen todos grado $3$. Esto reduce aún más el espacio de búsqueda.

Si comenzamos a llenar un isomorfismo de gráficos parcial, las piezas se irán encajando a medida que avanzamos. Por ejemplo, podríamos intentar ver si hay un isomorfismo de gráficos que mapea $C$ a $1$. Entonces $A$ (un vecino de $C$ que tiene grado $3$) debe ser mapeado a $4$ o $6$ (vecinos de $1$ que tienen grado $3$). Si $A$ se mapea a $4$, entonces $D$ (un vecino de $A$ y $C$) debe mapearse a $3$ (un vecino de $1$ y $4$), y muy pronto estará completo el isomorfismo.

Para hacer que esto funcione, necesitaremos hacer algunos casos y tal vez necesitemos retroceder, pero generalmente no deberías esperar tener muchas ramas para probar. Los gráficos altamente simétricos son más difíciles de abordar de esta manera, e de hecho son los lugares donde los algoritmos informáticos también fallan.

Otro ejemplo de mirar los grados

Aquí hay otro ejemplo de gráficos que podríamos analizar mirando los grados de los vértices.

Si escribimos los grados de todos los vértices en cada gráfico, en orden ascendente, obtenemos:

• $2, 2, 2, 3, 3, 4, 5, 5$ para el gráfico de la izquierda;
• $2, 2, 3, 3, 3, 4, 4, 5$ para los otros dos gráficos.

Esto nos dice que el primer gráfico no es isomórfico a los otros dos, porque las secuencias de grados no coinciden.

Importante, esto no nos dice que los otros dos gráficos sean isomórficos, aunque tengan la misma secuencia de grados. De hecho, tampoco lo son: en el gráfico del medio, el único vértice de grado $5$ es adyacente a un vértice de grado $2$, y en el gráfico de la derecha, el único vértice de grado $5$ solo está adyacente a vértices de grado $3$ o $4$.

Invariantes de graficos

Un enfoque más general para el isomorfismo de gráficos es buscar invariantes de gráficos: propiedades de un gráfico que pueden ser verdaderas o no para otro. (La secuencia de grados de un gráfico es un invariante de gráfico, pero hay muchos otros). Esto suele ser una forma rápida de demostrar que dos gráficos no son isomórficos, pero no nos dirá mucho si lo son.

Por ejemplo:

• ¿El número de vértices y aristas en un gráfico es igual que en el otro?
• Si un gráfico es planar, ¿es también planar el otro gráfico?
• Si un gráfico es bipartito, ¿es también bipartito el otro gráfico?
• Si un gráfico contiene dos ciclos de longitud $3$, ¿el otro gráfico también contiene dos ciclos de longitud $3$?

Existen invariantes más elaborados. Por ejemplo, podemos calcular el polinomio de Tutte de ambos gráficos: si obtenemos valores diferentes, entonces los gráficos no son isomórficos. Desafortunadamente, si dos gráficos tienen el mismo polinomio de Tutte, eso no garantiza que sean isomórficos.

Enlaces

• Consulta el artículo de Wikipedia sobre el isomorfismo de gráficos para más detalles.
• Nauty es un programa informático que se puede utilizar para probar si dos gráficos son isomórficos encontrando una etiqueta canónica para cada gráfico.

Answer 2

Un método que es útil para grafos con un pequeño número de vértices es tratar de visualizar una deformación continua de un grafo que lo cambie en otro grafo. Por ejemplo, para los grafos dados, si en el segundo grafo, el vértice $3$ es "jaloneado" lo suficiente hacia arriba al otro lado del borde $\{1, 2\}$ y el vértice $9$ también es jaloneado hacia arriba al otro lado del borde $\{7, 8\}$, entonces el grafo resultante es el mismo que el primer grafo. Una biyección entre los dos conjuntos de vértices es fácilmente formada.