GRAFOS - FT | Faculdade de Tecnologiamagic/ft024/isomorfismo.pdf · 2016-08-01 · Grafos e Aplicações Casamento de grafos Em determinadas situações, o isomorfismo entre grafos

MARCO ANTONIO GARCIA DE CARVALHOAbril de 2009

Grafos e Aplicações

GRAFOSIsomorfismo e Casamento de Grafos



Equivalência estrutural

-- Os vOs vértices e arestas dos grafos acima possuem os mesmos rótulosértices e arestas dos grafos acima possuem os mesmos rótulos-- É possível verificar que se dois nós É possível verificar que se dois nós ii e e jj de um grafo são vizinhos, de um grafo são vizinhos,também o são no outro grafotambém o são no outro grafo

2

0 1

3

4 5

6 7

7 6

32

5

4

1

0



Equivalência estrutural

-- Se os grafos nSe os grafos não possuem os mesmos rótulos, como no caso abaixo, éão possuem os mesmos rótulos, como no caso abaixo, épossível estabelecer um mapeamentopossível estabelecer um mapeamento

7

6

3

2

5

4

1

8

w

s

u

y

z

v t

x

através de uma função bijetora através de uma função bijetora ff

1 1 →→ s s 5 5 →→ w w2 2 →→ t t 6 6 →→ x x3 3 →→ u u 7 7 →→ y y4 4 →→ v v 8 8 →→ z z

G H



Equivalência estruturalNo grafo No grafo GG vê-se que o nó 1 é vizinho a 2, 3 e 5, não a outros vê-se que o nó 1 é vizinho a 2, 3 e 5, não a outros

No grafo No grafo HH vê-se que vê-se que s=f(1)s=f(1) é adjacente a é adjacente a t=f(2), u=f(3)t=f(2), u=f(3) e e w=f(5)w=f(5), mas, masnão a outros.não a outros.

Portanto, vê-se que a bijeção Portanto, vê-se que a bijeção f: Vf: VGG →→ V VHH também existe para a também existe para arelação de vizinhançarelação de vizinhança



Isomorfismo - definição

DefiniçãoDefiniçãoSeja Seja GG e e HH dois grafos simples. Uma bije dois grafos simples. Uma bijeção entre os nós ção entre os nós f: Vf: VGG →→ V VHH preserva a preserva aadjacência se para cada par de nós adjacentes adjacência se para cada par de nós adjacentes uu e e vv no grafo no grafo GG, os vértices , os vértices f(u)f(u)e e f(v)f(v) forem adjacentes no grafo forem adjacentes no grafo HH..

DefiniçãoDefiniçãoUma bijeUma bijeção entre os nós ção entre os nós f: Vf: VGG →→ V VHH preserva a estruturapreserva a estrutura se a estrutura de se a estrutura deadjacência e não-adjacência é preservada.adjacência e não-adjacência é preservada.



Isomorfismo - definição

ISOMORFISMOISOMORFISMODois grafos simples Dois grafos simples GG e e HH s são isomórficos, denotado por ão isomórficos, denotado por G G ≡≡ H H, se existe uma, se existe umapreservação da estrutura na bijeção dos nós preservação da estrutura na bijeção dos nós f: Vf: VGG →→ V VHH. Tal função . Tal função ff é chamada é chamadade isomorfismo entre de isomorfismo entre GG e e HH..

A generalizaA generalização do problema de isomorfismo entre grafos é chamado deção do problema de isomorfismo entre grafos é chamado demapeamento linear entre grafosmapeamento linear entre grafos, preserva a adjacência, mas não, preserva a adjacência, mas nãonecessariamente a não adjacência e não necessariamente é necessariamente a não adjacência e não necessariamente é bijetivabijetiva..

2

0 1

3

4 5

6 7

g=f(6)

f=f(5)

c=f(2)

b=f(1)

e=f(4)

d=f(3)

a=f(0)

h=f(7)



Isomorfismo

NNão existem algoritmos polinomiais para identificar se dois grafos sãoão existem algoritmos polinomiais para identificar se dois grafos sãoisomórficosisomórficos11..

Uma das formas deUma das formas de verificar se ocorre o isomorfismo entre dois grafosverificar se ocorre o isomorfismo entre dois grafos é provaré provarexatamente o contrário através do conceito de exatamente o contrário através do conceito de invarianteinvariante (propriedade que é(propriedade que épreservada pelo isomorfismo, como por exemplo, o número de nós e o grau).preservada pelo isomorfismo, como por exemplo, o número de nós e o grau).

1 1 R. C. R. C. ReadRead, D. G. , D. G. CorneilCorneil. . The graph isomorphism diseaseThe graph isomorphism disease. . Journal of Graph TheoryJournal of Graph Theory, , volvol. 1, . 1, pppp. 339-. 339-363, 1977.363, 1977.



Casamento de grafos

