Seja G a grade 3 -por-4 e H a grade 4 -por-3. Os grafos G e H são iguais? Eles são isomorfos? Em caso afirmativo, indique a bijeção.

Passo 1

Beleza, vamos lá! O que a gente está vendo aqui são dois grafos chamados de grades: G, que é uma grade 3 por 4, e H, que é uma grade 4 por 3. Nosso objetivo é descobrir se esses dois grafos são iguais ou se pelo menos são isomorfos. Para isso, vamos precisar entender conceitos de igualdade de grafos, isomorfismo de grafos e o que é uma bijeção entre os conjuntos de vértices.

Passo 2

Primeiro, vamos entender o que são essas grades que o exercício menciona. Uma grade 3 por 4 ( G) tem 3 linhas e 4 colunas de vértices, conectados por arestas que indicam adjacência (como em um tabuleiro). Já a grade 4 por 3 ( H) tem 4 linhas e 3 colunas. Visualmente, G é como um retângulo mais largo na horizontal, e H é um retângulo mais alto na vertical.

Passo 3

Agora, vamos ver se G e H são iguais. Dois grafos são iguais se tiverem exatamente os mesmos vértices e as mesmas conexões entre eles. Olhando para as dimensões, G tem 12 vértices (3x4) e H também tem 12 vértices (4x3). Mas será que as conexões são as mesmas? Na verdade, se você girar G em 90 graus, ele fica igual a H. Então, eles não são exatamente iguais na disposição original, mas têm a mesma estrutura.

Passo 4

Como os grafos não são iguais exatamente, vamos verificar se eles são isomorfos. Dois grafos são isomorfos se existe uma bijeção (uma correspondência um-para-um) entre seus conjuntos de vértices que preserva as conexões. Ou seja, conseguimos “renumerar” os vértices de um grafo para que fique igual ao outro.

Passo 5

Para encontrar essa bijeção, vamos associar cada vértice de G a um vértice de H de forma que as conexões sejam mantidas. Pense que estamos girando G em 90 graus para obter H. Se rotacionarmos as coordenadas dos vértices de G, conseguimos essa correspondência.
Mais especificamente, se um vértice em G tem coordenadas (i, j) (linha i, coluna j), no bijecção ele vai para o vértice com coordenadas (j, i) em H.

Passo 6

Vamos formalizar essa bijeção. Definimos uma função f: V(G) V(H) onde cada vértice (i, j) de G é mapeado para o vértice (j, i) de H. Aqui, V(G) e V(H) representam os conjuntos de vértices de G e H, respectivamente.

Passo 7

Agora, precisamos verificar se essa bijeção f realmente preserva as conexões. Ou seja, se dois vértices estão conectados em G, seus correspondentes em H também devem estar conectados.
Como f simplesmente troca as coordenadas, as adjacências horizontais em G viram adjacências verticais em H e vice-versa. Portanto, todas as conexões são preservadas.

Resposta

Sim, os grafos G e H são isomorfos. Uma bijeção que estabelece esse isomorfismo é f(i, j) = (j, i), onde cada vértice (i, j) de G é mapeado para o vértice (j, i) de H.

Exercícios relacionados