He identificado dos formas de mostrarlo isomórfico pero como es una pregunta de 9 marcas no creo que tenga suficiente y tampoco nuestro profesor nos ha explicado o dado suficientes notas sobre cómo se puede probar.
Mis respuestas están muy por debajo:
Es isomorfo, ya que el número de vértices en ambos gráficos es de 6 y el número de aristas en ambos gráficos es de 7.
Grado de los nodos:
Grado (A) = 1 y Grado (T) = 1
Grado (B) = 3 y Grado (U) = 3
Grado (C) = 1 y Grado (Y) = 1
Grado (D) = 2 y Grado (V) = 2
Grado (E) = 1 y Grado (Z) = 1
Grado (F) = 3 y Grado (W) = 3
Grado (G) = 1 y Grado (X) = 1
¿El grado de los nodos es correcto de la forma en que los he vinculado?
¿Es lo que he escrito arriba correcto y suficiente o se puede explicar más? Por favor, dé la solución a esta pregunta. Gracias.
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?