Em determinadas situaEm determinadas situações, o isomorfismo entre grafos pode não ser alcançadoções, o isomorfismo entre grafos pode não ser alcançadoe, portanto, é necessária uma outra metodologia para comparar a similaridadee, portanto, é necessária uma outra metodologia para comparar a similaridadeentre grafos.entre grafos.

As tAs técnicas que procuram determinar a correspondência entre grafos (nós e/ouécnicas que procuram determinar a correspondência entre grafos (nós e/ouarestas), sem que necessariamente seja preservada a estrutura, sãoarestas), sem que necessariamente seja preservada a estrutura, sãodenominadas de denominadas de casamento de grafoscasamento de grafos ( (graph matchinggraph matching).).

Portanto, os grafos nPortanto, os grafos não precisam ser necessariamente iguais para que hajaão precisam ser necessariamente iguais para que hajacasamento (correspondência) entre eles.casamento (correspondência) entre eles.

HHá diversas formas de calcular a correspondência entre grafos. Seráá diversas formas de calcular a correspondência entre grafos. Seráapresentada a seguir o casamento de grafos por meio de uma estruturaapresentada a seguir o casamento de grafos por meio de uma estruturarelacional denominada de relacional denominada de grafo associativografo associativo..



Casamento - Grafo Associativo (GA)

DefiniDefiniçãoçãoGrafo associativo Grafo associativo é uma estrutura relacional construída a partir de dois outrosé uma estrutura relacional construída a partir de dois outrosgrafos a fim de se determinar a correspondência (casamento) entre eles.grafos a fim de se determinar a correspondência (casamento) entre eles.

ConstruConstrução do GAção do GASejam dois grafos Sejam dois grafos GG11=(V=(V11,E,E11) ) ee G G22=(V=(V22,E,E22))..Um grafo associativo Um grafo associativo GA=(V,E)GA=(V,E) é o grafo:é o grafo:

- Para cada nó - Para cada nó vv11∈∈ VV1 1 e ve v22∈∈ V V22 construa um nó construa um nó vv de GA com rótulo ( de GA com rótulo (vv11,,vv22))- Conecte os nós de - Conecte os nós de GAGA caso os mesmos sejam caso os mesmos sejam compatíveiscompatíveis

A definiA definição de compatibilidade é dependente do problema. Um possível critérioção de compatibilidade é dependente do problema. Um possível critériopara o estabelecimento das arestas é o uso do para o estabelecimento das arestas é o uso do princípio da exclusãoprincípio da exclusão (unicidade (unicidadeda correspondência entre nós).da correspondência entre nós).




É dado um exemplo abaixo da construção de um É dado um exemplo abaixo da construção de um GAGA para 2 árvores para 2 árvores TT11 e e TT22..

GA

T1

T2




Aonde estAonde está uma possível solução para o problema de correspondência entre á uma possível solução para o problema de correspondência entre TT11 e eTT2 2 ? (CLIQUE)? (CLIQUE)



Grafo Associativo - Clique

1 1 B. Yang, W. E. B. Yang, W. E. SnyderSnyder, G. L. , G. L. BilbroBilbro. . Matching oversegmented Matching oversegmented 3D 3D images images to to models using associationmodels using associationgraphgraph. . Image and Vision ComputingImage and Vision Computing, , volvol. 7, no. 2, . 7, no. 2, pppp. 135-143, 1989.. 135-143, 1989.

ALGORITMOALGORITMO11 DeterminaDeterminação do clique máximo ção do clique máximo CmCm de um grafo associativode um grafo associativoEntrada: Grafo associativo Entrada: Grafo associativo GA = (V, E)GA = (V, E) e número de nós e número de nós nnSaída: Saída: Clique máximo Clique máximo CmCm

CC←∅←∅ % % cliques cliques de GAde GACmCm←∅←∅ % clique máximo de GA% clique máximo de GARotular os nós de GARotular os nós de GAPARA cada nó PARA cada nó ii até até nn FAÇA FAÇA SE rótulo( SE rótulo(ii)= )= ii ENTÃO ENTÃO C C ←← i i % novo clique % novo clique FIM SE FIM SE CLIQUE( CLIQUE(C, i, VC, i, V)) SE SE CC é é maximal maximal ENTÃOENTÃO Cm Cm ←← C C FIM SE FIM SEFIM PARAFIM PARA

FUNFUNÇÃOÇÃO CLIQUE (C, k, V)CLIQUE (C, k, V)PARA cada nó PARA cada nó jj←←k+1k+1 até até nn FAÇA FAÇA SE nó SE nó j j é vizinho de todos os nós em é vizinho de todos os nós em CC ENTÃO ENTÃO C C ←← C + {j} C + {j} rótulo(j) = rótulo(k) rótulo(j) = rótulo(k) CLIQUE(C, j, V) CLIQUE(C, j, V) FIM SE FIM SEFIM PARAFIM PARA

Documents

GRAFOS - FT | Faculdade de Tecnologiamagic/ft024/isomorfismo.pdf · 2016-08-01 · Grafos e Aplicações Casamento de grafos Em determinadas situações, o isomorfismo entre grafos