El gráfico de isomorfismo se puede describir como un gráfico en el que un solo gráfico puede tener más de una forma. Eso significa que dos gráficos diferentes pueden tener la misma cantidad de aristas, vértices y la misma conectividad de aristas. Este tipo de gráficos se conocen como gráficos de isomorfismo. El ejemplo de un gráfico de isomorfismo se describe a continuación:
El gráfico anterior contiene lo siguiente:
- El mismo gráfico se representa en más de una forma.
- Por tanto, podemos decir que estas gráficas son gráficas de isomorfismo.
Condiciones para el isomorfismo gráfico
Dos gráficos cualesquiera se conocerán como isomorfismo si satisfacen las cuatro condiciones siguientes:
- Habrá un número igual de vértices en los gráficos dados.
- Habrá un número igual de aristas en los gráficos dados.
- Habrá una cantidad igual de secuencia de grados en los gráficos dados.
- Si el primer gráfico está formando un ciclo de longitud k con la ayuda de los vértices {v1, v2, v3,…. vk}, entonces otro gráfico también debe formar el mismo ciclo de la misma longitud k con la ayuda de los vértices {v1, v2, v3,…. vk}.
Nota: La secuencia de grados de un gráfico se puede describir como una secuencia de grados de todos los vértices en orden ascendente.
Puntos importantes
- Para que dos gráficos sean un isomorfismo, las condiciones necesarias son las cuatro condiciones definidas anteriormente.
- No es necesario que las condiciones definidas anteriormente sean suficientes para demostrar que las gráficas dadas son isomorfas.
- Si dos gráficos satisfacen las cuatro condiciones definidas anteriormente, incluso entonces, no es necesario que los gráficos seguramente tengan isomorfismo.
- Si la gráfica no cumple alguna condición, entonces podemos decir que las gráficas seguramente no son un isomorfismo.
Condiciones suficientes para el isomorfismo gráfico
Si queremos demostrar que dos gráficos cualesquiera son isomorfismo, existen algunas condiciones suficientes que nos proporcionaremos para garantizar que los dos gráficos sean seguramente isomorfismo. Cuando los dos gráficos hayan superado con éxito las cuatro condiciones anteriores, solo entonces verificaremos que esos gráficos cumplan con las condiciones suficientes, que se describen a continuación:
- Si las gráficas complementarias de ambas gráficas son isomorfismos, entonces estas gráficas seguramente serán un isomorfismo.
- Si las matrices adyacentes de ambas gráficas son iguales, entonces estas gráficas serán un isomorfismo.
- Si las gráficas correspondientes de dos gráficas se obtienen eliminando algunos vértices de una gráfica, y sus imágenes correspondientes en otras imágenes son isomorfismos, solo entonces estas gráficas no serán un isomorfismo.
Cuando dos gráficas satisfacen cualquiera de las condiciones anteriores, entonces podemos decir que esas gráficas son seguramente isomorfismo.
Ejemplos de isomorfismo gráfico
Hay muchos ejemplos de isomorfismo de gráficos, que se describen a continuación:
Ejemplo 1:
En este ejemplo, hemos demostrado si las siguientes gráficas son isomorfismos.
Solución: Para ello, comprobaremos las cuatro condiciones del isomorfismo de grafos, que se describen a continuación:
métodos de cadena en java
Condición 1:
- En el gráfico 1, hay un total de 4 vértices, es decir, G1 = 4.
- En el gráfico 2, hay un total de 4 vértices, es decir, G2 = 4.
Aquí,
Hay el mismo número de vértices en ambos gráficos G1 y G2. Entonces estas gráficas satisfacen la condición 1. Ahora verificaremos la segunda condición.
Condición 2:
- En el gráfico 1, hay un total de 5 aristas, es decir, G1 = 5.
- En el gráfico 2, hay un total de 6 aristas, es decir, G2 = 6.
Aquí,
pitón reducir
No hay igual número de aristas en ambos gráficos G1 y G2. Entonces estas gráficas no satisfacen la condición 2. Ahora no podemos verificar todas las condiciones restantes.
Desde entonces, estas gráficas violan la condición 2. Entonces estas gráficas no son un isomorfismo.
∴ El gráfico G1 y el gráfico G2 no son gráficos de isomorfismo.
Ejemplo 2:
En este ejemplo, hemos demostrado si las siguientes gráficas son isomorfismos.
Solución: Para ello, comprobaremos las cuatro condiciones del isomorfismo de grafos, que se describen a continuación:
Condición 1:
- En el gráfico 1, hay un total de 4 vértices, es decir, G1 = 4.
- En el gráfico 2, hay un total de 4 vértices, es decir, G2 = 4.
- En el gráfico 3, hay un total de 4 vértices, es decir, G3 = 4.
Aquí,
Hay el mismo número de vértices en todos los gráficos G1, G2 y G3. Entonces estas gráficas satisfacen la condición 1. Ahora verificaremos la segunda condición.
Condición 2:
- En el gráfico 1, hay un total de 5 aristas, es decir, G1 = 5.
- En el gráfico 2, hay un total de 5 aristas, es decir, G2 = 5.
- En el gráfico 3, hay un total de 4 aristas, es decir, G2 = 4.
Aquí,
- Hay un número igual de aristas en ambos gráficos G1 y G2. Entonces estas gráficas satisfacen la condición 2.
- Pero no tiene el mismo número de aristas en las gráficas (G1, G2) y G3. Entonces las gráficas (G1, G2) y G3 no satisfacen la condición 2.
Desde entonces, las gráficas (G1, G2) y G3 violan la condición 2. Entonces podemos decir que estas gráficas no son un isomorfismo.
nueva línea de Python
∴ El gráfico G3 no es isomorfismo con el gráfico G1 ni con el gráfico G2.
Dado que las gráficas G1 y G2 satisfacen la condición 2, podemos decir que estas gráficas pueden ser un isomorfismo.
∴ Los gráficos G1 y G2 pueden ser un isomorfismo.
Ahora comprobaremos la tercera condición para los gráficos G1 y G2.
Condición 3:
- En el gráfico 1, el grado de la secuencia s es {2, 2, 3, 3}, es decir, G1 = {2, 2, 3, 3}.
- En el gráfico 2, el grado de secuencia s es {2, 2, 3, 3}, es decir, G2 = {2, 2, 3, 3}.
Aquí
Hay un número igual de secuencias de grados en ambos gráficos G1 y G2. Entonces estas gráficas satisfacen la condición 3. Ahora verificaremos la cuarta condición.
Condición 4:
El gráfico G1 forma un ciclo de longitud 3 con la ayuda de los vértices {2, 3, 3}.
El gráfico G2 también forma un ciclo de longitud 3 con la ayuda de los vértices {2, 3, 3}.
Aquí,
10 de 100.00
Muestra que ambos gráficos contienen el mismo ciclo porque ambos gráficos G1 y G2 forman un ciclo de longitud 3 con la ayuda de los vértices {2, 3, 3}. Entonces estas gráficas satisfacen la condición 4.
De este modo,
- Los gráficos G1 y G2 satisfacen las cuatro condiciones necesarias anteriores.
- Entonces G1 y G2 pueden ser un isomorfismo.
Ahora comprobaremos condiciones suficientes para demostrar que las gráficas G1 y G2 son un isomorfismo.
Comprobando condiciones suficientes
Como hemos aprendido, si las gráficas complementarias de ambas gráficas son isomorfismos, las dos gráficas seguramente serán un isomorfismo.
Entonces dibujaremos las gráficas en complemento de G1 y G2, que se describen a continuación:
En los gráficos de complemento anteriores de G1 y G2, podemos ver que ambos gráficos son isomorfismos.
∴ Los gráficos G1 y G2 son isomorfismos.
Ejemplo 3:
En este ejemplo, hemos demostrado si las siguientes gráficas son isomorfismos.
Solución: Para ello, comprobaremos las cuatro condiciones del isomorfismo de grafos, que se describen a continuación:
Condición 1:
- En el gráfico 1, hay un total de 8 vértices, es decir, G1 = 8.
- En el gráfico 2, hay un total de 8 vértices, es decir, G2 = 8.
Aquí,
Hay el mismo número de vértices en ambos gráficos G1 y G2. Entonces estas gráficas satisfacen la condición 1. Ahora verificaremos la segunda condición.
Condición 2:
- En el gráfico 1, el número total de aristas es 10, es decir, G1 = 10.
- En el gráfico 2, el número total de aristas es 10, es decir, G2 = 10.
Aquí,
Hay el mismo número de aristas en ambos gráficos G1 y G2. Entonces estas gráficas satisfacen la condición 2. Ahora verificaremos la tercera condición.
tipos de árboles binarios
Condición 3:
- En el gráfico 1, el grado de la secuencia s es {2, 2, 2, 2, 3, 3, 3, 3}, es decir, G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- En el gráfico 2, el grado de la secuencia s es {2, 2, 2, 2, 3, 3, 3, 3}, es decir, G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Aquí
Hay un número igual de secuencias de grados en ambos gráficos G1 y G2. Entonces estas gráficas satisfacen la condición 3. Ahora verificaremos la cuarta condición.
Condición 4:
- El gráfico G1 forma un ciclo de longitud 4 con la ayuda de vértices de grado 3.
- El gráfico G2 no forma un ciclo de longitud 4 con la ayuda de los vértices porque los vértices no son adyacentes.
Aquí,
Tanto los gráficos G1 como G2 no forman el mismo ciclo con la misma longitud. Entonces estos gráficos violan la condición 4.
Dado que los gráficos G1 y G2 violan la condición 4, debido a la violación de la condición 4, estos gráficos no serán un isomorfismo.
∴ Los gráficos G1 y G2 no son un isomorfismo.