Explique si estos dos gráficos son isomorfos. Si es así, dé la correspondencia 1-1 de los nodos.
He comprobado que los dos gráficos tienen los mismos grados, bordes y vértices, y comprobar que ambos no son bipartitos. Simplemente no puedo encontrar una correspondencia correcta de 1-1 nodos.
El gráfico de la izquierda tiene un 3-ciclo de $(a,b,j)$ (también se $(f,e,g)$). El gráfico de la derecha no tiene ninguno. No son isomorfos.
Cabe señalar que el gráfico de la derecha es simplemente (el esqueleto) de un prisma pentagonal; en consecuencia, cada vértice es (en un sentido) "equivalente" a todos los demás vértices. Este no es el caso en el gráfico de la izquierda.
Además, el gráfico de la derecha, como se ilustra, es planar; sin bordes se cruzan. En el gráfico de la izquierda, se puede sustituir "acordes" $bj$ $eg$ con rutas de acceso que viaje "fuera del círculo", la eliminación de las intersecciones con $af$, pero usted no puede hacer eso con tanto de $ch$ $di$ e no ha $ch$ $di$ cruz; un borde de intersección es inevitable (aunque esto necesita una rigurosa prueba), por lo que la gráfica no es planar.
El derecho que tiene uno de cuatro de 4 ciclos: 1,2,3,10; 3,4,9,10; 4,5,8,9; 5,6,7,8. No puedo encontrar más que c,d,i,h, a la izquierda. El de la derecha tiene dos disjuntos de 5 ciclos: 1,7,8,9,10; 2,3,4,5,6. A la derecha puedo encontrar más de 5 ciclos, pero ninguno de involucrar a una o f. Tal vez estoy con vistas a algunos.
Añadido: Sí, esta es una ruta para mostrar que no son isomorfos. Para ser isomorfo necesita la matriz de adyacencia a ser el mismo una vez que encuentre la asignación correcta. Si usted puede encontrar cualquier propiedad que no coincide con el de ellos no son isomorfos. Los grados, el número de vértices número de aristas son fáciles de comprobar, por lo que debe ser el primer paso. Para asegurarse de que le dicen que lo de los 3 mapas que tiene que ser parte de dos de cuatro ciclos, que incluyen también la cosa de los 10 mapas. Mirar a través de todos los vértices y ver que no se puede satisfacer este.
Para Isomorfismo cuatro condiciones deben ser verdaderas: 1. Tanto los gráficos deben tener el mismo número de vértices. 2. Tanto los gráficos deben tener el mismo número de aristas. 3. Tanto los gráficos deben tener el mismo número de vértices de un cierto grado. 4. Adyacencia siempre debe ser mantenida.
En tanto los gráficos de las tres primeras condiciones que he mencionado son de verdad. Pero si usted llega a la cuarta condición y atentamente verás que adyacencia no se ha mantenido. Todos los vértices son de grado 3 de acuerdo pero si me pongo a la asignación supongamos que un mapa a 1. Entonces, b,j y f son adyacentes, así que trato de asignación de b,j y f a los nodos adyacentes a 1 es decir, 2,7 y 10. Si yo mapa de b a 2 luego de que se me permita mapa de j a 7 o 10 para preservar de adyacencia. Pero la asignación de j a cualquiera de los 7 o 10 no conserva de adyacencia ya que en el primer gráfico b y j son adyacentes, mientras que ninguno de 2,7 o 10 son adyacentes.
Así, los gráficos no son isomorfos, ya que usted no puede encontrar una asignación o un bijection función
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
