O gráfico de isomorfismo pode ser descrito como um gráfico em que um único gráfico pode ter mais de uma forma. Isso significa que dois gráficos diferentes podem ter o mesmo número de arestas, vértices e a mesma conectividade de arestas. Esses tipos de gráficos são conhecidos como gráficos de isomorfismo. O exemplo de um gráfico de isomorfismo é descrito a seguir:
O gráfico acima contém o seguinte:
- O mesmo gráfico é representado em mais de uma forma.
- Portanto, podemos dizer que esses gráficos são gráficos de isomorfismo.
Condições para isomorfismo de gráfico
Quaisquer dois gráficos serão conhecidos como isomorfismo se satisfizerem as quatro condições a seguir:
- Haverá um número igual de vértices nos gráficos fornecidos.
- Haverá um número igual de arestas nos gráficos fornecidos.
- Haverá uma quantidade igual de sequência de graus nos gráficos fornecidos.
- Se o primeiro gráfico está formando um ciclo de comprimento k com a ajuda dos vértices {v1, v2, v3,…. vk}, então outro grafo também deve formar o mesmo ciclo de mesmo comprimento k com a ajuda dos vértices {v1, v2, v3,…. vc}.
Nota: A sequência de graus de um gráfico pode ser descrita como uma sequência de graus de todos os vértices em ordem crescente.
Pontos importantes
- Para que quaisquer dois gráficos sejam um isomorfismo, as condições necessárias são as quatro condições definidas acima.
- Não é necessário que as condições definidas acima sejam suficientes para mostrar que os gráficos dados são isomórficos.
- Se dois gráficos satisfazem as quatro condições definidas acima, mesmo assim, não é necessário que os gráficos tenham certamente isomorfismo.
- Se o gráfico não satisfaz nenhuma condição, podemos dizer que os gráficos certamente não são um isomorfismo.
Condições suficientes para isomorfismo de gráfico
Se quisermos provar que quaisquer dois gráficos são isomorfismo, existem algumas condições suficientes que nos forneceremos para garantir que os dois gráficos são certamente isomorfismo. Quando os dois gráficos forem eliminados com sucesso em todas as quatro condições acima, só então verificaremos esses gráficos quanto às condições suficientes, que são descritas a seguir:
- Se os gráficos complementares de ambos os gráficos forem isomorfismo, então esses gráficos certamente serão um isomorfismo.
- Se as matrizes adjacentes de ambos os gráficos forem iguais, então esses gráficos serão um isomorfismo.
- Se os gráficos correspondentes de dois gráficos forem obtidos excluindo alguns vértices de um gráfico, e suas imagens correspondentes em outras imagens forem isomorfismo, só então esses gráficos não serão um isomorfismo.
Quando dois gráficos satisfazem qualquer uma das condições acima, podemos dizer que esses gráficos são certamente isomorfismo.
Exemplos de isomorfismo de gráfico
Existem muitos exemplos de isomorfismo de grafos, que são descritos a seguir:
Exemplo 1:
Neste exemplo, mostramos se os gráficos a seguir são isomorfismo.
Solução: Para isso, verificaremos todas as quatro condições de isomorfismo de grafos, que são descritas a seguir:
Condição 1:
- No gráfico 1, há um número total de 4 vértices, ou seja, G1 = 4.
- No gráfico 2, há um número total de 4 vértices, ou seja, G2 = 4.
Aqui,
Há um número igual de vértices em ambos os gráficos G1 e G2. Portanto, estes gráficos satisfazem a condição 1. Agora verificaremos a segunda condição.
classificação de bolhas java
Condição 2:
- No gráfico 1, há um número total de 5 arestas, ou seja, G1 = 5.
- No gráfico 2, há um número total de 6 arestas, ou seja, G2 = 6.
Aqui,
Não existe um número igual de arestas nos dois gráficos G1 e G2. Portanto, estes gráficos não satisfazem a condição 2. Agora não podemos verificar todas as condições restantes.
Visto que esses gráficos violam a condição 2. Portanto, esses gráficos não são um isomorfismo.
∴ O gráfico G1 e o gráfico G2 não são gráficos de isomorfismo.
Exemplo 2:
Neste exemplo, mostramos se os gráficos a seguir são isomorfismo.
Solução: Para isso, verificaremos todas as quatro condições de isomorfismo de grafos, que são descritas a seguir:
Condição 1:
- No gráfico 1, há um número total de 4 vértices, ou seja, G1 = 4.
- No gráfico 2, há um número total de 4 vértices, ou seja, G2 = 4.
- No gráfico 3, há um número total de 4 vértices, ou seja, G3 = 4.
Aqui,
Há um número igual de vértices em todos os gráficos G1, G2 e G3. Portanto, estes gráficos satisfazem a condição 1. Agora verificaremos a segunda condição.
Condição 2:
idade de Salman Khan
- No gráfico 1, há um número total de 5 arestas, ou seja, G1 = 5.
- No gráfico 2, há um número total de 5 arestas, ou seja, G2 = 5.
- No gráfico 3, há um número total de 4 arestas, ou seja, G2 = 4.
Aqui,
- Há um número igual de arestas em ambos os gráficos G1 e G2. Portanto, esses gráficos satisfazem a condição 2.
- Mas não há igual número de arestas nos grafos (G1, G2) e G3. Portanto os gráficos (G1, G2) e G3 não satisfazem a condição 2.
Visto que os gráficos (G1, G2) e G3 violam a condição 2. Portanto, podemos dizer que esses gráficos não são um isomorfismo.
quando começa o q2
∴ O gráfico G3 não é isomorfismo com o gráfico G1 nem com o gráfico G2.
Como os gráficos G1 e G2 satisfazem a condição 2. Portanto, podemos dizer que esses gráficos podem ser um isomorfismo.
∴ Os gráficos G1 e G2 podem ser um isomorfismo.
Agora verificaremos a terceira condição para os gráficos G1 e G2.
Condição 3:
- No gráfico 1, o grau da sequência s é {2, 2, 3, 3}, ou seja, G1 = {2, 2, 3, 3}.
- No gráfico 2, o grau da sequência s é {2, 2, 3, 3}, ou seja, G2 = {2, 2, 3, 3}.
Aqui
Há um número igual de sequências de graus em ambos os gráficos G1 e G2. Portanto, estes gráficos satisfazem a condição 3. Agora verificaremos a quarta condição.
Condição 4:
O gráfico G1 forma um ciclo de comprimento 3 com a ajuda dos vértices {2, 3, 3}.
O gráfico G2 também forma um ciclo de comprimento 3 com a ajuda dos vértices {2, 3, 3}.
Aqui,
Mostra que ambos os gráficos contêm o mesmo ciclo porque ambos os gráficos G1 e G2 estão formando um ciclo de comprimento 3 com a ajuda dos vértices {2, 3, 3}. Portanto, esses gráficos satisfazem a condição 4.
Por isso,
- Os gráficos G1 e G2 satisfazem todas as quatro condições necessárias acima.
- Portanto, G1 e G2 podem ser um isomorfismo.
Agora verificaremos condições suficientes para mostrar que os grafos G1 e G2 são um isomorfismo.
Verificando condições suficientes
Como aprendemos que se os gráficos complementares de ambos os gráficos forem isomorfismo, os dois gráficos certamente serão um isomorfismo.
Assim desenharemos os gráficos complementares de G1 e G2, que são descritos a seguir:
ponteiro de desreferência
Nos gráficos complementares de G1 e G2 acima, podemos ver que ambos os gráficos são isomorfismo.
∴ Os gráficos G1 e G2 são isomorfismo.
Exemplo 3:
Neste exemplo, mostramos se os gráficos a seguir são isomorfismo.
Solução: Para isso, verificaremos todas as quatro condições de isomorfismo de grafos, que são descritas a seguir:
Condição 1:
exemplos de programação python
- No gráfico 1, há um total de 8 vértices, ou seja, G1 = 8.
- No gráfico 2, há um total de 8 vértices, ou seja, G2 = 8.
Aqui,
Há um número igual de vértices em ambos os gráficos G1 e G2. Portanto, estes gráficos satisfazem a condição 1. Agora verificaremos a segunda condição.
Condição 2:
- No gráfico 1, o número total de arestas é 10, ou seja, G1 = 10.
- No gráfico 2, o número total de arestas é 10, ou seja, G2 = 10.
Aqui,
Há um número igual de arestas em ambos os gráficos G1 e G2. Portanto, estes gráficos satisfazem a condição 2. Agora verificaremos a terceira condição.
Condição 3:
- No gráfico 1, o grau da sequência s é {2, 2, 2, 2, 3, 3, 3, 3}, ou seja, G1 = {2, 2, 2, 2, 3, 3, 3, 3} .
- No gráfico 2, o grau da sequência s é {2, 2, 2, 2, 3, 3, 3, 3}, ou seja, G2 = {2, 2, 2, 2, 3, 3, 3, 3} .
Aqui
Há um número igual de sequências de graus em ambos os gráficos G1 e G2. Portanto, estes gráficos satisfazem a condição 3. Agora verificaremos a quarta condição.
Condição 4:
- O gráfico G1 forma um ciclo de comprimento 4 com a ajuda de vértices de grau 3.
- O gráfico G2 não está formando um ciclo de comprimento 4 com a ajuda de vértices porque os vértices não são adjacentes.
Aqui,
Ambos os gráficos G1 e G2 não formam o mesmo ciclo com o mesmo comprimento. Portanto, esses gráficos violam a condição 4.
Visto que os gráficos G1 e G2 violam a condição 4. Portanto, devido à violação da condição 4, esses gráficos não serão um isomorfismo.
∴ Os gráficos G1 e G2 não são um isomorfismo.