Grafos Isomorfos Matem tica Discreta

Grafos Isomorfos
• Dois grafos são isomorfos se ambos têm a mesma estrutura, ou seja, se existe um mapeamento dos seus conjuntos de vértices que preserve as adjacências; f₁ : 1 → c e₁ 2→b
2
3
3
2 ɑ₂ 3→d
4→a
ɑ₁ ɑ₂ a

1

4

1

ɑ₁

4

c

e₂

b

d

f₂: ɑ₁ → e₁ ɑ₂ → e₂

Eles têm os mesmos nós, os mesmos, arcos e a mesma função que associa as extremidades a cada arco.

Grafos Isomorfos
Definição: Dois grafos (N₁, A₁, g₁) e (N₂, A₂, g₂) são isomorfos se existem bijeções f₁ : N₁ → N₂ e f₂ : A₁ → A₂ tais que, para cada arco ɑ ∈ A₁, g₁ (ɑ) = x − y se, e somente se, g ₂[f₂ (ɑ)] = f₁ (x) − f₂ (y).

Grafos Isomorfos
• Isomorfismo encontrado:

f₁ : 1 → a
2→b
3→c
4→d

f₂: ɑ₁ → e₁ ɑ₂ → e₄ ɑ₃ → e₂ ɑ₄ → e₃ ɑ₅ → e₈ ɑ₆ → e₇ ɑ₇ → e₅ ɑ₈ →e₆

Grafos Isomorfos
• Teorema sobre Isomorfismo de Grafos simples: Dois grafos simples (N₁,A₁,g₁) e (N₂,A₂,g₂) são isomorfos se existe uma bijeção f : N₁ → N₂ tal que, onde quaisquer nós nᵢ e nj de N₁, nᵢ e nj são adjacentes se, e somente se, f(nᵢ) e f(nj) são adjacentes.(A função f é chamada um isomorfismo do grafo 1 no grafo 2). ∈ N₁

Grafos Isomorfos
• Pode-se mostrar que grafos não são isomorfos através de invariantes como:
1.Um grafo tem mais nós do que o outro
2.Um grafo tem mais arcos do que o outro
3.Um grafo tem arcos paralelos e o outro não
4.Um grafo tem um laço e outro não
5.Um grafo tem um nó de grau k e o outro não
6.Um grafo é conexo e o outro não
7.Um grafo tem um ciclo e o outro não

Grafos Isomorfos
• Prove que esses dois grafos não são isomorfos

(a)

(b)