Cómo comprobar que dos matrices de adyacencia son iguales

Question

¿Cuál es la forma más sencilla de saber si estos dos grafos son isomorfos y cómo puedo saber qué nodos de ambos grafos son iguales? He hecho las matrices de adyacencia pero son bastante grandes. Creo que tengo que encontrar una matriz de permutación para las matrices de adyacencia, pero eso es un montón de trabajo, ¿hay una manera más fácil?

La solución al problema es:

Answer 1

Iba a decir que pensaba que el isomorfismo de grafos es NP-completo, pero he aquí que (probablemente) no lo es. Al menos no se sabe que sea NP-completo y hay algunas razones para pensar que podría no serlo. Aun así, las soluciones generales más eficientes no son especialmente buenas.

Para una solución manual, lo mejor que puedes hacer es buscar "formas" similares, es decir, subgrafos completos en unos pocos vértices. Puedes ver fácilmente que hay algunas parejas de vértices que forman triángulos y otras que no ( $\{d,c,h\}$ hace y $\{b,g,f,e\}$ no lo hace) y seguir a partir de ahí.

Personalmente he observado que se obtiene una partición del conjunto de vértices en dos cuádruples que forman cuadrados $\{a,b,c,d\},\{e,f,g,h\}$ y $\{a^\prime,c^\prime,e^\prime,g^\prime\},\{b^\prime,d^\prime,f^\prime,h^\prime\}$ .

Luego continué deformando el gráfico de manera que el centro formara un cuadrado y el exterior otro cuadrado para obtener una mejor representación visual intentando acercarme lo más posible a un gráfico plano. Eso significaba (según el gráfico original 2 intersecciones). A continuación, utilicé la intersección para obtener un punto de partida para la construcción de mi isomorfismo. Esto resultó ser bastante sencillo, ya que el gráfico es pequeño y el primer intento de hacer que "se viera bien" funcionó. Aunque me dio un isomorfismo diferente $\{a,b,c,d,e,f,g,h\}\to\{f^\prime,d^\prime,b^\prime,h^\prime,e^\prime,g^\prime,c^\prime,a^\prime\}$ .