O que são grafos isomorfos? Desenhe um exemplo.
Passo 1
O enunciado pede para definir o que são grafos isomorfos e depois ilustrar com um exemplo desenhado. O conteúdo é da teoria de grafos, e vamos precisar usar a definição de isomorfismo entre grafos.
Passo 2
Dois grafos G₁ e G₂ são isomorfos se existe uma bijeção f entre seus conjuntos de vértices de modo que, para quaisquer vértices u e v de G₁, u–v é aresta em G₁ se, e somente se, f(u)–f(v) é aresta em G₂. Ou seja, f preserva adjacências.
Passo 3
Para ilustrar, construí dois grafos de quatro vértices cada, ambos formando um ciclo: G₁ com vértices {1,2,3,4} e arestas {1–2,2–3,3–4,4–1}, e G₂ com vértices {A,B,C,D} e arestas {A–B,B–C,C–D,D–A}. A bijeção f que mostra o isomorfismo é f(1)=A, f(2)=B, f(3)=C, f(4)=D, que leva cada aresta de G₁ numa aresta de G₂.
Segue o “desenho” em ASCII para visualizar o exemplo:
G₁:
1 —— 2
| |
4 —— 3
Segue o “desenho” em ASCII para visualizar o exemplo:
G₁:
1 —— 2
| |
4 —— 3
G₂:
A —— B
| |
D —— C
A —— B
| |
D —— C
Como cada conexão em G₁ corresponde a uma em G₂ via f, esses grafos são isomorfos.
Resposta
Dois grafos são isomorfos quando existe uma bijeção f entre seus vértices que preserva as arestas: para quaisquer vértices u,v de G₁, u–v está em E(G₁) se, e somente se, f(u)–f(v) está em E(G₂).
Exemplo desenhado (ciclo de 4 vértices):
G₁:
1 —— 2
| |
4 —— 3
1 —— 2
| |
4 —— 3
G₂:
A —— B
| |
D —— C
A —— B
| |
D —— C
A bijeção que mostra o isomorfismo é f(1)=A, f(2)=B, f(3)=C, f(4)=D.