Primero haz la matriz de adyacencia para ambos grafos.
Estas matrices serían cuadradas y simétricas. (Si no hay aristas múltiples o dirigidas)
La diagonal principal sería todo ceros (si no hay bucles)
si el número de 1s y 0s no es el mismo en ambas matrices entonces no es isomorfo seguramente. Si son iguales, entonces puede ser isomorfo.
Toma cualquiera de las matrices.
Ahora puedes intercambiar 2 colores de esta matriz, pero cuando lo haces también debes intercambiar las mismas filas.
Por lo tanto, al intercambiar la fila 2 y la fila 3, se debe intercambiar inmediatamente la col 2 y la col 3 también. El orden de intercambio no importa. Como es una matriz cuadrada, todas las columnas tendrán sus filas correspondientes.
De este modo, simplemente se intercambiaría la posición del vértice en la matriz de adyacencia y se cambiaría el mapeo de cada vértice.
Utilizando nuestra capacidad de encontrar patrones, podemos elegir qué filas y columnas intercambiar para que una matriz sea exactamente igual a la otra. Lo conseguirás en un máximo de 3-4 intercambios.
Es bastante fácil, ya que son cuadrados simétricos.
Si no son isomorfas, entonces podrías intentar intercambiar filas y coles sin cesar tratando de hacer coincidir el patrón, pero con un poco de intuición puedes evitarlo.
Son isomorfas si la matriz de adyacencia tiene el mismo aspecto. Esta matriz te dará los mapeos.
Así que es como tratar de encontrar un mapeo de todos los posibles mapeos de un gráfico, que se ven exactamente como la otra matriz de adyacencia por cleaverly intercambiando la posición de los vértices (por el intercambio de filas y cols). No funciona tan bien para los gráficos enormes.
0 votos
Es difícil de decir, depende de lo explícita que tenga que ser la respuesta para ser aceptada. No basta con el grado de los nodos (considere algunos $k$ -regulares con el mismo número de vértices), sin embargo, ciertamente das una correspondencia válida, y dudo que hayas tenido que enumerar todos $\binom{7}{2}$ posibles aristas para demostrar que es un isomorfismo.
5 votos
Tu definición de isomorfo es errónea: necesitas una biyección $f:\ V\to V'$ con $\{v_1,v_2\}\in E$ si $\{f(v_1),f(v_2)\}\in E'$ . (Según su definición, un grafo con cero aristas sería isomorfo a cualquier grafo con el mismo número de vértices).
0 votos
@dtldarek estoy recibiendo respuestas mixtas, ¿tengo que mostrar el grado de los nodos o no para demostrar que son isomorfos? No entramos en mucho detalle en clase así que no creo que tenga que mostrar demasiado
0 votos
@ChristianBlatter No sé la definición, esto fue tomado de un trabajo de examen realizado anteriormente
1 votos
@Jay Los grados pueden ser útiles para demostrar que dos gráficos son no isomorfo, sin embargo, no es necesario demostrar que dos grafos lo son. Si se quiere utilizar la definición (por ejemplo, véase Wikipedia ), entonces hay que construir $f$ (que implícitamente hiciste alineando los vértices correspondientes en las mismas filas, sin embargo no estoy seguro de que eso sea aceptado) y luego mostrar que $\{u,v\} \in E$ si y sólo si $\{f(u),f(v)\} \in E'$ (el enfoque de fuerza bruta sería escribir una línea para cada una de las 21 aristas posibles).
0 votos
@dtldarek no sé a qué te refieres con lo de la fuerza bruta, ya que sólo hemos tocado el tema de los grafos isomórficos en clase, sí, entiendo lo que quieres decir, creo que lo único que tengo que hacer es enumerar los vértices correspondientes. Pero, ¿hay alguna forma, correcta o incorrecta, de corresponder cada arista al otro grafo?