Representação de grafos no computador

Introdução
Construímos um programa que contém campos para inserir dois grafos, os quais serão submetidos a verificações diversas.
Estas verificações vão resultar em informar se os grafos aqui dispostos são
ISOMORFOS ou NÃO.

Isomorfismo
Dois grafos G1(V1,E1) e G2(V2,E2) são ditos isomorfos entre si se existe uma correspondência entre os seus vértices e arestas de tal maneira que a relação de incidência seja preservada. Em outros termos, temos |V 1|= |V2| e existe uma função unívoca f: V1-->V2, tal que (i,j) é elemento de E1 se e somente se (ƒ(i),f(j)) é elemento de E2. Eis alguns exemplos de grafos isomorfos:

Figura 5
Para ver o isomorfismo dos grafos da figura 5, podemos utilizar a seguinte função: f(a) = 1, f(b) = 2, f(c) = 3, f(d) = 8, f(e) = 5, f(f) = 6, f(g) = 7, f(h) = 4.

Figura 6
Para ver o isomorfismo dos grafos 6(a) e 6(b), utilize a seguinte função: f(a) = s, f(b) = t, f(c) = u, f(d) = v, f(e) = r, f(f) = m, f(g) = n, f(h) = o, f(i) = p, f(j) = q
Para ver o isomorfismo dos grafos 6(a) e 6(c), utilize a seguinte função: f(a) = 1, f(b) = 10, f(c) = 4, f(d) = 5, f(e) = 6, f(f) = 2, f(g) = 9, f(h) = 3, f(i) = 8, f(j) = 7.
Esses exemplos devem ser suficientes para mostrar que não é sempre fácil determinar se dois grafos são isomorfos. Não existe atualmente um alg oritmo eficiente para resolver esse problema. Poderíamos tentar todas as permutações possíveis, mas isso daria um algoritmo de complexidade em O(n!). Para que dois grafos sejam isomorfos, no mínimo essas condições têm que ser respeitadas:
1. Os dois têm o mesmo número de vértices.
2. Os dois têm o mesmo número de arestas.
3. Os dois têm o mesmo número de vértices de grau n, para qualquer valor n entre 0 e o número de vértices que o grafo contém.
Note que isso não é suficiente par que sejam isomorfos. Por exemplo , os grafos da figura 7 respeitam essas condições e não são isomorfos.

Figura 7
Mesmo se ambos os grafos são regulares de grau k, as condições acima