Te damos la bienvenida a proyecto on line, aquí vas a hallar la resolución a lo que necesitas.
Solución:
Desafortunadamente, dos gráficos no isomorfos pueden tener la misma secuencia de grados. Vea aquí un ejemplo. Verificar la secuencia de grados solo puede refutar que dos gráficos son isomorfos, pero no puede probar que lo sean. En este caso, simplemente especificaría mi isomorfismo (que básicamente ha hecho al identificar los vértices A y T, B y U, etc.) y luego mostraría que dos vértices están conectados por una arista en el gráfico original si y solo si están conectados en la imagen. Es un poco tedioso, pero debería ser algo que puedas aplicar en general a este tipo de problemas.
Para mostrar que las dos gráficas son isomorfas, aplique la definición dada. Llamemos al gráfico de la izquierda $G[V_1,E_1]$, y el gráfico de la derecha $G[V_2,E_2]ps Ahora da una biyección explícita $$f: V_1 longrightarrow V_2,$$ y demuestra que si $e_1,e_2\in E_1$, entonces $f(e_1),f(e_2) en E_2$.
Comprobar que $operatornameDeg(e)=operatornameDeg(f(e))$ para todo $ein V$ no es suficiente: Dado un isomorfismo $f$, obtenemos otra biyección $g: V_1 longrightarrow V_2$ cambiando $U$ y $W$, es decir; $$g(e)=left{beginarrayccW&text si f(e)=U\U&text si f(e)=W\f(e)&text de lo contrarioendarrayright.$$ Los grados se conservan, pero esto no es un isomorfismo.
Primero haga una matriz de adyacencia para ambos gráficos.
Estas matrices serían cuadradas y simétricas. (Si no hay bordes múltiples o dirigidos)
La diagonal principal sería todo ceros (si no hay bucles)
si el número de 1 y 0 no es el mismo en ambas matrices, entonces seguramente no es isomorfo. Si son iguales, entonces puede ser isomorfo.
Tome cualquiera de las matrices.
Ahora puede intercambiar 2 columnas de esta matriz, pero cuando lo haga, también debe intercambiar las mismas filas.
Entonces, al intercambiar fila2 y fila3, también debe intercambiar inmediatamente col2 y col3. El orden de intercambio no importa. Dado que su matriz es cuadrada, todas las columnas tendrán filas correspondientes.
Hacer esto simplemente cambiaría la posición del vértice en la matriz de adyacencia y, por lo tanto, cambiaría el mapeo de cada vértice.
Mediante el uso de nuestra capacidad de búsqueda de patrones, podemos elegir qué filas y columnas intercambiar para que una matriz se vea exactamente igual a la otra. Lo obtendrías en un máximo de 3-4 intercambios.
Es bastante fácil ya que son cuadrados simétricos.
Si no son isomorfos, puede intentar intercambiar filas y columnas sin cesar para intentar que coincida con el patrón, pero con un poco de intuición puede evitarlo.
Son isomorfos si la matriz de adyacencia se ve igual. Esta matriz le daría las asignaciones.
Entonces, es como tratar de encontrar una asignación de todas las asignaciones posibles de un gráfico, que se vea exactamente como la otra matriz de adyacencia al intercambiar hábilmente la posición de los vértices (al intercambiar filas y columnas). No funciona tan bien para gráficos enormes.
Al final de la web puedes encontrar las anotaciones de otros gestores de proyectos, tú igualmente puedes dejar el tuyo si dominas el tema.