Isomorfismo em Grafos

[Grafos Isomorfos] - Slide 1
Isomorfismo em Grafos
Renan Manola
[Grafos Isomorfos] - Slide 2
Sumário
●
Definição do Problema
●
Principais aplicações
●
Principais métodos de solução
●
Exemplo de solução
●
Conclusão
[Grafos Isomorfos] - Slide 3
Definição do Problema
●
●
Dois grafos são isomorfos se ambos têm a mesma estrutura, ou seja, se existe um mapeamento dos seus conjuntos de vértices que preserve as adjacências;
Matematicamente:
–
Seja G1(V1,E1) e G2(V2,E2) dois grafos, são isomorfos se: |V1|= |V2| 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
[Grafos Isomorfos] - Slide 4
Principais Aplicações
●
●
Processamento de Imagem
–
Impressões digitais
–
Tomografia
–
Análise de cenas
Química Orgânica
–
Compostos e Subcompostos
●
Braços Mecânicos
●
...
[Grafos Isomorfos] - Slide 5
Principais Métodos de Solução
●
Força Bruta O(n!)
●
Nauty (Brendan D. McKay) (1981)
●
Hopcroft – Wong (Linear Time Algorithm for Isomorphism of Planar Graphs) (1974)
●
●
Algoritmo de Tempo Polinomial (Dharwadker­Tevet) (Fev – 2009)
Cordella, Foggia, Vento (An Efficient Algorithm for the Inexact Matching of ARG Graphs Using a Contextual Transformational Model) (1996)
[Grafos Isomorfos] - Slide 6
Exemplo de Solução
●
Algoritmo: Ashay Dharwadker and John­
Tagore Tevet ­ THE GRAPH ISOMORPHISM ALGORITHM – 2009
●
Definições:
–
Collateral Graph (G\uv)
–
Pair Graph: G uv
–
Sign Matrix
●
suv =± d uv . n uv . m uv
[Grafos Isomorfos] - Slide 7
Exemplo Prático
●
G1 G2
[Grafos Isomorfos] - Slide 8
Exemplo Prático
●
●
Para todos os pares, encontrar:
–
Distância entre eles;
–
Número de vértices de
–
Número de Arestas de
Em encontrar menores caminhos de 1 para todo resto e encontrar menores caminhos de 2 para todo o resto.
[Grafos Isomorfos] - Slide 9
Exemplo Prático
●
●
Descobre­se que: d(1,2) = 2.
Obter menores caminhos de 1 a 2: (1,7,2), (1,8,2), (1,4,2), (1,5,2),(1,6,2)
●
Tais nós compõe o “Pair Graph” de 1,2 ( )
●
Com isso pode­se concluir que ●
●
Sinal negativo pois 1 e 2 não possuem ligação direta por uma aresta.
[Grafos Isomorfos] - Slide 10
Exemplo Prático
●
●
●
Montar matriz de sinais para os demais pares. Lembrando que:
Lembrando também que:
[Grafos Isomorfos] - Slide 11
Exemplo Prático
[Grafos Isomorfos] - Slide 12
Exemplo Prático
[Grafos Isomorfos] - Slide 13
[Grafos Isomorfos] - Slide 14
[Grafos Isomorfos] - Slide 15
[Grafos Isomorfos] - Slide 16
Exemplo Prático
●
●
Mapeamentos do Isomorfismo: