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: 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 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: