Introdução

Análise da matriz de adjacência

A matriz de adjacência de um grafo representa toda relação de correspondência entre os vértices e as arestas. A construção da matriz de adjacência é feita de modo que a posição da linha e coluna atribuída a um vértice será feita de forma arbitraria, sem destruir a relação de incidência. Dependendo do modo em que os vértices estão arrumados nas linhas e colunas da matriz é possível obter uma representação de correspondência em diferentes matrizes de adjacência. Podemos considerar que cada matriz de adjacência de um mesmo grafo representa outro grafo isomorfo. Veja o exemplo abaixo:

Exemplo de matrizes de adjacência para um mesmo grafo

Força Bruta

Permutando a matriz de adjacência

Ao realizar permutação entre as linhas e as colunas é possível obter matrizes de adjacência que matém a relação de correspondência entre os vértices. Cada permutação na matriz equivale a um grafo isomorfo.

Algoritmo

Um algoritmo simples, porém muito custoso computacionalmente, é o algoritmo que realiza permutaçãoes entre as linhas e as colunas da matriz de adjacência de um dos grafos. Para cada permutação realizada em G1 deve verificar se essa nova matriz é idêntica a matriz de G2. O algoritmo deve realizar esse procedimento para cada permutação possível em G1.

Devido a necessidade de trabalhar com permutações esse algoritmo é conhecido como Força Bruta, pois realiza testes baseados em condições "aleatórias" que podem estar próximas ou distantes da solução.

Este algoritmo possui, dependendo da quantidade de vértices, um número muito elevado de repetições. Para um grafo com 20 vértices o algoritmo pode realizar até 20! (20!=2432902008176640000) trocas de linhas e colunas, e testes de comparação em uma matriz de dimensão 20x20.