Isomorfismos
Definição de isomorfismo
Dois grafos
G1=(V1,A1) e
G2=(V2,A2)
dizem-se isomorfos se existirem correspondências
bijectivas respectivamente entre os conjuntos de vértices
V1 e V2,
e entre os conjuntos de arestas
A1 e A2,
tais que:
- dada uma aresta de G1
e a sua imagem em G2
as respectivas extremidades estão em
correspondência bijectiva,
- dado um par de vértices em G1
e o par imagem em G2 as
arestas que ligam o primeiro par estão
em correspondência bijectiva com as arestas
que unem o segundo par.
O par de correspondências bijectivas,
entre os conjuntos de vértices e de arestas,
diz-se um isomorfismo entre os
dois grafos.
Se um grafo é simples
é claro que um isomorfismo fica determinado pela
correspondência bijectiva entre os respectivos vértices.
A relação de isomorfia é uma relação
de equivalência. Significa isto que
- Todo o grafo é isomorfo a si mesmo.
(reflexividade)
- Se grafo é isomorfo a um segundo grafo então também
o segundo é isomorfo ao primeiro.
(simetria)
- Se um grafo é isomorfo a um segundo, que por sua vez
é isomorfo a um terceiro grafo, então o
o primeiro é isomorfo ao terceiro.
(transitividade)
A classe de isomorfia de um grafo é, por definição,
o conjunto de todos os outros grafos (incluindo o
próprio) que lhe são isomorfos.
Porque a relação de isomorfia é uma relação de
equivalência as classes de isomorfia são
disjuntas duas a duas e o universo
de todos os grafos fica
dividido nas classes de isomorfia.
Alguns exemplos: