Isomorfismo pelo método da força bruta
Document Actions
Note: This is the print view with all the tutorial pages on one page. The paginated version is available here, if you prefer that.
Introdução
O que é Isomorfismo?
Em teoria dos grafos, isomorfismo define a preservação de incidência entre dois grafos, ou seja, dois grafos são ditos isomorfos se para todo vértice e aresta existente em G1 existe um correspondente em G2. Em outras palavras dois grafos são isomorfos se:
- Os dois têm o mesmo número de vértices.
- Os dois têm o mesmo número de arestas.
- Os dois têm o mesmo número de vértices de grau n.
- Os dois têm o mesmos vértices de grau n, ligados aos mesmos vértices de graun.
- Todos subgrafos existentes em G1, devem existir em G2
Exemplos:
 |
| Exemplo de grafos isomorfos |
 |
| Exemplo de grafos isomorfos |
Método da força bruta
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.
Implementação do código
Realizando permutações
O código abaixo realiza a permutação entre índices nas linhas através do método ChangeMatrixRows() e nas coluns através do método ChangeMatrixCols().
Perceba que o parametro aIndexes[], existente nos dois métodos, é o vertor que possui a permutação que deve ser realiza. Nesse vetor o valor presente no índice i é o número que indica a troca da linha/coluna i pela linha/coluna aIndexes[i].
O método cloneMatrix() retorna a cópia de uma nova instância da matriz que foi passada como parametro.
//
// ChangeMatrixRows - Troca linhas de uma matrix
private void ChangeMatrixRows( int aMatrix[][], int aIndexes[] ) {
int aSourceMatrix[][] = this.cloneMatrix( aMatrix);
for ( int x = 0; x < aMatrix.length; x++ )
for ( int y = 0; y < aMatrix.length; y++ )
aMatrix[x][y] = aSourceMatrix[aIndexes[x]][y];
}
//
// ChangeMatrixCols - Troca colunas de uma matrix
private void ChangeMatrixCols( int aMatrix[][], int aIndexes[] ) {
int aSourceMatrix[][] = this.cloneMatrix( aMatrix);
for ( int y = 0; y < aMatrix.length; y++ )
for ( int x = 0; x < aMatrix.length; x++ )
aMatrix[x][y] = aSourceMatrix[x][aIndexes[y]];
}
Executando o algoritmo de força bruta
O algoritmo de força bruta consiste em:
- Obter permutação da ordem dos vértices
- Obter uma cópia de G2
- Realizar permutação das linhas em G2
- Realizar permutação das colunas em G2
- Comparar G1 com G2
- Se G1 fo igual G2 para execução, se forem diferentes repete os passos anteriores
Nessa implementação a calsse que gera permutações (GenratorPermutation) foi obtida em http://www.merriampark.com/perm.htm.
As variáveis aAdjGraph1 e aAdjGraph2 são as matrizes de adjacência dos grafos G1 e G2.
A variável aVertexRelationshipMap é um vertor que indica a relação de correspondência entre os vértices dos grafos G1 e G2.
//
// PermutationAnalysis - Realiza permutações para tentar obter grafo isomorfo.
private boolean PermutationAnalysis() {
// Obtém Gerador de permutações
PermutationGenerator aPermut = new PermutationGenerator( this.aAdjGraph2.length );
// Enquanto houver permutações...
while ( aPermut.hasMore()) {
// Obtém próxima permutação
int aIndexes[] = aPermut.getNext();
// Obtém uma cópia temporaria da matrix que será modificada
int aTempAnalisysMatrix[][] = this.cloneMatrix( this.aAdjGraph2 );
// Troca as linhas reais pelas linhas da permutação atual.
this.ChangeMatrixRows( aTempAnalisysMatrix, aIndexes );
// Troca as Colunas reais pelas colunas da permutação atual.
this.ChangeMatrixCols( aTempAnalisysMatrix, aIndexes );
// Compara as matrizes
if ( this.CompareMatrix( this.aAdjGraph1, aTempAnalisysMatrix )) {
this.aVertexRelationshipMap = aIndexes;
return true;
}
}
return false;
}
Carregando os grafos com o roxGt
A API do roxGt fornece um método para carregar um arquivo .graph e também um metódo para obter a matriz de adjacência de um grafo carregado.
// Carrega arquivo que contém o grafo IGraph oGraph1 = GraphUtils.getInstance().getGraph( "myGraph.graph" ); IGraph oGraph2 = GraphUtils.getInstance().getGraph( "myGraph1.graph" ); // Obtém matrizes de ajacência int oAdjGraph1[][] = GraphUtils.getInstance().getAdjacencyMatrix( oGraph1 ); int oAdjGraph2[][] = GraphUtils.getInstance().getAdjacencyMatrix( oGraph2 ); // Realiza análise IsomorphAnalysis oIsomorphAnalysis = new IsomorphAnalysis( oAdjGraph1, oAdjGraph2 ); boolean bIsIsomorph = oIsomorphAnalysis.getResult();
Forgot your password?
New user?
Introdução