No dejes de compartir nuestro espacio y códigos con otro, ayúdanos a hacer crecer nuestra comunidad.
Solución:
En general, es un problema difícil.
No existe un algoritmo eficiente conocido que garantice que le diga si dos gráficos son isomorfos. Por supuesto, podríamos probar todas las permutaciones posibles de los vértices, pero esto llevará mucho tiempo. Conocemos la heurística: cosas buenas para probar que funcionarán en muchos casos, pero que a veces nos darán una respuesta no concluyente.
Pero podemos resolverlo a mano para pequeños ejemplos.
En la práctica, cuando el número de vértices no es demasiado grande, a menudo podemos verificar el isomorfismo sin demasiado trabajo. Hacemos esto eligiendo características distintivas de los vértices en cada gráfico. Entonces tenemos menos biyecciones entre los conjuntos de vértices para comprobar si las gráficas son isomorfas.
Una de las características distintivas más simples de un vértice es su grado: el número de aristas que salen de ese vértice. Para el ejemplo en la pregunta, notamos que:
- vértices $A, B, E, F, H, I$ del primer gráfico tienen grado $3$y vértices $C,D,G$ tener título $4$.
- vértices $4, 5, 6, 7, 8, 9$ del segundo gráfico tienen grado $3$y vértices $1,2,3$ tener título $4$.
Así que hemos reducido significativamente nuestro espacio de búsqueda de $9! = 362,880$ para $6! cdot 3! = 4,320$ isomorfismos de grafos: ese es el número de biyecciones entre los conjuntos de vértices que envían $A,B,E,F,H,I$ para $4,5,6,7,8,9$ y $C,D,G$ para $1,2,3$. (Y si el número de vértices de cada grado no coincidiera, rápidamente sabríamos que no hay isomorfismo en el gráfico).
Podemos distinguir además 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 los vértices de grado $4$; $B,F,H$en cambio, son vértices de grado $3$ cuyos vecinos todos tienen titulación $3$. Esto reduce aún más el espacio de búsqueda.
Si comenzamos a completar un isomorfismo de gráfico parcial, las piezas encajan a medida que avanzamos. Por ejemplo, podríamos intentar ver si hay un isomorfismo gráfico que mapee $C$ para $1$. Entonces $A$ (un vecino de $C$ que tiene grado $3$) debe asignarse a $4$ o $6$ (vecinos de $1$ que tienen grado $3$). Si $A$ está asignado a $4$entonces $D$ (un vecino de $A$ y $C$) debe mapear a $3$ (un vecino de $1$ y $4$), y muy pronto todo el isomorfismo está ahí.
Para que esto funcione, tendremos que hacer algunos casos y es posible que tengamos que retroceder, pero por lo general no debe esperar tener muchas sucursales para probar. Los gráficos altamente simétricos son más difíciles de abordar de esta manera y, de hecho, son los lugares donde los algoritmos informáticos también tropiezan.
Otro ejemplo de mirar grados
Aquí hay otro ejemplo de gráficos que podríamos analizar al observar los grados de los vértices.
Si anotamos los grados de todos los vértices de 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 isomorfo a los otros dos, porque las secuencias de grados no coinciden.
Es importante destacar que no es dinos que las otras dos gráficas son isomorfas, aunque tienen la misma secuencia de grados. De hecho, tampoco son isomorfos: en el grafo central, 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 es adyacente a los vértices de grado $3$ o $4$.
Graficar invariantes
Un enfoque más general para el isomorfismo de gráficos es buscar invariantes de gráficos: propiedades de un gráfico que pueden o no serlo. true Por otro. (La secuencia de grados de un gráfico es un gráfico invariante, pero hay muchos otros.) Por lo general, esta es una forma rápida de demostrar que dos gráficos son no isomorfos, pero no nos dirá mucho si son.
Por ejemplo:
- ¿El número de vértices y aristas en un gráfico es el mismo que en el otro?
- Si un gráfico es plano, ¿el otro gráfico también es plano?
- Si un gráfico es bipartito, ¿el otro gráfico también es bipartito?
- 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 elaboradas. Por ejemplo, podemos calcular el polinomio de Tutte de ambas gráficas: si obtenemos valores diferentes, entonces las gráficas no son isomorfas. Desafortunadamente, si dos gráficos tienen el mismo polinomio de Tutte, eso no garantiza que sean isomorfos.
Enlaces
- Consulte el artículo de Wikipedia sobre isomorfismo de grafos para obtener más detalles.
- Nauty es un programa de computadora que se puede usar para probar si dos gráficos son isomorfos al encontrar un etiquetado canónico de cada gráfico.
Un método que es útil para gráficos con un pequeño número de vértices es tratar de visualizar una transformación continua de un gráfico que lo convierte en otro gráfico. Por ejemplo, para los gráficos dados, si en el segundo gráfico, el vértice $3$ se “tira” lo suficiente hacia el otro lado del borde $1, 2$ y el vértice $9$ también se tira hacia arriba en el otro lado del borde $7, 8$, entonces el gráfico resultante es el mismo que el primer gráfico. Entonces se forma fácilmente una biyección entre los dos conjuntos de vértices.
Sección de Reseñas y Valoraciones
Al final de la artículo puedes encontrar las acotaciones de otros sys admins, tú asimismo eres capaz insertar el tuyo si te apetece.