Seja
a grade 3 -por-4 e
a grade 4 -por-3. Os grafos
e
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:
, que é uma grade 3 por 4, e
, 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 (
) 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 (
) tem 4 linhas e 3 colunas. Visualmente,
é como um retângulo mais largo na horizontal, e
é um retângulo mais alto na vertical.
Passo 3
Agora, vamos ver se
e
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,
tem 12 vértices (3x4) e
também tem 12 vértices (4x3). Mas será que as conexões são as mesmas? Na verdade, se você girar
em 90 graus, ele fica igual a
. 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
a um vértice de
de forma que as conexões sejam mantidas. Pense que estamos girando
em 90 graus para obter
. Se rotacionarmos as coordenadas dos vértices de
, conseguimos essa correspondência.
Mais especificamente, se um vértice em
tem coordenadas
(linha
, coluna
), no bijecção ele vai para o vértice com coordenadas
em
.
Passo 6
Vamos formalizar essa bijeção. Definimos uma função
onde cada vértice
de
é mapeado para o vértice
de
. Aqui,
e
representam os conjuntos de vértices de
e
, respectivamente.
Passo 7
Agora, precisamos verificar se essa bijeção
realmente preserva as conexões. Ou seja, se dois vértices estão conectados em
, seus correspondentes em
também devem estar conectados.
Como
simplesmente troca as coordenadas, as adjacências horizontais em
viram adjacências verticais em
e vice-versa. Portanto, todas as conexões são preservadas.
Resposta
Sim, os grafos
e
são isomorfos. Uma bijeção que estabelece esse isomorfismo é
, onde cada vértice
de
é mapeado para o vértice
de
.