Um Algoritmo para o Problema do Isomorﬁsmo de Grafosposcomp.ufabc.edu.br/images/uploaded_files/dissertacoesDefendidas/... · No Capítulo 3, é apresentado o Problema do Isomorﬁsmo

Universidade Federal do ABC

Curso de Pós-Graduação em Ciência da Computação

Dissertação de Mestrado

Edilson José Rodrigues

Um Algoritmo para o Problema do

Isomorfismo de Grafos

Santo André

2014

Universidade Federal do ABC

Curso de Pós-Graduação em Ciência da Computação

Dissertação de Mestrado

Edilson José Rodrigues

Um Algoritmo para o Problema do


Trabalho apresentado como requisito par-cial para a obtenção do título de Mestre emCiência da Computação, sob orientação doProfessor Doutor Daniel Morgato Martin.

Santo André

2014

Resumo

Neste trabalho estudamos o Problema do Isomorfismo de Grafos e a sua comple-xidade para resolvê-lo. Nossa principal contribuição é a proposta de um algoritmopara o caso geral do Problema, baseado no particionamento do conjunto de vérticese em emparelhamentos perfeitos de grafos bipartidos.Estudamos também o algoritmo de Brendan McKay, que é o mais rápido algoritmopara o Problema do Isomorfismo de Grafos conhecido. Ao final, implementamos oalgoritmo proposto nesta dissertação e o algoritmo de McKay.Após a comparação dos dois algoritmos, verificamos que os resultados obtidos peloalgoritmo proposto não foram satisfatórios, porém apresentamos possíveis melhoriasde como deixá-lo mais eficiente.

Palavras-chave: Problema do Isomorfismo de Grafos. Emparelhamentos em grafosbipartidos. Particionamento do conjunto de vértices.

Abstract

In this work we study the Graph Isomorphism Problem and their complexity tosolve it. Our main contribution is to propose an algorithm for the general case ofthe Problem, based on partitioning the set vertex and perfect matchings of bipartitegraphs.We also studied the Brendan McKay’s algorithm, who is the fastest algorithm forthe Graph Isomorphism Problem known. At the end, we implemented the algorithmproposed in this dissertation and McKay’s algorithm.After comparison of the two algorithms, we found that the results obtained by theproposed algorithm were not satisfactory, but improvements are possible as to makeit more efficient.

Key words: Graph Isomorphism Problem. Matchings in bipartite graphs. Partiti-oning of vertex set.

Agradecimentos

Agradeço primeiramente a Deus, a minha esposa Taís, aos meus pais José eMaria, ao meu orientador Prof. Dr. Daniel Martin, a UFABC, e todos aqueles que,direta ou indiretamente me ajudaram na realização deste trabalho.

Conteúdo

1 Introdução xi

1.1 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi1.2 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xii1.3 Estrutura do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . . xii

2 Preliminares 1

2.1 Definições básicas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.1.1 Grafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12.1.2 Vizinhança e grau . . . . . . . . . . . . . . . . . . . . . . . . 22.1.3 Subgrafo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22.1.4 Representações de grafos no plano . . . . . . . . . . . . . . . 3

2.2 Isomorfismo de grafos . . . . . . . . . . . . . . . . . . . . . . . . . . 42.3 Simetrias em grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52.4 Problemas computacionais . . . . . . . . . . . . . . . . . . . . . . . . 7

2.4.1 Classes de problemas . . . . . . . . . . . . . . . . . . . . . . . 82.4.2 NP-Completo . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Isomorfismo de Grafos 11

3.1 Problema do Isomorfismo de Grafos . . . . . . . . . . . . . . . . . . 113.2 Problema do Automorfismo de Grafos . . . . . . . . . . . . . . . . . 133.3 Relação entre os problemas . . . . . . . . . . . . . . . . . . . . . . . 133.4 Problema do Isomorfismo de Subgrafos . . . . . . . . . . . . . . . . . 143.5 Aplicações práticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

3.5.1 Impressões digitais . . . . . . . . . . . . . . . . . . . . . . . . 153.5.2 Zero knowledge proof . . . . . . . . . . . . . . . . . . . . . . 153.5.3 Aplicações em química . . . . . . . . . . . . . . . . . . . . . . 173.5.4 Outras aplicações . . . . . . . . . . . . . . . . . . . . . . . . . 17

3.6 Revisão bibliográfica . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4 Emparelhamentos em grafos bipartidos 19

4.1 Definições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194.2 Encontrando um emparelhamento máximo . . . . . . . . . . . . . . . 204.3 Enumerando os emparelhamentos perfeitos . . . . . . . . . . . . . . 24

4.3.1 Componentes fortemente conexas . . . . . . . . . . . . . . . . 254.3.2 Gerando novos emparelhamentos . . . . . . . . . . . . . . . . 294.3.3 Análise de complexidade . . . . . . . . . . . . . . . . . . . . . 32

5 Algoritmo para o Problema do Isomorfismo de Grafos 35

5.1 Simulação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 365.1.1 Efeitos de uma p-simulação . . . . . . . . . . . . . . . . . . . 375.1.2 Partições . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 385.1.3 Partição associada a uma rodada . . . . . . . . . . . . . . . . 395.1.4 Algoritmo para uma p-simulação . . . . . . . . . . . . . . . . 405.1.5 Árvore de partição . . . . . . . . . . . . . . . . . . . . . . . . 42

5.2 Propriedades de uma p-simulação . . . . . . . . . . . . . . . . . . . . 445.3 Algoritmo proposto . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

5.3.1 Emparelhamentos perfeitos e isomorfismo . . . . . . . . . . . 50

6 Algoritmo Pratical Graph Isomorphism 53

6.1 Rotulação canônica e isomorfo canônico . . . . . . . . . . . . . . . . 546.2 Refinamento de partições . . . . . . . . . . . . . . . . . . . . . . . . 556.3 Algoritmo de refinamento . . . . . . . . . . . . . . . . . . . . . . . . 566.4 Partições aninhadas . . . . . . . . . . . . . . . . . . . . . . . . . . . 596.5 Árvore de busca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 596.6 Podando a árvore de busca . . . . . . . . . . . . . . . . . . . . . . . 63

7 Resultados 65

7.1 Gerador de grafos aleatórios - instâncias positivas . . . . . . . . . . . 667.1.1 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66

7.2 Grafos com alto padrão de simetria . . . . . . . . . . . . . . . . . . . 687.2.1 Grafos fortemente regulares não isomorfos . . . . . . . . . . . 68

8 Considerações Finais 71

8.1 Trabalhos futuros . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

Bibliografia 73

9 Anexo 78

Lista de Figuras

2.1 Grafo completo com 4 vértices. . . . . . . . . . . . . . . . . . . . . . 22.2 H é subgrafo de G . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.3 Um grafo planar. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32.4 Dois grafos isomorfos. . . . . . . . . . . . . . . . . . . . . . . . . . . 42.5 Hipercubo de dimensão 3. . . . . . . . . . . . . . . . . . . . . . . . . 62.6 Um grafo rígido. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

4.1 Grafo dirigido por um emparelhamento perfeito. . . . . . . . . . . . 214.2 Componentes fortemente conexas em um digrafo ~D. . . . . . . . . . 26

5.1 Simulação em um grafo G . . . . . . . . . . . . . . . . . . . . . . . . 375.2 Grafo G rotulado . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.3 Árvore de partição. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 435.4 Exemplos de partições. . . . . . . . . . . . . . . . . . . . . . . . . . . 495.5 Exemplo de árvore de recursão do Algoritmo 15. . . . . . . . . . . . 50

6.1 Grafo G. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616.2 Árvore T (G). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

7.1 Partição π obtida após uma simulação em um grafo fortemente regular. 70

Lista de Tabelas

2.1 Um isomorfismo entre G e H. . . . . . . . . . . . . . . . . . . . . . . 5

7.1 Grafos aleatórios densos. . . . . . . . . . . . . . . . . . . . . . . . . . 667.2 Grafos aleatórios esparsos. . . . . . . . . . . . . . . . . . . . . . . . . 677.3 Grafos fortemente regulares isomorfos. . . . . . . . . . . . . . . . . . 687.4 Grafos fortemente regulares não isomorfos. . . . . . . . . . . . . . . . 70

Lista de Siglas

PAG Problema do Automorfismo de Grafos

PGI Pratical Graph Isomorphism

PIG Problema do Isomorfismo de Grafos

ZKP Zero knowledge proof

CAPÍTULO 1

Introdução

1.1 Objetivos

Este trabalho tem como finalidade estudar o Problema do Isomorfismo de Grafos.

Nesse problema, o conjunto de instâncias válidas são pares {G,H} de grafos finitos,

e o objetivo é decidir se os grafos G e H são isomorfos, isto é, se possuem a mesma

estrutura subjacente.

A principal contribuição deste trabalho é a proposta de uma nova abordagem

para o Problema do Isomorfismo de Grafos baseada num algoritmo desenvolvido

por McKay [25] em 1981 e que utiliza fortemente o conceito de emparelhamentos em

grafos bipartidos e tópicos relacionados. Nossa proposta consiste em distinguir os

vértices de um grafo através de um processo de simulação e posteriormente utilizar o

resultado dessas simulações para acelerar um algoritmo de força bruta que enumera

mapas entre G e H na busca de um possível isomorfismo entre esses grafos.

O objetivo específico deste trabalho é apresentar um algoritmo que execute, na

prática, em um tempo razoável. É sabido que os algoritmos conhecidos para o caso

geral do Problema do Isomorfismo de Grafos possuem complexidade de tempo expo-

Capítulo 1. Introdução xii

nencial, demandando muito tempo de processamento (a complexidade do Problema

e o consumo de tempo dos algoritmos serão abordados no Capítulo 3).

1.2 Motivação

O Problema do Isomorfismo de Grafos tem uma vasta gama de aplicabilidade prática

em diversas áreas de conhecimento, e por isso resolvemos estudá-lo. No Capítulo 3,

mostraremos uma série de aplicações práticas do problema.

1.3 Estrutura do trabalho

Esta monografia, que doravante será chamada de dissertação, está dividida em seis

capítulos, além deste breve capítulo introdutório: o Capítulo 2 introduz os principais

conceitos e definições da teoria dos grafos que são utilizados ao longo da dissertação.

No Capítulo 3, é apresentado o Problema do Isomorfismo de Grafos, com definições,

resultados relacionados e aplicações. O Capitulo 4 aborda o conceito de emparelha-

mentos em grafos bipartidos que servirá de base para o algoritmo apresentado no

Capítulo 5. No Capítulo 6 apresentamos o Algoritmo proposto por McKay, compa-

rando as diferenças e semelhanças com o algoritmo apresentado nesta dissertação.

O último Capítulo 7 apresenta os resultados obtidos, bem como os detalhes da sua

implementação na linguagem C++.

CAPÍTULO 2

Preliminares

2.1 Definições básicas

Neste capítulo serão introduzidas algumas definições e notações necessárias para

que o problema considerado nesta dissertação seja descrito de forma precisa. Essas

definições foram baseadas nas referências [18], [34], [22], [28], [6], [5] e [12].

2.1.1 Grafo

Um grafo é um par ordenado (V,E) onde V é um conjunto finito não vazio, e E é

um conjunto de pares não ordenados de elementos de V . O conjunto V é chamado

de conjunto de vértices1, e E de conjunto de arestas. Quando um grafo G não é

definido de maneira explícita, usa-se V (G) e E(G) para fazer referência aos conjuntos

de vértices e de arestas de G respectivamente.

1Neste trabalho, é comum supor que o conjunto V é o conjunto de números naturais {1, . . . , n}para algum n.

Capítulo 2. Preliminares 2

2.1.2 Vizinhança e grau

Se u e v são vértices de um grafo, e a = {u, v} é uma aresta desse grafo, diz-se que

u e v são vizinhos ou vértices adjacentes, ou ainda que estão ligados pela aresta a.

Dizemos ainda que u e v são as pontas ou extremidades da aresta a. O conjunto de

vizinhos de um vértice v num grafo G é denotado por NG(v), ou seja, tem-se

NG(v) ={

u ∈ V (G) : {u, v} ∈ E(G)}

.

O grau de um vértice v em um grafo G é o número de vizinhos de v em G, ou seja,

é o número de elementos de NG(v). Denota-se o grau de v por dG(v). Quando o

grafo G puder ser identificado pelo contexto, denotamos NG(v) e dG(v) simplesmente

por N(v) e d(v) respectivamente. Quando todos os vértices de um grafo possuem

grau d, diz-se que esse grafo é d-regular.

0 1

2 3

G

Figura 2.1: Grafo completo com 4 vértices.

Na Figura 2.1, o grafo G é 3-regular. O grafo completo de ordem n é um grafo

Kn = (V,E), onde V = {1, 2, . . . , n}, que possui todas as arestas, isto é, com

E ={{u, v} : {u, v} ⊆ V }

.

2.1.3 Subgrafo

Um grafo H é um subgrafo de um grafo G se VH ⊆ VG e EH ⊆ EG.

3 2.1. Definições básicas

G

1

2 3

5 4

32

5

H

4

Figura 2.2: H é subgrafo de G

Na figura 2.2, o grafo H é um subgrafo de G.

2.1.4 Representações de grafos no plano

O objeto grafo leva esse nome porque pode ser representado graficamente de modo

natural. Pode-se representar os vértices de um grafo por pontos no plano, e as

arestas desse grafo por curvas que ligam pares de pontos. Há infinitas maneiras

de se representar um mesmo grafo no plano, e cada uma delas é chamada de uma

imersão no plano.

Um grafo é planar se possui uma imersão no plano de modo que nenhum par de

arestas se cruze.

K4

1 2

34

Figura 2.3: Um grafo planar.

Na figura 2.3 temos um exemplo de um grafo planar. O objetivo deste trabalho

não é estudar representações de grafos no plano, mas esses conceitos serão utilizados


para ilustrar e exemplificar ideias.

2.2 Isomorfismo de grafos

Os grafos da Figura 2.4 compartilham algumas propriedades entre si (como o número

de vértices e de arestas), dando a impressão que são dois grafos iguais.

G

1 2 3

4 5 6

H

1 2 3

4 5 6

Figura 2.4: Dois grafos isomorfos.

Claramente, esses grafos não são iguais pois seus respectivos conjuntos de arestas

não são os mesmos: G possui a aresta {2, 4} e H não; G possui a aresta {2, 6}

e H não; H possui a aresta {4, 5} enquanto G não a possui. No entanto, pode-se

dizer que, de algum modo, esses grafos compartilham certas propriedades, como

conjunto de vértices e padrão de vizinhanças. A definição a seguir, que é central

nesta dissertação, formaliza o que acabamos de dizer.

Dois grafos G e H são isomorfos se há uma bijeção ϕ : V (G) → V (H) tal que,

para todo par de vértices i, j ∈ V (G), tem-se

{i, j} ∈ E(G) ⇐⇒ {ϕ(i), ϕ(j)} ∈ E(H).

Uma bijeção com esta propriedade é chamada de isomorfismo. Se G e H são iso-

morfos, denota-se esse fato pela expressão G ∼= H.

O conjunto de todos os isomorfismos entre G e H é denotado por Iso(G,H).

5 2.3. Simetrias em grafos

Note que Iso(G,H) é um conjunto de funções.

A Tabela 2.1 mostra um isomorfismo entre os grafos G e H da Figura 2.4.

Tabela 2.1: Um isomorfismo entre G e H .

i 1 2 3 4 5 6ϕ(i) 1 5 3 4 2 6

Seja G = (V,E) um grafo e seja K o conjunto de todos os pares não ordenados

de V . Então G = (V,K\E) é chamado de grafo complementar de G, ou simples-

mente, de complemento de G. É um fato simples que, se G ∼= H, então G ∼= H.

2.3 Simetrias em grafos

Alguns grafos, como o da Figura 2.5 são visualmente simétricos2. O grafo da Fi-

gura 2.5 é chamado de cubo. Em geral, um hipercubo de dimensão n é um grafo

Qn = (V,E) onde os conjuntos V e E são dados por

V = {0, 1}n

E = {{u, v} ⊆ V | u difere de v em apenas um bit}

2O conceito de grafo simétrico será enunciado após o conceito de automorfismo


Q3

000 001

010 011 100

101

110 111

Figura 2.5: Hipercubo de dimensão 3.

O hipercubo de dimensão n > 3 também é simétrico, embora não seja tão fácil

de se perceber isso pela observação de uma imersão do Qn no plano. Para forma-

lizar o conceito de simetrias em grafos de modo abstrato utilizamos o conceito de

automorfismo.

Um automorfismo de um grafo G = (V,E) é uma permutação3 ϕ : V → V que

preserva as adjacências em G, isto é, que satisfaz

{i, j} ∈ E ⇐⇒ {ϕ(i), ϕ(j)} ∈ E

para todo par de vértices i, j ∈ V .

O conjunto de todos os automorfismos ϕ de um grafo G é denominado Aut(G),

isto é, tem-se

Aut(G) = {ϕ : V → V | ϕ é automorfismo de G}.

Todo grafo possui um automorfismo trivial, a permutação identidade. Se um grafo

3Uma permutação é uma bijeção de um conjunto nele mesmo.

7 2.4. Problemas computacionais

não possui nenhum automorfismo, exceto o trivial, ele é chamado de grafo rígido.

1 2 3 4 5

6

Figura 2.6: Um grafo rígido.

Um grafo G é não rígido se |Aut(G)| > 1, ou seja, se G não for rígido. Os grafos

das Figuras 2.1 e 2.5 são exemplos de grafos simétricos.

Um grafo G é vértice-transitivo se, dado qualquer par de vértices u, v, há um

automorfismo ϕ : V → V tal que ϕ(u) = v.

Um grafo G é aresta-transitivo se, dados quaisquer dois pares de vértices adja-

centes i1, j1 e i2, j2, há um automorfismo ϕ : V → V tal que ϕ(i1) = i2 e ϕ(j1) = j2.

Um grafo G é simétrico se é vértice-transitivo e aresta-transitivo.

O conjunto de todas as permutações de {1, 2, . . . , n} é denotado por Sn. O grafo

completo com n vértices é um exemplo de grafo para o qual Aut(G) = Sn.

Dado um grafo G = (V,E) e uma função injetora ϕ : V → V , denotamos por

ϕ(G) o grafo definido por

ϕ(G) = (V,ϕ(E))

onde ϕ(E) ={{ϕ(u), ϕ(v)} : {u, v} ∈ E(G)

}

.

2.4 Problemas computacionais

As definições4 que se seguem foram baseadas nas referências [18] e [33].

4Estas definições são baseadas em um modelo computacional de Turing


Um alfabeto é um conjunto finito cujos elementos são chamados de símbolos. Uma

palavra sobre um alfabeto Σ é uma sequência finita de símbolos de Σ. O comprimento

de uma palavra w é o número de elementos da sequência w e é denotado por |w|. O

conjunto de todas as palavras sobre Σ é denominado Σ∗. Uma linguagem sobre um

alfabeto Σ é um subconjunto de Σ∗.

Em computação, um tipo de problema muito estudado é o problema de decisão.

Problemas desse tipo admitem apenas as respostas sim ou não. Por exemplo, des-

cobrir se uma página na web contêm o texto “index of” é um problema de decisão;

descobrir se a conectividade de uma rede de computadores é tolerante à falha de k

máquinas nessa rede é outro problema de decisão.

Todo problema de decisão em computação corresponde ao problema de se decidir

se uma dada palavra w sobre um alfabeto Σ pertence ou não a uma linguagem L.

Neste trabalho, os termos linguagem e problema se referem ao mesmo conceito. Por

isso, quando se diz que um algoritmo A decide uma linguagem L, o que se quer dizer

é que o algoritmo A, ao receber uma palavra w como entrada, devolve corretamente

sim caso w ∈ L e não caso w 6∈ L.

2.4.1 Classes de problemas

Classificamos os problemas de decisão em classes de complexidade de acordo com

a quantidade de recursos5 necessários para resolvê-los. Embora existam diversas

classes de complexidade, este trabalho apenas faz referência às classes P e NP, que

serão definidas a seguir (conforme [18]).

Uma linguagem L pertence à classe P se existe um polinômio p(n) e um algoritmo

que decide L cujo tempo total de execução com entrada w (até uma resposta sim

ou não) não ultrapassa p(|w|).

Uma linguagem L está na classe NP se e somente se há uma linguagem A ∈ P5As definições apresentadas são aplicadas ao modelo computacional de Turing.

9 2.4. Problemas computacionais

e um polinômio p(n) tal que, para toda palavra x ∈ Σ∗, tem-se x ∈ L se e somente

se existe y ∈ Σ∗ com |y| ≤ p(|x|) tal que (x, y) ∈ A. A palavra y é chamada de um

certificado para x ∈ L.

Sejam A e B duas linguagens. Dizemos que A é Turing-redutível a B em tempo

polinomial (escreve-se A ≤pT B) se existe um algoritmo que decide A, que executa

em tempo polinomial, e que pode ter instruções condicionais na forma

se y ∈ B então . . . senão . . . fim.

onde considera-se (para o cômputo do consumo de tempo do algoritmo) que uma

consulta da forma y ∈ B leva tempo constante.

2.4.2 NP-Completo

Uma linguagem L é NP-Completo se L ∈ NP e toda linguagem em NP é Turing-

redutível a L. Esta classe é de suma importância para o entendimento do problema

P versus NP, pois haverá um algoritmo em tempo polinomial para um problema NP-

Completo se e somente se todo problema em NP possuir um algoritmo em tempo

polinomial que o resolva. Em outras palavras, se houver um algoritmo polinomial

para um problema NP-Completo, então P = NP. Como há evidências que P e NP

são diferentes, a prova de que um problema é NP-Completo é considerada uma forte

evidência desta intratabilidade.

CAPÍTULO 3


Neste capítulo, apresentamos dois problemas computacionais: o Problema do Iso-

morfismo de Grafos e o Problema do Automorfismo de Grafos. Daremos também

algumas aplicações do Problema do Isomorfismo em situações práticas.

3.1 Problema do Isomorfismo de Grafos

Definimos a versão de decisão para o Problema do Isomorfismo de Grafos (PIG)

do seguinte modo: dado um par de grafos {G,H}, decidir se esse par pertence ao

conjunto

I ={{G,H} | G é isomorfo a H

}

.

Um algoritmo para a versão de decisão do PIG retorna sim se os grafos da entrada

forem isomorfos e não caso contrário.

O melhor algoritmo conhecido para o PIG é o proposto por Babai e Luks em [4],

Capítulo 3. Isomorfismo de Grafos 12

que possui tempo de execução 2O(√

n log n), onde n é o número de vértices. Foggia [10]

comparou os algoritmos propostos por Ullmann [36], Cordella[11], McKay [25] e

Schimidt [32], e concluiu que o algoritmo implementado no programa Nauty (e

elaborado por B. McKay [25]) é o mais rápido na prática. Em [35], Torán demonstrou

que o PIG é pelo menos tão difícil quanto o problema de se computar o determinante

de uma matriz com entradas inteiras.

Existem algoritmos que decidem casos especiais do PIG em tempo polinomial.

Tais algoritmos existem para: árvores [18], grafos planares [15], grafos de intervalo

[20], grafos de permutação [7], grafos de genus limitado [26], grafos de grau limitado

[21], e grafos cujos autovalores possuem multiplicidade limitada [3]. No entanto, não

se conhece nenhum algoritmo eficiente para o caso geral e portanto não se sabe se

o PIG está na classe P ou se é NP-Completo [16], embora suspeita-se que ele esteja

estritamente entre as duas classes [2]. Por outro lado, dados dois grafos G e H e um

mapa ϕ entre seus conjuntos de vértices, há um algoritmo polinomial que decide se

ϕ é um isomorfismo entre os grafos dados.

Algoritmo 1: Um verificador para o PIGEntrada: Grafos G e H com mesmo número de vértices, e função injetora

ϕ : V (G)→ V (H)Saída: sim se ϕ(G) = H e não caso contrárioinício

para todo u ∈ V faça

para todo v ∈ V faça

se {u, v} ∈ E(G) e {ϕ(u), ϕ(v)} /∈ E(H) então

retorna não

fim se

se {u, v} /∈ E(G) e {ϕ(u), ϕ(v)} ∈ E(H) então

retorna não

fim se

fim para todo

fim para todo

retorna sim

fim

13 3.2. Problema do Automorfismo de Grafos

Conforme a definição de certificado, (vide seção 2.4.1), sabemos que o PIG per-

tence à classe NP. Para demonstrar tal afirmação, considere a linguagem

A ={

({G,H}, ϕ) : G,H são grafos e ϕ ∈ Iso(G,H)}

Note que {G,H} ∈ PIG ⇔ ({G,H}, ϕ) ∈ A. Ademais, A ∈ P pois o Algo-

ritmo 1 decide A e é claramente polinomial. Note também que qualquer mapea-

mento ϕ : V (G) → V (H) pode ser representado usando tamanho O(n). Com isso,

podemos concluir que PIG ∈ NP.

3.2 Problema do Automorfismo de Grafos

Seja G um grafo. Decidir se o grupo de automorfismos de G possui algum auto-

morfismo diferente do trivial é um problema de decisão chamado Problema do Au-

tomorfismo de Grafos (PAG), e consiste em determinar se G pertence ao conjunto

A = {G : |Aut(G)| > 1}.

Assim como o PIG, o Problema do Automorfismo de Grafos também pertence à

classe NP [18].

3.3 Relação entre os problemas

Podemos mostrar que o PAG é Turing-redutível ao PIG. Antes de mostrarmos a

redução, precisamos da seguinte definição: G[i] é o grafo obtido de G ligando ao

vértice i um caminho com |V (G)| + 1 novos vértices. O propósito desta construção

é que todo automorfismo deste grafo modificado mapeia o vértice i em si mesmo, e

além disso, não ocorre no grafo modificado nenhum automorfismo que não estivesse


presente no grafo original (isto é, Aut(G[i]) ⊆ Aut(G)).

A ideia central da Turing-redução apresentada no Algoritmo 2 é a seguinte: se os

grafos G e H são isomorfos, e existe um isomorfismo ϕ de G em H tal que v = ϕ(u),

então os grafos G[u] e H[v] também são isomorfos. O Algoritmo 2 computa o PAG

em tempo polinomial fazendo consultas de decisão ao PIG como descrito a seguir.

Algoritmo 2: Algoritmo para o PAG usando consultas ao PIGEntrada: Grafo G com conjunto de vértices {1, 2, . . . , n}Saída: sim se |Aut(G)| > 1 e não se G é rígidoinício

para i← 1 até n− 1 faça

para j ← i+ 1 até n faça

se {G[i], G[j]} ∈ PIG entãoretorna sim

fim se

fim para

fim para

retorna não

fim

Retomando a demonstração da corretude da Turing-redução, o grafo G possui

um automorfismo não trivial se, e somente se, G tem um automorfismo que mapeia

i em j para algum par de vértices i 6= j. Pela observação no parágrafo que precede o

Algoritmo 2, um automorfismo que mapeia i em j existe se, e somente se, os grafos

G[i] e G[j] são isomorfos. Como o algoritmo testa todas as possíveis combinações

de diferentes vértices i e j, ele consegue determinar, em tempo O(n2) se o grafo

de entrada é rígido ou não. Portanto PAG ≤pT PIG. Atualmente não se conhece

nenhuma Turing-redução do PIG ao PAG [18].

3.4 Problema do Isomorfismo de Subgrafos

Dados dois grafos G e H, o Problema do Isomorfismo de Subgrafos consiste em

decidir se H é isomorfo a algum subgrafo de G, ou seja, se H pode ser transformado

15 3.5. Aplicações práticas

em um subgrafo de G apenas renomeando-se seus vértices. Este problema é uma

generalização do PIG e pertence à classe dos problemas NP-Completos, que são os

problemas mais difíceis da classe NP [37].

3.5 Aplicações práticas

Nesta seção, destacaremos algumas aplicações práticas onde o problema de isomor-

fismo de grafos é utilizado.

3.5.1 Impressões digitais

Nandi [27] utiliza o PIG para confrontar imagens de impressões digitais, que são

representadas por grafos gerados pelas características presentes em cada imagem.

Cada uma dessas características representa um vértice no grafo, e as arestas re-

presentam as relações que estas características possuem entre si. Para verificar se

uma impressão digital corresponde a outra, resolve-se uma instância do Problema

do Isomorfismo dos Grafos. Para essa aplicação, seria desejada a existência de um

algoritmo polinomial para o PIG ou que as instâncias geradas a partir das imagens

de impressões digitais fossem grafos de uma das classes onde o PIG é solúvel em

tempo polinomial (como aquelas listadas na Seção 3.1).

3.5.2 Zero knowledge proof

Sistemas de zero knowledge proof 1 tem aplicações em criptografia e protocolos de

segurança que requerem autenticação. Uma dessas aplicações, que se baseia na

dificuldade de se resolver o PIG, é descrita a seguir.

Um agente P conhece um circuito Hamiltoniano C em um grafo G, e um ou-

tro agente, chamado Q, conhece o grafo G mas não o circuito Hamiltoniano. O

1Adaptado de [18] e [13]


agente Q está disposto a pagar uma grande quantia em dinheiro pelo circuito Ha-

miltoniano2 C, porém, antes de fazer o pagamento, ele precisa se certificar de que

P realmente conhece o circuito Hamiltoniano que diz conhecer. O agente P, por sua

vez, precisa provar a Q que conhece o circuito C sem revelá-lo, pois se o revelar a

Q, este poderá ser desonesto e não fazer o pagamento, uma vez que já adquiriu o

objeto de seu desejo.

Os dois começam, então, um jogo no qual, em cada rodada, P escolhe uma per-

mutação qualquer ϕ : V (G) → V (G) e cria um grafo H = ϕ(G) (que é claramanete

isomorfo a G) e o envia a Q. Note que, se P conhece um circuito Hamiltoniano C

em G, então ele também conhece um em H, a saber, o circuito ϕ(C). Em seguida,

Q solicita a P que revele exatamente uma dentre duas coisas: ou o isomorfismo ϕ

entre G e H, ou um circuito Hamiltoniano em H. Se Q solicitou um isomorfismo,

então P mostra o mapeamento ϕ e Q verifica que, de fato, este mapeamento é um

isomorfismo de G em H. Se Q solicitou o circuito, P mostra o circuito ϕ(C) em H.

As respostas de P não revelam o ciclo Hamiltoniano original em G (a menos

que Q seja tão poderoso computacionalmente que consiga resolver o PIG). A cada

rodada, Q saberá apenas o isomorfismo de H em G ou um circuito Hamiltoniano

em H, mas nunca ambos numa mesma rodada. Ele precisaria de ambas as respostas

na mesma rodada a fim de descobrir o circuito em G; assim, a informação permanece

protegida.

Para ser capaz de responder às duas perguntas corretamente, P deve conhecer

um isomorfismo entre G e H e também um circuito Hamiltoniano em H (e portanto

também em G). Suponhamos agora que P não conheça um circuito Hamiltoniano

e esteja tentando enganar Q para ficar com o dinheiro. A cada rodada, P não sabe

qual pergunta lhe será feita até enviar H para Q. O agente P pode tentar adivinhar

qual pergunta Q irá fazer e gerar o grafo H de acordo. Se P acha que Q irá lhe

2Um circuito é Hamiltoniano quando vértice é visitado apenas uma vez.

17 3.5. Aplicações práticas

perguntar um isomorfismo ele pode gerar um grafo H isomorfo a G. Nesse caso,

suas más intenções seriam descobertas caso Q lhe fizesse a outra pergunta pois ele

não conhece um circuito Hamiltoniano em G (e portanto também não o conhece

em H). Se P acha que Q irá lhe perguntar por um circuito Hamiltoniano ele pode

tentar gerar um grafo H que tenha um tal circuito, mas seria desmascarado caso Q

lhe pedisse por um isomorfismo.

Com isso, se Q escolhe a pergunta aleatoriamente com probabilidade 1/2, a

chance de P enganar Q é de 2−n, onde n é o número de rodadas. Portanto, após um

número razoável de rodadas, Q se convence, com um alto grau de confiabilidade, de

que P de fato conhece um circuito Hamiltoniano em G.

Observa-se que, enquanto a primeira aplicação seria beneficiada caso PIG ∈

P , a segunda perderia completamente seu sentido, pois baseia-se na dificuldade

computacional de se decidir a linguagem PIG.

3.5.3 Aplicações em química

Para se determinar se uma molécula possui uma estrutura similar a uma outra, é

necessário fazer uma comparação desta molécula com um banco de dados de molé-

culas existentes. Cada molécula é representada por um grafo, onde os vértices são os

átomos e as arestas correspondem às ligações atômicas. O processo de comparação

consiste em verificar se as estruturas moleculares são idênticas, ou seja, se os grafos

que representam duas moléculas são isomorfos [30].

3.5.4 Outras aplicações

O autor Conte [8] utiliza o PIG para o reconhecimento de padrões. Já Farouk [9]

trabalha com o reconhecimento de imagens e Pedarsani [29], em seu artigo, trata da

segurança de informação em redes sociais, todos utilizam o PIG para a resolução de

seus problemas.


3.6 Revisão bibliográfica

Para a realização desta pesquisa foram consultados diversos trabalhos, entre artigos

e dissertações. O primeiro a ser destacado é o artigo escrito por McKay [25], onde o

autor apresenta um algoritmo para o PIG. Este algoritmo determina uma represen-

tação canônica dos grafos utilizando um particionamento ordenado de seus vértices.

Todos os vértices de uma partição possuem uma mesma rotulação, distinguindo-os

dos demais vértices do grafo. Este particionamento é calculado aplicando-se um con-

junto de invariantes de vértices a uma primeira partição, que, inicialmente, agrupa

todos os vértices do grafo. Ao final do processo, dois grafos são isomorfos se, e

somente se, possuem a mesma representação. No Capítulo 6 descreveremos com

maiores detalhes o algoritmo proposto por McKay.

Para obter o referencial teórico do Problema do Isomorfismo de Grafos, foi es-

tudado o livro de Köbler, Schöning e Torán [18]. Este livro traz as definições do

PIG e do PAG, apresenta quais problemas computacionais são redutíveis ao PIG,

e apresenta uma abordagem muito detalhada do PIG do ponto de vista de sua

complexidade.

CAPÍTULO 4

Emparelhamentos em grafos bipartidos

O algoritmo que será proposto no Capítulo 5 utiliza emparelhamentos em um grafo

bipartido para a verificação do isomorfismo entre dois grafos G e H. Portanto, neste

capítulo vamos apresentar o conceito de emparelhamento, e também um método

eficiente para enumerar todos os emparelhamentos perfeitos de um grafo bipartido.

4.1 Definições

Um grafo G é chamado bipartido se seu conjunto de vértices V pode ser dividido em

dois conjuntos disjuntos V1 e V2, onde toda aresta de G é da forma {u, v} com u ∈

V1, v ∈ V2.

Dado um grafo G, um emparelhamento M em G é um conjunto de arestas disjun-

tas duas a duas. Um vértice é dito saturado (ou coberto) por M quando é incidente

a uma aresta do emparelhamento. Um emparelhamento M é dito: perfeito quando

todos os vértices estão saturados; maximal quando não há nenhum emparelhamento

Capítulo 4. Emparelhamentos em grafos bipartidos 20

M ′ que contenha propriamente M ; e máximo se não existe um emparelhamento

com maior número de arestas que M . Observe que todo emparelhamento perfeito é

máximo.

Um caminho em um grafo é chamado de caminho alternante em relação a um

emparelhamento M (ou M -alternante) se, para quaisquer duas arestas consecutivas

desse caminho, uma está em M e a outra não. Um caminho alternante é dito

caminho aumentante em relação a M (ou M -aumentante) quando o primeiro e o

último vértice não estão saturados por M .

Um grafo dirigido (ou digrafo) ~G é um par ordenado (V,A) onde V é um conjunto

finito de vértices e A é um conjunto de pares ordenados de V chamados arcos. Seja

a = (u, v) um arco de ~G, dizemos que u é o vértice de partida e v o vértice de chegada

de a. Dizemos ainda que o arco a é orientado de u para v. A vizinhança de saída

de um vértice u é o conjunto N+(u) = {v ∈ V ( ~G) : (u, v) ∈ A( ~G)}.

Dados um grafo bipartido G = (V1 ∪ V2, E) e um emparelhamento M de G,

definimos o digrafo associado como sendo o digrafo ~D = ~D(G,M), onde V (~D) =

V (G) e A(~D) é o conjunto de arcos que é obtido orientando-se as arestas de M de

V1 para V2 e as arestas de E \M no sentido oposto. A Figura 4.1 nos mostra um

exemplo de um grafo bipartido G, de um emparelhamento perfeito M em G e do

digrafo associado ~D(G,M).

4.2 Encontrando um emparelhamento máximo

Nesta seção, apresentamos um algoritmo para encontrar um emparelhamento má-

ximo em um grafo bipartido. Porém, antes de apresentarmos tal algoritmo, vamos

enunciar o Teorema de Berge1, que será importante para seu entendimento.

Teorema 1. Um emparelhamento M de um grafo G é máximo se e somente se não

1Adaptado de [17] e [31]

21 4.2. Encontrando um emparelhamento máximo

0 1 2 3

4 5 6 7

0 1 2 3

0 1 2 3

4 5 6 7

4 5 6 7

G

M

~D(G,M)

Figura 4.1: Grafo dirigido por um emparelhamento perfeito.

existe um caminho M -aumentante em G.

Demonstração. Se existe um caminho M -aumentante P , podemos criar um empa-

relhamento maior eliminando as arestas de M que pertencem a P e incluindo as

arestas de P que originalmente não pertençam a M . Note que esta permuta de

arestas corresponde a tomar o emparelhamento2 M∆P . Para provar a recíproca,

suponhamos que M não é máximo. Portanto, existe um outro emparelhamento M ′

com mais arestas que M . Considere o grafo H definido por H = (V (G),M∆M ′).

Cada vértice v ∈ V (H) tem grau 0, 1 ou 2 porque v pode ser incidente em, no

máximo, uma aresta de M e uma de M ′. As componentes conexas de H podem

2O símbolo ∆ denota a operação de diferença simétrica entre dois conjuntos.


então ser: ou vértices isolados, ou circuitos de ordem par3 com arestas alternadas

de M e de M ′, ou ainda caminhos com arestas alternadas de M e de M ′. Como

|M ′| > |M |, o grafo H tem mais arestas de M ′ que de M e, portanto, pelo menos

uma das componentes de H é um caminho que começa e termina com arestas de M ′

(e que não pertencem a M); esse caminho é um caminho M -aumentante no grafo

G. Isso encerra a prova do teorema.

Com base no conceito de caminho M -aumentante e no Teorema 1, podemos de-

senvolver um algoritmo que encontra um emparelhamento máximo (Algoritmo 3).

A ideia do algoritmo é encontrar caminhos M -aumentantes e fazer a permuta das

arestas de M com as arestas dos caminhos encontrados. A busca por caminhos

aumentantes e a permuta de arestas são realizadas sucessivamente até que o em-

parelhamento corrente seja máximo4. Vamos usar S para denotar o conjunto de

vértices saturados.

O algoritmo tem como entrada um grafo G e um emparelhamento inicial M , que

pode ser vazio. Note que, caso M = ∅, todas os arcos de ~D(G,M) serão orientados

em um único sentido. Quanto maior for o emparelhamento inicial M , mais rápido o

algoritmo encontra um emparelhamento máximo.

Em seguida, para todo vértice a ∈ V1 não saturado, é realizada uma busca em

profundidade, e é obtido um caminho dirigido P entre a e um vértice não saturado

b ∈ V2. O vértice a é não saturado pela própria escolha de a (na linha 8 do Al-

goritmo 3) e b é não saturado pois é o vértice devolvido pelo algoritmo de busca

em profundidade (Algoritmo 4), que possui justamente como critério de parada en-

contrar um vértice não saturado em V2 (veja linha 2). Note que P é um caminho

M -aumentante, pois começa em a e termina em b[a], que são ambos não saturados.

3Circuitos que possuem um número par de arestas.4Este algoritmo é uma adaptação do algoritmo de Hopcroft-Karp, disponível em [14]

23 4.2. Encontrando um emparelhamento máximo

Algoritmo 3: Encontrar emparelhamento máximo de um grafo GEntrada: Grafo bipartido G = (V1 ∪ V2, E), emparelhamento M

1 início

2 S ← {v ∈ V1 ∪ V2 : v incide em alguma aresta de M}3

~D ← ~D(G,M)4 repita

5 para todo v ∈ ~D(G) faça

6 pai[v]← NULL7 fim para todo

8 para todo a ∈ V1 \ S faça

9 pai[a] = a10 b[a]← Busca(a)11 fim para todo

12 para todo a ∈ V1 \ S faça

13 se b[a] 6= NULL então

14 Inverte(b[a])15 S ← S ∪ {a, b[a]}16 fim se

17 fim para todo

18 até até que a cardinalidade de S não aumente;19 fim

Uma vez encontrado o caminho M -aumentante P de a até b, o emparelha-

mento M é substituido por M∆P . Essa atualização do emparelhamento é feita de

modo implícito, invertendo-se a orientação dos arcos no caminho P (através de uma

chamada ao Algoritmo 5). Desse modo o novo grafo ~D é, na realidade, ~D(G,M∆P ).

O laço entre as linhas 4 e 18 do Algoritmo 3 é executado até que não seja mais

possível saturar nenhum novo vértice, ou seja, até que nenhum outro caminho M -

aumentante possa ser encontrado. Quando isto ocorre, pelo Teorema 1, temos que

M é máximo.


Algoritmo 4: BuscaEntrada: vértice uSaída: vértice b ou NULL

1 início

2 se u ∈ V2 e N+(u) = ∅ então

3 retorna u4 fim se

5 para todo v ∈ N+(u) faça

6 se pai[v] = NULL então

7 pai[v]← u8 b← Busca(v)9 se b 6= NULL então

10 retorna b11 fim se

12 fim se

13 fim para todo

14 retorna NULL

15 fim

4.3 Enumerando os emparelhamentos perfeitos

Nesta seção apresentamos um algoritmo que enumera os emparelhamentos perfeitos

em um grafo bipartido G, baseado no algoritmo proposto por Uno [38]. Seja G

um grafo bipartido, M um emparelhamento perfeito de G e ~D = ~D(G,M) o grafo

dirigido associado. Podemos obter um novo emparelhamento de G permutando

arestas de M com arestas presentes em um circuito ou em caminhos M -alternantes

de ~D. Em outras palavras, o grafo gerado pela diferença simétrica de M com um

emparelhamento diferente é composta por circuitos, caminhos alternantes ou vértices

isolados.

Como em um emparelhamento perfeito todos os vértices estão saturados, o grafo

gerado pela diferença simétrica entre dois emparelhamentos perfeitos é composta

apenas por circuitos alternantes e vértices isolados. Portanto, um grafo G possuirá

emparelhamentos perfeitos diferentes de M somente se o digrafo ~D(G,M) possuir

circuitos alternantes. Portanto, a ideia central do Algoritmo 9 é encontrar um cir-

25 4.3. Enumerando os emparelhamentos perfeitos

Algoritmo 5: InverteEntrada: vértice b

1 início

2 x← b3 enquanto pai[x] 6= x faça

4 Remover arco (pai[x], x) de ~D

5 Inserir arco (x, pai[x]) em ~D6 x← pai[x]7 fim enquanto

8 fim

cuito dirigido ~C no digrafo ~D(G,M) e permutar suas arestas com as arestas empa-

relhamento perfeito M . Essa permuta irá gerar um novo emparelhamento perfeito

M ′ = M∆ ~C. Um modo de se encontrar um circuito dirigido em ~D seria fazer uma

busca em profundidade no grafo ~D, buscando uma aresta de retorno [19]. Uma outra

maneira é decompor ~D em componentes fortemente conexas (este assunto será abor-

dado na próxima seção). Este método é mais eficiente em relação ao primeiro pois

é possível encontrar todos os circuitos com apenas duas buscas em profundidade.

4.3.1 Componentes fortemente conexas

Uma componente fortemente conexa de um digrafo ~G = (V,A) é um subconjunto

maximal de vértices S ⊆ V ( ~G) tal que, para todo par de vértices u e v em S, há um

caminho de u a v e vice-versa. O grafo transposto de ~G é o grafo ~GT = (V,AT ) onde

AT ={

(u, v) : (v, u) ∈ A(G))}

. A Figura 4.2 apresenta as componentes fortemente

conexas de um digrafo ~D.

Os conceitos de circuito dirigido e componentes fortemente conexas estão associa-

dos, visto que um arco está em um circuito dirigido se e somente se suas extremidades

estão em uma mesma componente fortemente conexa. De fato, sejam u e v vértices

e F uma componente fortemente conexa de um digrafo ~G. Como u, v ∈ F , haverá

um caminho P de u até v e um caminho P ′ de v até u. Com isso, é fácil verificar


que P ∪ P ′ contém um circuito. Portanto, um modo de se encontrar um circuito

~C no grafo ~D(G,M) é executar um algoritmo que particiona os vértices de ~D em

componentes fortemente conexas e, em seguida, verificar quais arcos pertencem a

uma mesma componente fortemente conexa.

Suponha que um arco e não pertença a nenhum circuito. Podemos excluir o

arco e do digrafo ~D pois ele será irrelevante para encontrarmos um emparelhamento

perfeito M ′. Neste ponto, suponha que o arco e tenha sido removido de ~D. Vamos

analisar os dois casos possíveis para o arco e: em primeiro lugar, se e ∈ M , então

e estará presente também em M ′ = M∆C. No segundo caso, se e /∈ M , então

e /∈M ′ = M∆C. Em ambos os casos, a presença de e em ~D não teve relevância para

encontrarmos um novo emparelhamento perfeito M ′. Portanto, podemos excluir e

de ~D sem nenhum prejuízo ao emparelhamento M ′.

0 1 2 3

4 5 6 7

~D

Figura 4.2: Componentes fortemente conexas em um digrafo ~D.

Como não estamos apenas interessados em encontrar um circuito em ~D, mas

também em eliminar do grafo ~D todos os arcos que não pertencem a circuitos, é

importante encontrar todos os circuitos de ~D. Para tanto, optamos por utilizar um

algoritmo (com custo de tempo linear, ou seja, O(|V | + |E|)) que particione ~D em

componentes fortemente conexas. Na próxima seção vamos apresentar um algoritmo

que faça essa decomposição e na Seção 4.3.2 vamos explicar como remover de ~D os


arcos que não estão em circuitos usando componentes fortemente conexas.

Algoritmo para decomposição em componentes fortemente conexas

O Algoritmo 6 decompõe um digrafo em suas componentes fortemente conexas5, e

depende dos Algoritmos 7 e 8, que executam uma busca em profundidade a partir

de um conjunto ordenado de vértices.

Algoritmo 6: ComponentesFortementeConexas

Entrada: Digrafo ~GSaída: Vetor C2

1 início

2 F0 ← ordem qualquer dos vértices de V ( ~G)3 (F1, C1)← DFS(~G,F0)4 (F2, C2)← DFS(~GT , F1)5 retorna C2

6 fim

Nos Algoritmos 7 e 8 temos um vetor chamado pai, que é utilizado para guardar

as árvores de uma floresta de busca em profundidade. Para todo nó v em uma árvore

de busca, o nó pai de v estará armazenado em pai[v]. Definimos também que os

vértices ainda não explorados pela busca em profundidade recebem o valor NULL

como pai e um vértice raiz de uma árvore de busca terá a si mesmo como pai.

Temos também nos Algoritmos 7 e 8 um estrutura do tipo fila, denominada F ,

que armazena os vértices na ordem em que eles foram explorados na busca em pro-

fundidade. Note que, na linha 10 do Algoritmo 7 e nas linhas 7 e 10 do Algoritmo 8

temos uma operação de concatenação (representada pelo símbolo ·) entre um vértice

e uma lista de vértices ou entre duas listas de vértices. Observe que ao percorrer-

mos a fila F do fim para o início, temos os vértices de ~G ordenados pelo momento5Adaptado de [19]


Algoritmo 7: DFS

Entrada: Digrafo ~G, lista de vértices LSaída: Vetor C e Fila F

1 início

2 F ← ∅3 C ← novo vetor com |V ( ~G)| elementos4 para todo u ∈ V ( ~G) faça

5 pai[u]← NULL6 fim para todo

7 k ← 08 para todo u ∈ L faça

9 se pai[u] = NULL então

10 pai[u]← u11 F ← DFSVISIT(u,C) · F12 k ← k + 113 fim se

14 fim para todo

15 retorna F,C

16 fim

em que foram explorados pelo algoritmo de busca em profundidade (vértices mais a

esquerda tiveram sua exploração finalizada por último).

Na linha 11 do Algoritmo 7, k é um contador de componentes da floresta de

busca do digrafo ~G. Ao se encerrar a exploração de uma árvore na floresta de busca

em profundidade, o contador k é incrementado (observe que cada árvore na floresta

da busca inicializada na linha 4 do Algoritmo 6 está associada a uma componente

fortemente conexa) e, ao se iniciar a exploração em uma nova árvore enraizada por

u, o Algoritmo 8 armazena no vetor C a componente fortemente conexa na qual u

e seus descendentes v pertencem (veja linha 3).

Sejam n o número de vértices e m o número de arcos do digrafo ~G. Como todo

vértice u deve ser explorado pela busca em profundidade, temos n chamadas ao

Algoritmo 8 (muitas delas recursivas). Em cada chamada, todo vértice v ∈ N+(u)

será testado. No total, o número de testes realizados será igual ao número de arcos.


Algoritmo 8: DFSVISITEntrada: vértice u, vetor CSaída: Vértice u concatenado com a Fila F

1 início

2 F ← ∅3 C[u]← k4 para todo v ∈ N+(u) faça

5 se pai[v] = NULL então

6 pai[v]← u7 F ← DFSVISIT(v,C) · F8 fim se

9 fim para todo

10 retorna u · F11 fim

O tempo total gasto para as chamadas ao Algoritmo 8 é O(m). Devemos acrescentar

também o tempo gasto para inicialização do vetor pai (linhas 3 a 5 do Algoritmo

7) e o tempo gasto para se verificar se o vértice s já foi explorado pela busca em

profundidade (linha 8 do Algoritmo 7). Ao todo, isso leva tempo O(n). Portanto, o

tempo de execução6 do Algoritmo 7 é O(n+m).

4.3.2 Gerando novos emparelhamentos

Note que, após a decomposição, as componentes fortemente conexas de ~D serão ou

vértices isolados ou circuitos. Portanto, os arcos de ~D ou estarão em um circuito

ou terão seus vértices de partida e chegada localizados em componentes fortemente

conexas diferentes. O Algoritmo 11 se utiliza desta propriedade para eliminar todos

os arcos que não pertencem a nenhum circuito pois, como veremos mais adiante,

apenas arcos que estejam em um circuito são utilizados para se encontrar novos

emparelhamentos (linha 8 do Algoritmo 9 e linhas 10 e 13 do Algoritmo 10.

Em uma descrição informal, o Algoritmo 9 recebe inicialmente um emparelha-

mento perfeito M (obtido pelo Algoritmo 3) e o digrafo ~D = ~D(G,M) e escolhe um

6Para mais explicações e verificação da corretude do algoritmo, consulte [19]


arco arbitrário e = (u, v) de ~D, que também pertença a M . No próximo passo, é

encontrado um circuito ~C, contendo e, e é construído um emparelhamento perfeito

M ′ = M∆C. Depois, o algoritmo gera dois novos digrafos: o primeiro é obtido

excluindo-se os vértices u e v e os arcos que incidem neles; o segundo é obtido

excluindo-se o arco e. Em ambos os digrafos obtidos, os arcos que não pertencem

a um circuito são excluídos do digrafo. Por fim, o algoritmo realiza uma chamada

recursiva para cada grafo gerado. Veremos com maiores detalhes o funcionamento

do algoritmo após enunciá-lo.

Com base nas definições acima, e no algoritmo de decomposição em componentes

fortemente conexas, podemos então mostrar o Algoritmo 9, que enumera todos os

emparelhamentos perfeitos em um grafo bipartido.

Algoritmo 9: Enumerar Emparelhamentos PerfeitosEntrada: Grafo bipartido G

1 início

2 Encontrar um emparelhamento perfeito M de G pelo Algoritmo 33 se M não existe então

4 Fim

5 fim se

6 Imprimir M7

~D ← ~D(G,M)8 EliminarArestasDesnecessarias ( ~D)9 EnumEmpPerfeitosRecursivo (~D,M).

10 fim

Primeiramente o Algoritmo 9 verifica se há um emparelhamento perfeito no grafo

dado utilizando o Algoritmo 3. Caso exista, inicia-se o processo de listar todos os

emparelhamentos perfeitos, procurando um circuito C, M -alternante, e gerando um

novo emparelhamento perfeito M ′ = M∆C. O próximo passo é escolher um arco e

que esteja tanto em M quanto no circuito C. Observe que e está em M mas não


Algoritmo 10: EnumEmpPerfeitosRecursivo

Entrada: ~D,M1 início

2 se ~D = ∅ então

3 Fim

4 fim se

5 Encontrar um circuito M -alternante C6 Escolher uma aresta arbitrária e ∈ C ∩M7 M ′ ← C∆M8 Imprimir M ′

9 Gerar grafo ~D(+e)

10 EliminarArestasDesnecessarias(D(+e))

11 EnumEmpPerfeitosRecursivo (D(+e),M)

12 Gerar grafo D(−e)

13 EliminarArestasDesnecessarias(D(−e))

14 EnumEmpPerfeitosRecursivo (D(−e),M ′)

15 fim

em M ′. No próximo passo, o algoritmo gera dois subproblemas de mesma natureza:

enumerar todos os emparelhamentos perfeitos que possuem e, e todos os empare-

lhamentos perfeitos que não possuem o arco e. Vamos analisar primeiramente o

segundo caso: para enumerar os emparelhamentos perfeitos que não contém e, con-

sideramos o digrafo ~D(−e) que é obtido removendo-se o arco e de ~D, e em seguida o

Algoritmo 10 chama-se a si mesmo, passando como parâmetro o digrafo D(−e) e o em-

parelhamento perfeito M ′. Já no primeiro caso, para enumerar os emparelhamentos

perfeitos que possuem e, consideramos o grafo D(+e) que é obtido removendo-se de ~D

as extremidades de e, e todos os arcos que partem ou chegam nelas. Note que todo

emparelhamento perfeito de D(+e) corresponde a um único emparelhamento perfeito

de ~D que contém e. Portanto, para se enumerar os emparelhamentos perfeitos que

contém e, o Algoritmo 10 executa uma chamada recursiva, tendo como parâmetros

D(+e) e M . Note que um emparelhamento perfeito de D(

+e) não conterá o arco e,


Algoritmo 11: EliminarArestasDesnecessarias

Entrada: ~D1 início

2 cfc← ComponentesFortementeConexas ( ~D) para todo (u, v) ∈ A( ~D)faça

3 se cfc(u) 6= cfc(v) então

4 A(~D)← A(~D) \ (u, v)5 fim se

6 fim para todo

7 fim

porém e estará presente em M (que foi passado como parâmetro na chamada recur-

siva). Portanto, todo emparelhamento perfeito obtido pela diferença simétrica de

M com um circuito dirigido de D(+e) é um emparelhamento perfeito do grafo G que

contém e.

4.3.3 Análise de complexidade

Nesta seção, vamos analisar a complexidade de tempo para enumerar todos os em-

parelhamentos perfeitos de um grafo bipartido.

Primeiramente, vamos analisar a complexidade do Algoritmo 3, que encontra

um emparelhamento máximo em um grafo bipartido G = (V1 ∪ V2, E). Sejam n =

|V1 ∪ V2| e m = E. Cada execução das linhas 8 a 11 corresponde a um busca em

profundidade no grafo, o que leva tempo O(n + m). Para se inicializar o vetor

pai, gasta-se tempo O(n). Já o Algoritmo 5, no pior caso, levará tempo O(n),

pois um caminho terá, no máximo, n vértices. Temos, no máximo, |V2| chamadas

ao Algoritmo 5, pois no pior caso todos os caminhos a serem invertidos possuirão

apenas uma aresta {a ∈ V1 \ S, b ∈ V2 \ S}. Cada iteração no laço das linhas 4

a 17 levará, no pior caso, tempo O(n2 + n + |V2|) (um grafo bipartido terá, no

máximo, n2 arestas). Teremos, no máximo, n/2 iterações no laço das linhas 4 a 17,

pois inicialmente S pode ser vazio, e no pior caso, apenas 2 vértices são inseridos


em S a cada iteração (linha 15). Portanto, o Algoritmo 3 demandará um tempo

O(n/2(n2 + n+ |V2|)) = O(n3).

No Algoritmo 10, as operações de eliminar arestas desnecessárias e gerar os digra-

fos D(+e) e D(

−e) levam tempo O(n). Portanto, o tempo de execução do Algoritmo 10

é proporcional a O(n3 + nk), onde k é o número de emparelhamentos perfeitos. Há

um algoritmo mais rápido, que demanda tempo O = (√n(n + m)) [14], porém não

utilizamos devido a complexidade de implementação e também porque ele não me-

lhoraria muito a velocidade de execução na prática do algoritmo para o Problema

do Isomorfismo de Grafos proposto nesta dissertação.

CAPÍTULO 5

Algoritmo para o Problema do Isomorfismo de Grafos

Neste capítulo será apresentado o algoritmo que desenvolvemos para o Problema

do Isomorfismo de Grafos, baseado em um processo de simulação sobre os vértices

de um grafo G. O objetivo destas simulações é encontrar partições do conjunto de

vértices de G, que servirão de base para decidir se dois grafos G e H são isomorfos.

O algoritmo é dividido em três partes principais: a primeira consiste em executar

p-simulações em G e H, aplicando-se uma função f sobre seus respectivos conjuntos

de vértices. Ao final desta etapa, os vértices estarão agrupados em classes, e os

vértices de uma determinada classe compartilham as mesmas propriedades entre si

(grau, padrão de vizinhança).

Na segunda etapa, construímos um grafo bipartido R = (V (G)∪V (H), E), onde

o conjunto de arestas representa a compatibilidade entre os vértices de G e H. Esse

grafo R é construído de acordo com o particionamento de V (G) e V (H) obtidos na

etapa anterior.

Capítulo 5. Algoritmo para o Problema do Isomorfismo de Grafos 36

A terceira etapa consiste em encontrar emparelhamentos perfeitos deR e verificar

se um emparelhamento perfeito M corresponde a um isomorfismo ϕ(V (G))→ V (H).

5.1 Simulação

Como definimos na Seção 2.1.2, o conjunto NG(v) é também chamado de vizinhança

aberta de um vértice v no grafo G. Agora vamos definir NG[v] = NG(v) ∪ {v} como

a vizinhança fechada1de v em G.

Um multiconjunto é definido como um par (X,m), onde X é um conjunto qual-

quer e m : X → N∗ uma função que associa cada elemento deX a um inteiro positivo.

Denotamos por M a família de todos os multiconjuntos finitos de N.

Fixamos um grafo G = (V,E), uma função f :M→ N e um inteiro positivo k.

Para um vértice p ∈ V , que será denominado pivô, uma p-simulação é uma sequência

de vetores x(1), x(2), . . . , x(k) com entradas em N indexados por V que são definidos

indutivamente pela seguinte relação. Para i = 1, atribua x(1)v = 1 se v = p ou

x(1)v = 0 se v 6= p. Para i > 1, defina

x(i)v = f

({x(i−1)w : w ∈ NG[v]}).

Por conveniência, suponha que x(0) é um vetor nulo.

Exemplo

A Figura 5.1 traz o exemplo de uma p-simulação no grafo da Figura 5.2, para k = 8,

com a função f dada por

f(M) =∑

m∈M

m.

1Suprimiremos o subscrito quando o grafo estiver subentendido no texto.

37 5.1. Simulação

p

00

0

0

00

0

0

x(0)

p

10

0

0

00

0

0

x(1)

p

11

0

0

00

0

1

x(2)

79

6

2

02

6

9

x(4)

2528

26

10

210

26

28

x(5)

p

32

2

0

00

2

2

x(3)

p p

291370

350

198

60186

348

370

x(7)

1031

1359

1288

794

258732

1274

1359

x(8)

p

81105

92

48

1246

92

105

x(6)

p p

Figura 5.1: Simulação em um grafo G

5.1.1 Efeitos de uma p-simulação

Sabemos que, na i-ésima rodada de uma p-simulação, x(i)v é o valor atribuído pela

função f ao vértice v. Antes do inicio da p-simulação, todos os vértices possuem

valor 0, não sendo possível distinguir os vértices entre si. Na primeira rodada, temos

que o valor de p é 1 e o valor dos demais vértices é 0. Com isso, podemos dizer que

a primeira rodada de uma p-simulação distingue o vértice pivô dos demais vértices

do grafo. Conforme o número de rodadas vai aumentando, mais vértices podem ser


distinguidos uns dos outros através dos valores atribuídos pela função f . Assim, se

na i-ésima rodada os valores de u e v forem diferentes (isto é, se x(i)u 6= x

(i)v ), dizemos

que u é distinguível de v, e estes vértices permanecem distinguíveis até o final da

simulação (mesmo que em alguma rodada posterior eles voltem a ter o mesmo valor).

Desse modo, podemos associar uma partição dos vértices do grafo a cada rodada

de uma p-simulação, onde vértices são agrupados de acordo com seus respectivos

valores naquela rodada. Antes de formalizar o conceito de uma partição associada

a uma rodada vamos definir partição e alguns conceitos relacionados.

5.1.2 Partições

Uma partição de V é uma família de subconjuntos disjuntos não vazios de V , onde

a união de todos eles é o próprio conjunto V . Uma partição ordenada de V é uma

sequência (V1, V2, . . . , Vr) tal que {V1, V2, . . . , Vr} é uma partição de V . O conjunto

de todas as partições de V e o conjunto de todas as partições ordenadas de V são

denotados por P(V ) e P ′

(V ), respectivamente.

Seja π ∈ P(V ) ∪ P ′

(V ) uma partição (ordenada ou não). Cada membro de π

é chamado de célula. Dizemos que uma célula em π é trivial se tiver apenas um

elemento. Se todas as células de π forem triviais, então π é chamada de partição

discreta, enquanto que, se π possuir apenas uma célula, então π é chamada de

partição unitária.

Duas partições ordenadas (V1, V2, . . . , Vr) e (W1,W2, . . . ,Ws) são compatíveis se

r = s e, para todo índice i entre 1 e r, vale que |Vi| = |Wi|.

Seja π = (V1, V2, . . . , Vr) uma partição ordenada de V . Para cada x ∈ V defini-

mos idx(x, π) = i, onde x ∈ Vi.

Sejam π1 e π2 duas partições. Dizemos que π1 é um refinamento de π2 se toda

célula de π1 for um subconjunto de alguma célula de π2. Dizemos que (W1, . . . ,Ws)

é um refinamento ordenado de (V1, . . . , Vr) se:

39 5.1. Simulação

(i) {W1, . . . ,Ws} for um refinamento de {V1, . . . , Vr};

(ii) se Wi ⊆ Va, Wj ⊆ Vb e a < b, então i < j.

5.1.3 Partição associada a uma rodada

Vamos definir agora, para cada i ∈ {0, 1, . . . , k}, uma partição ordenada ψ(i)G,p que

será a partição associada a x(i), ou seja, a partição associada à i-ésima rodada de

uma p-simulação. Em ψ(i)G,p, temos que u está na mesma célula que v se e somente

se

x(j)u = x(j)

v , (5.1)

para todo j, com 1 ≤ j ≤ i. Para definir a ordem das células em ψ(i)G,p, sejam u e v

vértices em células distintas, e seja j, com 1 ≤ j ≤ i, o primeiro índice que viola a

condição (5.1). Nesse caso, a célula de u precede a célula de v em ψ(i)G,p se e somente

se x(j)u < x

(j)v . Observe que, para todo i ∈ [k], ψ(i)

G,p é um refinamento ordenado de

ψ(i−1)G,p .

Proposição 1. Se a função f satisfaz f({0, . . . , 0}) = 0 e f({1, 0, 0, . . . , 0}) 6= 0

então a partição ψ(2)G,p possui exatamente três células, a saber:

ψ(2)G,p =

(

NG(p), NG(p), {p}).

Demonstração. Pela definição de simulação, temos que ψ(1)G,p terá apenas o vértice p

distinguido dos demais, porque o vetor x(1) possuirá o valor 0 em todas as posições,

exceto em x(1)p , que terá o valor 1.

Seja Miv um multiconjunto formado pelos valores do vetor x(i) nas posições

dadas pelos vértices de NG[v], para v ∈ V (G). Na segunda rodada, o vetor x(2) terá

a seguinte configuração: a posição p terá o valor 1, pois em x(1), todas as posições

relativas aos vizinhos de p possuem valor 0, e x(1)p possui valor 1. Logo,M1

p terá um


único elemento 1, e os demais serão 0. Com isso, f(M1p) 6= 0 por hipótese.

Agora vamos analisar a aplicação da função nos vizinhos de p. Para todo u ∈

NG(p), o multiconjunto M1u também será formado por um único elemento 1, e

os demais 0. Isso ocorre pois o único vizinho de u que possui o valor 1 em sua

respectiva posição no vetor x(1) é p. Os demais terão o valor 0 em suas posições em

x(1). Também por hipótese, f(M1u) 6= 0.

Para todo o vértice w ∈ NG(p), o multiconjunto M1w conterá apenas elementos

0, pois todas as posições relativas aos vértices da vizinhança fechada de w possui o

valor 0 em x(1). Portanto, f(M1w) = 0 por hipótese.

Com isso, o vetor x(2) apresentará a seguinte configuração: x(2)p = 1, x(2)

u = 1,

para todo u ∈ NG(p), e x(2)w = 0, para todo w ∈ NG(p). Note que, apesar de x(2)

p

e x(2)u poderem possuir os mesmos valores, o vértice p já foi distinguido na primeira

rodada. Com isso, a partição ψ(2)G,p possuirá três células: ψ(2)

G,p[1] contendo os vértices

que não são vizinhos de p, ψ(2)G,p[2], com os vértices vizinhos de p e ψ(2)

G,p[3] contendo

apenas o vértice p, o que encerra a prova.

5.1.4 Algoritmo para uma p-simulação

Antes de apresentarmos o algoritmo para uma p-simulação, é necessário algumas

definições: dada a partição ordenada π, denotamos por π[i] a i-ésima célula de π. O

símbolo · denota a operação de concatenação de duas partições, que é definida por:

π · σ = (π[1], π[2], . . . , π[r], σ[1], σ[2], . . . , σ[s]), onde r = |π| e s = |σ|. Sejam π e σ

duas partições compatíveis. Dizemos que duas células π[i] e σ[j] são correspondentes

se i = j. Seja X uma célula de uma partição, denotamos por X〈j〉 o j-ésimo menor

elemento deX. O Algoritmo 12 formaliza os passos envolvidos em uma p-simulação2.

O Algoritmo 13 subdivide uma célula Z, da partição ψ(k)G,p de acordo com os

2O conceito de partição igualitária será abordado na Seção 5.3

41 5.1. Simulação

Algoritmo 12: SimulaçãoEntrada: G, p, f : M→ N

Saída: Célula ψ(k)G,p

1 início

2 k ← 1

3 ψ(1)G,p ←

(

V (G) \ {p}) · ({p})

4 para todo v ∈ V (G) faça

5 x(1)v ← 0

6 fim para todo

7 x(1)p ← 1

8 repita

9 ψ ← ()

10 t← |ψ(k)G,p|

11 para todo v ∈ V (G) faça

12 x(k)v ← f

({x(k−1)w : w ∈ NG[v]})

13 fim para todo

14 para i de 1 até t faça

15 ψ ← ψ· RefinaCelula(ψ(k)G,p[i], x(k))

16 fim para

17 ψ(k)G,p ← ψ

18 k ← k + 1

19 até ψ(k)G,p seja igualitária;

20 retorna ψ(k)G,p

21 fim

valores obtidos através da aplicação de uma função f em NG(z), para todo z ∈ Z.

Estes valores são armazenados no vetor x(k), na posição z. O primeiro passo é

ordenar os vértices de Z de acordo com os valores que eles possuem no vetor x(k),

de modo crescente. Este passo é realizado para otimizar o processo de verificação

de quais vértices possuem valores iguais no vetor x(k) (pela equação 5.1 dois vértices

a, b estão em uma mesma célula se e somente se x(k)a = x

(k)b ). O próximo passo

do algoritmo é realizar uma varredura no vetor x(k), inserindo os vértices em suas

respectivas células. Uma nova célula é criada sempre que o valor de x(k)s for diferente

de seu antecessor x(k)s−1.


Algoritmo 13: RefinaCelula

Entrada: Célula Z, vetor x(k)

Saída: Partição π1 início

2 Ordenar Z conforme o valor de x(k)z para cada z ∈ Z, em ordem crescente

3 j ← 14 π[1]← {Z〈1〉}5 para s de 2 até |Z| faça

6 se x(k)Z<s−1> 6= x

(k)Z〈s〉 então

7 j ← j + 18 π[j]← ∅9 fim se

10 π[j]← π[j] ∪ {Z〈s〉}11 fim para

12 retorna π

13 fim

5.1.5 Árvore de partição

Uma árvore de partição TG,p é construída a partir das partições de V associadas

a cada rodada de uma p-simulação em G. O conjunto de nós dessa árvore é a

união disjunta de todas as partições ψ(i)G,p, para i ∈ {0, 1, . . . , k}. A raiz de TG,p é

o conjunto V (que é uma célula da partição ψ(0)G,p) e um nó A ∈ ψ(i)

G,p é filho de um

nó C ∈ ψ(i−1)G,p se A ⊆ C. Ademais, se dois nós A e B no nível i são filhos de um

mesmo nó C, então A encontra-se à esquerda de B se x(i)a < x

(i)b para algum a ∈ A e

algum b ∈ B; e A encontra-se à direita de B se x(i)a > x

(i)b para algum a ∈ A e algum

b ∈ B. Isto ocorre pois no refinamento de uma célula, os vértices são ordenados de

forma crescente (linha 2 do Algoritmo 13). Por fim, temos que a partição associada

à última rodada da p-simulação será denotada por ψG,p, ou seja, ψG,p = ψ(k)G,p.

Exemplo

A Figura 5.3 traz a árvore de partição para a p-simulação mostrada na Figura 5.1.

A Figura 5.2 abaixo mostra o grafo de exemplo com seus vértices rotulados.

43 5.1. Simulação

pa

b

c

def

g

Figura 5.2: Grafo G rotulado

ψ(0)G,p

ψ(1)G,p

ψ(2)G,p

ψ(3)G,p

ψ(5)G,p

ψ(6)G,p

ψ(7)G,p

ψ(8)G,p

ψ(4)G,p

Particao Unitaria

{a, b, c, d, e, f, g} {p}

{b, c, d, e, f} {a, g} {p}

{c, d, e} {b, f} {a, g} {p}

{d} {c, e} {b, f} {a, g} {p}

{d} {c, e} {b, f} {a, g} {p}

{p}{a, g}{b, f}{c}{e}{d}

{d} {e} {c} {f} {b} {a, g} {p}

{p}{a, g}{b}{f}{c}{e}{d}

Figura 5.3: Árvore de partição.


5.2 Propriedades de uma p-simulação

Lema 1. Seja ϕ um isomorfismo entre grafos G e H, e seja v ∈ V (G) um vértice

qualquer. Então NH [ϕ(v)] = ϕ(NG[v]).

Demonstração. Seja v como no enunciado e w ∈ NG(v) um vértice qualquer. Se

{v,w} ∈ E(G), então {ϕ(v), ϕ(w)} ∈ E(H). Portanto ϕ(w) ∈ NH(ϕ(v)). Como w

é qualquer, fica estabelecido que NH(ϕ(v)) ⊇ ϕ(NG(v)).

Reciprocamente, seja u ∈ NH(ϕ(v)) um vértice qualquer. Como ϕ é sobrejetora,

existe w ∈ V (G) com ϕ(w) = u. Com isso temos

{ϕ(w), ϕ(v)} ∈ E(H)⇒ {v,w} ∈ E(G)⇒ w ∈ NG(v).

Conclui-se que u = ϕ(w) ∈ ϕ(NG(v)). Como u é qualquer, fica estabalecida a

inclusão NH(ϕ(v)) ⊆ ϕ(NG(v)).

Para concluir a prova do lema, observe que ϕ(v) ∈ NH [ϕ(v)] ∩ ϕ(NG[v]).

A seguir, apresentamos a propriedade fundamental de uma p-simulação.

Teorema 2. Sejam G ∼= H dois grafos, seja ϕ um isomorfismo entre G e H, e

seja ψG,p = (V1, . . . , Vr) a partição associada a uma p-simulação em G, para algum

p ∈ V (G). Nessas condições, vale que

ψH,ϕ(p) = (ϕ(V1), . . . , ϕ(Vr)), (5.2)

onde ϕ(Vi) = {ϕ(v) : v ∈ Vi}.

Demonstração. Sejam G, H, ϕ e p conforme o enunciado do teorema. Seja q = ϕ(p).

Seja x(1), . . . , x(k) uma p-simulação em G, e seja y(1), . . . , y(k) uma q-simulação em

45 5.2. Propriedades de uma p-simulação

H. Vamos primeiro mostrar, por indução em i, que

∀ v ∈ V (G) : y(i)ϕ(v) = x(i)

v . (5.3)

Quando i = 1, pela definição de p-simulação, temos x(1)v = 1 se v = p e x(1)

v = 0

se v 6= p. Pela definição de q-simulação, temos y(1)ϕ(v) = 1 se ϕ(v) = q (isto é, se

v = p) e x(1)ϕ(v) = 0 caso contrário. Assim, segue que (5.3) vale para i = 1.

Suponha então que i > 1, e suponha que (5.3) valha com i − 1 no lugar de i.

Nesse caso, temos

y(i)ϕ(v) = f

({y(i−1)u : u ∈ NH [ϕ(v)]})

= f({y(i−1)

ϕ(w) : w ∈ ϕ−1(NH [ϕ(v)]})

= f({y(i−1)

ϕ(w) : w ∈ ϕ−1(ϕ(NG[v]))})

= f({y(i−1)

ϕ(w) : w ∈ NG[v]})

= f({x(i−1)

w : w ∈ NG[v]})

= x(i)v .

A primeira igualdade segue da definição de y(i)ϕ(v), a segunda do fato de que ϕ é

um isomorfismo, a terceira segue do Lema 1, a quinta segue da hipótese de indução

e a sexta da definição de x(i)v . Portanto (5.3) é verdade.

Agora temos que mostrar (5.2). Sejam u, v ∈ V (G) vértices quaisquer. Se

u, v ∈ Vℓ para algum ℓ, então x(j)u = x

(j)v para todo j ∈ {0, 1, . . . , k}. Usando (5.3),

temos que y(j)ϕ(u) = y

(j)ϕ(v) para todo j ∈ {0, 1, . . . , k}, o que implica que ϕ(u) e ϕ(v)

pertencem à mesma célula de ψH,ϕ(p). Isso mostra que {ϕ(V1), . . . , ϕ(Vr)} é um refi-

namento de ψH,ϕ(p). Um argumento simétrico mostra que ψH,ϕ(p) é um refinamento

de {ϕ(V1), . . . , ϕ(Vr)}. Portanto, as células dessas partições são as mesmas.

Por se tratar de uma identidade de partições ordenadas, resta ainda mostrar


que a ordem relativa das células de ψH,ϕ(p) e (ϕ(V1), . . . , ϕ(Vr)) é a mesma. Para

isso, suponha que u ∈ Vi e v ∈ Vj com i < j. Isso implica que x(ℓ)u < x

(ℓ)v para

algum ℓ ≤ k e x(m)u = x

(m)v para todo m entre 0 e ℓ − 1. Mas então, por (5.3),

vale que ∀m ∈ {0, . . . , ℓ − 1} temos y(m)ϕ(u) = y

(m)ϕ(v) e y(ℓ)

ϕ(u) < y(ℓ)ϕ(u). Isso implica que

idx(ϕ(u), ψH,ϕ(p)) < idx(ϕ(v), ψH,ϕ(p)) e portanto a ordem das classes também é

respeitada.

O Teorema 2 permite que p-simulações sejam usadas para resolver o Problema

do Isomorfismo de Grafos, pois a célula em que um dado vértice é colocado, ao final

de uma p-simulação, independe do nome inicialmente dado a ele. É por esse motivo

que, se dois grafos G e H são isomorfos e se q ∈ V (H) é a imagem de um vértice

p ∈ V (G) por algum isomorfismo em Iso(G,H), então uma p-simulação em G e uma

q-simulação em H fazem a mesma classificação dos vértices. Essa idéia é resumida

no enunciado a seguir.

Corolário 1. A partição ψG,p independe dos nomes dos vértices do grafo.

5.3 Algoritmo proposto

Denotamos por L(G) o conjunto

L(G) = {ψG,p : p ∈ V (G)}.

Nesta seção, propomos o Algoritmo 14, que decide se dois grafos G e H são

isomorfos. Vamos supor que V (G) ∩ V (H) = ∅.

Este algoritmo tem como entrada os grafos G e H, e como saída sim se os grafos

são isomorfos, e não caso contrário. Podemos dividir o algoritmo em duas etapas

principais: na primeira, fazemos p-simulações para todo vértice p ∈ V (G) e, ao final

47 5.3. Algoritmo proposto

Algoritmo 14: Verifica se dois grafos são isomorfosEntrada: Grafos G e HSaída: sim se G e H são isomorfos, não caso contrário

1 início

2 π ← ∅3 para todo p ∈ V (G) faça

4 ψG,p ← Simulação(G, p, f)5 se ψG,p é discreta então

6 π ← ψG,p

7 Sai do laço8 senão

9 L(G)← L(G) ∪ {ψG,p}

10 se π 6= ∅ então

11

({u1}, {u2}, . . . , {un})← π

12 para todo q ∈ V (H) faça

13 fazer q-simulação em H para obter ψH,q

14 se ψH,q é discreta então

15

({v1}, {v2}, . . . , {vn})← ψH,q

16 ϕ← mapeamento que leva ui 7→ vi

17 se ϕ é um isomorfismo de G em H então

18 retorna sim

19 retorna não

20 senão

21 para todo q ∈ V (H) faça

22 fazer q-simulação em H para obter ψH,q

23 L(H)← L(H) ∪ {ψH,q}24 Construir grafo bipartido R = (V (G) ∪ V (H), E = ∅)25 para todo {p, q} ∈ E(R) faça

26 se ψG,p for compatível com ψH,q então

27 E(R)← E(R) ∪ {p, q}

28 M ← Emparelhamento perfeito obrido pelo Algoritmo 329 ~D ← ~D(R,M)30 EnumerarCandidatoIsomorfismo(~D,M)31 retorna não

32 fim

desta etapa, temos o conjunto L(G) que contém todas as partições ψG,p. A segunda

etapa do algoritmo é a verificação do isomorfismo. Esta etapa subdivide-se em dois


casos:

1. existe vértice u ∈ V (G) tal que ψG,u é a partição discreta;

2. ψG,u não é discreta para nenhum vértice u.

No primeiro caso, é necessário fazer q-simulações para todo vértice q ∈ V (H) e

verificar, para toda partição ψH,q que for discreta, se o mapeamento que leva ψG,u nos

vértices correspondentes de ψH,q (preservando a ordem das células) é um isomorfismo

entre G e H. Se algum desses mapas for um isomorfismo, o algoritmo para e devolve

sim. Caso contrário o algoritmo devolve não.

No segundo caso, considera-se um grafo bipartido R = (V (G)∪V (H), E), inicial-

mente vazio (sem nenhuma aresta entre V (G) e V (H)). Para cada par não ordenado

{p, q} de V (G)× V (G), acrescenta-se a aresta {p, q} se as partições ψG,p e ψH,q são

compatíveis3. Caso contrário, não pode haver um isomorfismo que mapeie p ∈ V (G)

a q ∈ V (H). Portanto, neste caso, a aresta {p, q} não é inserida em R.

Dados v ∈ V e W ⊂ V , definimos dG(v,W ) como o número de elementos de W

que são adjacentes a v em G. Dizemos que π ∈ P(V ) ∪ P ′

(V ) é uma partição

igualitária com relação ao grafo G (ou G-igualitária) se, para todo par de células

V1, V2 ∈ π (não necessariamente distintas) e para quaisquer elementos x, y ∈ V1,

temos que dG(x, V2) = dG(y, V2). O Teorema 3 mostra que, se uma partição G-

igualitária for encontrada, então a árvore de partições estabilizará.

A Figura 5.4 mostra um exemplo de partição G-igualitária e não igualitária:

na partição π, tomamos as célula V1 = {0, 1} e V2 = {2, 3}. A partição π não é

igualitária, pois dG(0, V2) = 0 e dG(1, V2) = 1.

3Como visto anteriormente, duas partições são compatíveis se ambas possuírem o mesmo númerode células, e se todas as células correspondentes possuírem o mesmo número de elementos


0

1

2

3

4

5

6

π nao e igualitaria.

0

1

2

3

4

5

6

σ e igualitaria.

Figura 5.4: Exemplos de partições.

Teorema 3. Uma árvore de partições Tp se estabiliza ao encontrar uma partição

G-igualitária.

Demonstração. Seja π a partição ψ(k)G,p e i = idx(v, π) para todo v ∈ V (G). Definimos

por dyj o grau que um vértice qualquer da célula π[y] possui dentro da célula π[j].

Observe que d(v, π[j]) = dij. Definimos por x(k)i o valor de x(k)

u para algum u ∈ π[i].

Pela definição de x(k+1)v temos:

x(k+1)v = f

({x(k)u : u ∈ N [v]})

= f({x(k)

idx(u,π) : u ∈ N [v]})

= f

( n⋃

j=1

dij{x(k)j }

)

Observe que a fórmula à direita do símbolo = independe de v, mas apenas de

i = idx(v, π), que é igual para todo vértice em π[i]. Portanto, x(k+1)v é igual para

todo v ∈ π[i].

Logo, se ψ(k)G,p é G-igualitária, então ψ(k)

G,p[j] = ψ(k+1)G,p [j],∀j ∈ {0, . . . , |ψ(k)

G,p|}.


5.3.1 Emparelhamentos perfeitos e isomorfismo

Após a construção do grafo bipartido R, o algoritmo verifica se os emparelhamentos

perfeitos de R podem corresponder a um isomorfismo. Como vimos na Seção 4.1, o

algoritmo de Uno [38] lista todos os emparelhamentos perfeitos em um grafo bipar-

tido de forma recursiva, onde em um ramo da recursão é fixada uma aresta arbitrária

e em um emparelhamento, e no outro ramo e é retirado do emparelhamento perfeito.

Como o objetivo do nosso algoritmo é encontrar um isomorfismo entre os grafos G

e H, ao escolher uma aresta e, podemos ignorar os emparelhamentos perfeitos que

não correspondem a um isomorfismo. Para tanto, modificamos o Algoritmo 10 de

modo que arestas cujas extremidades estão em células não correspondentes não se-

jam inseridas em ~D(+e).

Veja o exemplo: dados dois grafos G e H, um isomorfismo ϕ : V (G) → V (H) e

as arestas a = {p, q}, f = {u, v} ∈ R. Suponha que ϕ(p) = q. Se ϕ(u) ∈ ψH,q[i] e

v ∈ ψH,q[j], com i 6= j, então ϕ 6= v. Portanto, a aresta f não estará presente no

digrafo ~D(+e) pois não há um isomorfismo que leva u em v.

D

D(+e1) D(

−

e1)

D(+e1

+e2) D(

+e1

−

e2) D(−

e1+e2) D(

−

e1−

e2)

D(+e1

+e2

+e3) D(

+e1

+e2

−

e3) D(+e1

−

e2+e3) D(

+e1

−

e2−

e3) D(−

e1+e2

+e3) D(

−

e1+e2

−

e3) D(−

e1−

e2+e3) D(

−

e1−

e2−

e3)

Figura 5.5: Exemplo de árvore de recursão do Algoritmo 15.

Assim, reescrevemos o Algoritmo 10 de modo que as arestas de R cujas extremi-

dades estejam em células não correspondentes em duas partições compatíveis ψG,p

e ψH,q não estejam presentes no digrafo ~D(+e).

Na primeira chamada do Algoritmo 15 é passado o digrafo D(R,M), onde M foi

obtido pelo Algoritmo 3. O grafo D(+e) é obtido eliminando-se as pontas da aresta


e e todas as arestas não correspondentes. Já o grafo D(−e) é obtido deletando-se a

aresta e.

Algoritmo 15: EnumerarCandidatoIsomorfismoEntrada: D,M

1 início

2 se M ′ corresponde a um isomorfismo então

3 para e imprime isomorfismo entre G e H4 fim se

5 se E(D) = ∅ então

6 Fim

7 fim se

8 Encontrar um circuito C M -alternante9 Escolher uma aresta arbitrária e ∈ C ∩M

10 M ′ ← C∆M

11 Gerar grafo D(+e)

12 EliminarArestasDesnecessarias (D(+e))

13 EnumerarCandidatoIsomorfismo (D(+e),M)

14 Gerar grafo D(−e)

15 EliminarArestasDesnecessarias (D(−e))

16 EnumerarCandidatoIsomorfismo (R(−e),M ′)

17 fim

Como visto na Seção 4.1, todo emparelhamento perfeito obtido em D(+e) pode

ser estendido a R adicionando-se a aresta e. Já o emparelhamento perfeito obtido

através de D(−e) é também um emparelhamento perfeito de R.

CAPÍTULO 6

Algoritmo Pratical Graph Isomorphism

Neste Capítulo descreveremos o funcionamento do algoritmo utilizado no programa

Nauty, proposto por McKay [25].

O algoritmo Pratical Graph Isomorphism (PGI) é baseado em uma rotulação

canônica e no grupo de automorfismos de um grafo. Uma rotulação canônica pode

ser entendida como um processo que recebe um grafo e devolve uma rotulação dos

vértices desse grafo, sempre produzindo a mesma saída quando as entradas são grafos

isomorfos. A ideia central do PGI é comparar as rotulações canônicas de G e H e

caso sejam iguais, os grafos G e H são isomorfos. Caso contrário, o PGI retorna

não-isomorfos.

Para encontrar uma rotulação canônica, o PGI se divide em duas partes princi-

pais: o procedimento de refinamento e o procedimento de busca. Em linhas gerais,

o procedimento de refinamento tem como entrada uma partição qualquer π e como

retorno uma partição igualitária dos vértices de G que é um refinamento de π. O pro-

Capítulo 6. Algoritmo Pratical Graph Isomorphism 54

cedimento de busca é um algoritmo recursivo que recebe uma partição G-igualitária

e introduz uma assimetria nesta partição para uma subsequente execução do proce-

dimento de refinamento. Este processo recursivo é repetido até se encontrar todas1

as partições discretas de V (G). A cada partição discreta obtida pelo procedimento

de busca é associado um grafo, e a rotulação será um destes grafos, escolhido segundo

uma ordem pré-estabelecida.

Nas próximas seções, mostraremos o funcionamento da etapa de refinamento e

do algoritmo recursivo do procedimento de busca.

6.1 Rotulação canônica e isomorfo canônico

Nesta seção, definiremos o conceito de isomorfo canônico. Para tanto, precisamos

introduzir alguns conceitos iniciais: seja G o conjunto de todos os grafos sobre o

conjunto de vértices {1, . . . , n}. Uma rotulação canônica é uma função C : G → G tal

que, para todo par de grafos isomorfos G e H pertencentes a G, vale C(G) = C(H).

Para um dado grafo G, o grafo C(G) é chamado isomorfo canônico.

Seja π uma partição discreta de V = {1, 2, . . . , n}. Definimos γπ ∈ Sn como

uma permutação tal que γπ(v) = idx(v, π). Denotamos por γπ(G) o grafo obtido

através da permutação γπ em V (G). Seja P ={{x1, y1}, . . . , {xt, yt}

}

o conjunto

de pares(V

2

)

. Podemos representar o grafo G por um vetor característico χE(G), de

comprimento t = n(n − 1)/2, que possui o valor 1 na posição j se o par {xj , yj} ∈

E(G) e 0 caso contrário. Dados grafos G e H, definimos G � H se χE(G) ≤ χE(H)

lexicograficamente.

Para encontrar um isomorfo canônico, o PGI refina uma partição dos vértices de

G, de modo a encontrar uma partição discreta de V (G). Caso isso não seja possível,

o PGI constrói uma árvore de busca na qual todas as folhas corresponderão a uma

1Este processo não lista todas as n! partições discretas, mas apenas aquelas que terão utilidadepara se encontrar a rotulação canônica.

55 6.2. Refinamento de partições

partição discreta π de V (G). O isomorfo canônico C(G) então será o maior grafo

γπ(G), de acordo com a ordem de �, onde π é uma partição discreta associada a uma

folha da árvore de partições de G. Em seguida, o PGI executa os mesmos passos

para calcular C(H) e verifica o isomorfismo entre G e H comparando os isomorfos

canônicos C(G) e C(H), pois G e H serão isomorfos se e somente se C(G) = C(H).

A comparação dos isomorfos canônicos é muito eficiente, pois basta comparar o

conjunto de arestas destes grafos, que demanda um tempo O(n2).

Na próxima seção, mostraremos como o PGI executa o procedimento de refina-

mento.

6.2 Refinamento de partições

O objetivo principal da etapa de refinamento é encontrar uma partição G-igualitária

que seja um refinamento de uma determinada partição π. A seguir, mostraremos

como este procedimento é realizado.

Para uma partição ordenada π de V (G), existe um conjunto Z(π) de partições

ordenadas de V (G) que são refinamentos de π e, ao mesmo tempo, partições G-

igualitárias.2 Note que Z(π) 6= ∅, pois a partição discreta é sempre G-igualitária e é

um refinamento de π. É possível argumentar3 que existe uma partição ζ(π) ∈ Z(π)

que satisfaz σ ≤ ζ(π) para toda σ ∈ Z(π). Em outras palavras, existe uma única

partição que é um refinamento G-igualitário de π com o número mínimo possível de

células, denominada ζ(π).

A estratégia do PGI é encontrar a partição ζ(π) a partir de uma partição or-

denada π. Mas para determinados tipos de grafos (por exemplo, os grafos vértice-

transitivos), a partição ζ(π) não será discreta. Isso torna-se uma dificuldade para

o PGI, pois como vimos, o isomorfo canônico está associado a uma partição dis-

2Neste capítulo, omitiremos as provas. Para detalhes, consulte o artigo [25]3Seção 2.3 de [25]


creta de V (G). Para resolver este problema, o PGI cria novas partições ordenadas

σ1, σ2, . . . , σm (onde m é o tamanho da maior célula de ζ(π)), refina cada uma destas

novas partições ordenadas obtidas e executa este processo sucessivamente até encon-

trar partições discretas de V (G) (esta etapa será explicada nas Seções 6.4 e 6.5). A

seguir, apresentamos o algoritmo que executa o procedimento de refinamento para

uma partição ordenada π.

6.3 Algoritmo de refinamento

O objetivo principal do Algoritmo 16 é encontrar uma partição G-igualitária que seja

um refinamento da partição π passada como argumento. Para tanto, o Algoritmo

16 de refinamento recebe, além do grafo G, uma partição ordenada π ∈ V (G) e uma

sequência α = (W1,W2, . . . ,WM ) de células distintas de π, que respeita a ordem de

π, e tem como saída uma partição ordenada, denominada R(G,π, α), de V (G). O

processo de refinamento consiste, a grosso modo, em verificar o número de vizinhos

que os vértices de uma célula de π possuem em relação a algum elemento de α.

Esta verificação será abordada mais adiante, ainda nesta seção. Dado que antes da

execução do Algoritmo 16, a única partição de V (G) conhecida é a partição unitária

π = V (G), então, inicialmente, o Algoritmo 16 receberá como argumentos o grafo

G, a partição unitária π e a sequência de células α = π. Pelo Teorema 4, temos que

a partição R(G,π, π) retornada pelo Algoritmo 16 é a partição ζ(π).

Teorema 4. ([25]) Para todo grafo G e toda partição ordenada π de V (G), vale que

R(G,π, π) = ζ(π).

Antes de mostrarmos o Algoritmo 16, faz-se necessário algumas definições: o

tamanho de uma partição ordenada π é a quantidade de células que ela possui,

57 6.3. Algoritmo de refinamento

denotado por |π|. Lembre-se de que π[i] denota a i-ésima célula de π. Deno-

tamos por π[i, j] a sequência de células (π[i], π[i + 1], . . . , π[j]). O símbolo · de-

nota a operação de concatenação de duas partições, que é definida por: π · σ =

(π[1], π[2], . . . , π[r], σ[1], σ[2], . . . , σ[s]), onde r = |π| e s = |σ|. Seja γ uma permu-

tação do conjunto V (G). A imagem de v ∈ V sob γ é denotada por γ(v). Para

W ⊆ V , temos γ(W ) = {γ(w)|w ∈ W}. Para π = (V1, V2, · · · , Vr), definimos

γ(π) = (γ(V1), γ(V2), · · · , γ(Vr)).

A sequência de células α pode ser entendida como uma fila de processamento

de células. Para cada m, a célula π[k] é subdividida. Esta subdivisão é feita com

base no número de vizinhos que cada vértice em π[k] possui no conjunto α[m]. Ao

término desta subdivisão, a célula π[k] foi quebrada em novas células (σ[1], . . . , σ[s]).

Dados os subconjuntos X,Y ⊂ V (G), dizemos que X é homogêneo em relação a Y

se d(x, Y ) = d(x′, Y ) para todo x, x′ ∈ X. Pelo modo como π[k] foi subdividida, os

vértices x, y ∈ σ[i] têm o mesmo número de vizinhos dentro de α[m]. Portanto, todo

σ[i] é homogêneo em relação à α[m].

Após a subdivisão, todo σ[i] é inserido na fila. Isso é necessário pois para uma

célula π[j] qualquer, π[j] poderia ser homogênea em relação a π[k]. Com o refina-

mento, π[j] pode não ser homogênea em relação a todas as células de σ criadas a

partir de π[k]. Portanto, é necessário incluir todo4 σ[i] em α. Por fim, π é atuali-

zado, concatenando-se π com σ. Em outras palavras, a célula π[k] é substituída por

σ, visto que σ é um refinamento de π[k]. O processo então se repete com a próxima

célula da lista de processamento, até que o algoritmo encontre uma partição discreta,

ou termine de processar todas as células da lista α.

Caso a partição retornada não seja discreta, é necessário então continuar o pro-

cesso para forçar a obtenção de uma partição que seja discreta. Isto é feito através

4No Algoritmo 16, a maior célula de σ (linha 23: σ[t]) não é inserida na fila devido a umaotimização do algoritmo.


Algoritmo 16: Procedimento de RefinamentoEntrada: Grafo G, partição ordenada π de V (G) e α subsequência de πSaída: R(G,π, α)

1 início

2 π ← π3 m← 14 enquanto π não é discreta ou m ≤ |α| faça

5 π ← ()6 para k de 1 até |π| faça

7 p← |π[k]|8 (u1, . . . , up)← elementos de π[k] ordenados de tal forma que

d(ui, α[m]) < d(uj , α[m])⇒ i < j9 σ ← ({u1})

10 s← 111 para i de 2 até p faça

12 se d(ui−1,W ) = d(ui,W ) então

13 σ[s]← σ[s] ∪ {ui}14 senão

15 s← s+ 116 σ[s]← {ui}17 fim se

18 fim para

19 se s > 1 então

20 t← arg max{|σ[t]| : 1 ≤ t ≤ s}21 se α[j] = π[k] para algum j (m ≤ j ≤ |α|) então

22 α[j] ← σ[t]23 fim se

24 α← α · σ[1, t− 1] · σ[t + 1, s]25 π ← π · σ26 fim se

27 fim para

28 π ← π29 m← m+ 130 fim enquanto

31 retorna π

32 fim

de um algoritmo recursivo, que isola um vértice na partição obtida e executa o

procedimento de refinamento novamente. Nas duas próximas seções, mostraremos

como é feita a escolha deste vértice e explicaremos o funcionamento deste algoritmo

59 6.4. Partições aninhadas

recursivo.

6.4 Partições aninhadas

Seja π = (V1, V2, . . . , Vk) uma partição ordenada de V (G) e v ∈ Vi para algum i.

Definimos π ◦ v =

1. π, se |Vi| = 1.

2. (V1, . . . , Vi−1, v, Vi \ v, Vi+1, . . . , Vk), se |V1| > 1

Definimos também π ⊥ v = R(G,π ◦ v, (v)).

Teorema 5. ([25]) Seja G um grafo, π uma partição ordenada de V (G) e suponha

que há alguma partição G-igualitária σ tal que π ≤ σ. Se escolhermos α ⊆ π tal que

para todo W ∈ σ, temos X ⊆W para, no máximo, um X ∈ π \α, então, R(G,π, α)

é G-igualitária.

Pelo Teorema 5, temos que R(G,π ◦ v, (v)) é G-igualitária.

Dado um grafo G, uma partição ordenada π de V (G) e uma sequência v =

v1, v2, . . . , vm−1 de vértices distintos de V , definimos por ν = (π1, π2, . . . , πm) a

sequência de partições aninhadas derivadas de G, π e v, onde:

1. π1 = R(G,π, π) e,

2. πi = πi−1 ⊥ vi−1, para 2 ≤ i ≤ m.

O conjunto de todas as sequências de partições aninhadas derivadas de algum

G,π e um vetor v de elementos distintos de V é denotado por N(V ).

6.5 Árvore de busca

Uma árvore de busca T (G) é o conjuntos de todas as partições aninhadas ν ∈ N(V )

tal que ν é derivado de um grafo G, uma partição ordenada π de V (G) e uma


sequência v1, v2, . . . , vm−1 onde, para 1 ≤ i ≤ m− 1, vi é um elemento da primeira

célula não trivial de πi que possui o menor tamanho. A definição implica que |πi| <

|πi+1| para 1 ≤ i < m. A sequência ν também é chamada de nó da árvore. Seja

ν = (π1, π2, . . . , πm) um nó da árvore T (G). Dizemos que ν é um nó terminal se

πm for discreta. Dados dois nós ν1 = (π1, π2, . . . , πm) e µ = (π1, π2, . . . , πm, πm+1),

dizemos que µ é sucessor (ou filho) de ν. De mesmo modo, dizemos que ν é antecessor

(ou pai) de µ. O nó ν = (π1) é um ancestral comum a todos os nós, já que a escolha

de π1 está fixada: π1 = R(G,π, π).

O algoritmo 17 encontra todos os nós da árvore T (G), tendo como partição inicial

a partição unitária π = ({V (G)}).

Algoritmo 17: Árvore de BuscaEntrada: Grafo G

1 início

2 π ← (

V (G))

3 ν ← (R(G,π, π))

4 Gera(ν)5 fim

Observe que o Algoritmo 18 é um algoritmo de backtracking, onde os nós ν de

T (G) são gerados de forma recursiva5. Note que, no Algoritmo 18, a partição π será

impressa se ela for discreta. As demais partições do nó ν são utilizadas apenas para

o backtracking do algoritmo, pois como já visto anteriormente, apenas as partições

discretas geradas neste processo terão utilidade para o cômputo do isomorfo canônico

C(G) e, consequentemente, para a verificação do isomorfismo.

Observe que não serão todas as n! partições discretas de V (G) que serão geradas

pelo Algoritmo 18. Isso ocorre pois os vértices que serão isolados durante o backtrac-

5O algoritmo 17 é uma versão recursiva do algoritmo iterativo apresentado por B. McKay em[25], página 55.

61 6.5. Árvore de busca

Algoritmo 18: Gera(ν)Entrada: ν

1 início

2 k ← |ν|3 π ← ν[k]4 se π é discreta então

5 Imprime π6 retorna

7 fim se

8 t← min{i : |π[i]| > 1}9 W ← π[t]

10 para cada v ∈W faça

11 σ ← π ⊥ v12 Gera(ν · (σ))13 fim para

14 fim

king estarão obrigatoriamente em uma célula não trivial (veja linha 7 do Algoritmo

18). Assim, células triviais não serão alteradas e terão suas posições fixadas no nós

descendentes na árvore de busca.

Além disso, pelo Teorema 6, temos que a quantidade de partições discretas ge-

radas pelo Algoritmo 18 para o grafo G é igual ao número de partições discretas

geradas pelo Algoritmo 18 para o grafo H.

Figuras 6.1 e 6.2 temos um exemplo de um grafo G e a árvore de busca T (G).

1

3

5

76

4

2

0

Figura 6.1: Grafo G.


π = ({0, . . . , 7})

π1 = ({7}, {6}, {0}, {5}, {1, 2}, {4}, {3})

ν1 =(

π1, π2 = ({7}, {6}, {0}, {5}, {1}, {2}, {4}, {3}))

ν2 =(

π1, π2 = ({7}, {6}, {0}, {5}, {2}, {1}, {4}, {3}))

Figura 6.2: Árvore T (G).

Como visto anteriormente, para cada partição discreta π impressa pelo Algo-

ritmo 18, associamos uma permutação γπ. Ao aplicarmos esta permutação no grafo

G, obtemos o grafo γπ(G), que é representado por seu vetor característico χE

(

γπ(G)).

Denotamos por P (G) o conjunto de todos grafos γπ(G). Assim, definimos o isomorfo

canônico de G como sendo o grafo

C(G) = max�{γπ(G) ∈ P (G)}

Teorema 6. ([25]) Se G e H são isomorfos, então P (G) = P (H).

Como visto, o Algoritmo 18 produz as partições discretas que serão utilizadas

para o cômputo do isomorfo canônico, através da associação de uma partição discreta

a uma permutação do grafo G. O processo então se repete para o grafo H e compara-

se os isomorfos canônicos C(G) e C(H). O Teorema 6 nos garante que se os grafos

G e H são isomorfos, então C(G) = C(H), pois como P (G) = P (H), então o grafo

máximo de P (G) é o mesmo para P (H).

A verificação do isomorfo canônico pode ser otimizada, utilizando-se o grupo de

automorfismos para descartar partições discretas impressas pelo Algoritmo 18. Na

próxima seção, veremos como o PGI utiliza o grupo de automorfismos de G para

podar a árvore de busca T (G) e otimizar ainda mais a busca pelo isomorfo canônico.

63 6.6. Podando a árvore de busca

6.6 Podando a árvore de busca

Se o grupo de automorfismos de um grafo G for grande (isso ocorre, por exemplo,

em grafos vértice-transitivos), então a árvore de busca T (G) terá muitos ramos

e, consequentemente, o número de nós terminais será, no mínimo, o tamanho de

Aut(G). Como a árvore é explorada em profundidade, então os automorfismos que

são descobertos durante a busca serão usados para podar a árvore de busca.

Sejam ν1 e ν2 dois nós terminais de uma árvore de busca T (G), e sejam π ∈

ν1 e σ ∈ ν2 partições discretas. Suponha que ν1 está a esquerda (será analisado

primeiramente pelo Algoritmo 18) de ν2 na árvore de busca. Se γπ(G) = γσ(G),

então a permutação τ : V → V definida por τ(v) = γ−1π

(

γσ(v))

é um automorfismo

de G.

Seja γ uma permutação de Sn e σ uma partição ordenada de V (G). Denotamos

por γ(σ) a partição ordenada obtida permutando-se os vértices de σ conforme γ. Seja

ν = (π1, π2, . . . , πm) um nó na árvore T (G). Denotamos por γ(ν) a permutação γ

aplicada a todas as partições de ν, ou seja, γ(ν) = (γ(π1), γ(π2), . . . , γ(πm)). Sejam

a, b, c nós de T (G) tal que a é o ancestral comum mais recente de ν1 e ν2, b é o filho

de a e ancestral de ν1 e c é o filho de a e ancestral de ν2. A permutação τ envia π a σ,

fixa a e envia b para c. Em outras palavras, temos que τ(π) = τ(σ) e τ(b) = τ(c).

Denotamos por T (G,x) uma subárvore de T (G) enraizada pelo nó x. Então T (G, c) é

isomorfa a T (G, b) (pela permutação τ), e portanto o conjunto de grafos gerados por

nós terminais de T (G, c) é o mesmo conjunto de grafos gerados por nós terminais de

T (G, b). Como a árvore de busca T (G) é explorada em profundidade, então T (G, b)

é visitada antes de T (G, c). Portanto6, não é necessário explorar T (G, c) e a busca

continua pelo nó a.

6O Algoritmo 18 não incorpora esta otimização

CAPÍTULO 7

Resultados

Neste capítulo vamos discutir os resultados obtidos nos testes do Algoritmo PGI e

também do algoritmo proposto. Para realizar os testes, implementamos o Algoritmo

proposto na linguagem C++, e o programa Nauty foi obtido no sítio nauty and

Traces [24] e testados em um computador com processador Intel Core i5 2.5GHz,

4GB de memória RAM e sistema operacional OS X Mavericks. Para efetuar os

testes, utilizamos um gerador de pares de grafos isomorfos e também bibliotecas

de grafos disponíveis em [23]. Nas próximas seções, o programa Nauty refere-se a

implementação do algoritmo PGI, e o programa Mabi (Matching based isomorphism

é a implementação do algoritmo proposto nesta dissertação, ambos na linguagem

C++, utilizando o compilador gcc, com diretiva de compilação O2. O código fonte

da implementação do algoritmo proposto está disponível no Anexo 9 e no repositório

Bitbucket1.

1https://bitbucket.org/rodrigedilson/dissertacao-isomorfismo-grafos

Capítulo 7. Resultados 66

7.1 Gerador de grafos aleatórios - instâncias positivas

Utilizamos o modelo de Erdős-Rényi, que gera um grafo G com n vértices e com m

arestas, em média. A probabilidade de uma aresta {u, v} ser inserida no grafo G é

dada por

p =m(n

2

) .

Para se gerar o grafo G, para cada par de vértices {u, v} é realizado um sorteio,

com probabilidade p de sucesso. Caso o sorteio seja bem sucedido, a aresta {u, v}

é inserida em G. O número de arestas do grafo será, com alta probabilidade, muito

próximo a m, pois a distribuição do número de arestas é binominal e possui grande

concentração em torno da média2.

Já o grafo H, isomorfo a G, é gerado permutando-se os vértices de G com uma

permutação γ ∈ Sn aleatória.

7.1.1 Resultados

A metodologia de testes foi gerar cinco pares de grafos com n vértices e m arestas e

executar tanto o programa Nauty quanto o programa Mabi para cada par de grafo.

Nas Tabelas 7.1 e 7.2, os valores se referem à média dos tempos de execução, em

segundos. Para os grafos densos, a quantidade de arestas foi dada por(n

2

)

e para os

grafos esparsos, a quantidade de arestas foi definida por 2n.

Tabela 7.1: Grafos aleatórios densos.

Vértices Nauty Mabi50 0.004 0.287100 0.017 2.490200 0.150 22.876400 0.945 191.211

2Veja desigualdade de Chernoff, em [1].

67 7.1. Gerador de grafos aleatórios - instâncias positivas

Tabela 7.2: Grafos aleatórios esparsos.

Vértices Nauty Mabi50 0.002 0.257100 0.002 0.375200 0.002 3.877400 0.005 24.014

Como observado nas tabelas, o algoritmo PGI teve um desempenho muito supe-

rior em todos os testes realizados. O motivo principal para tal superioridade é que

o PGI isola um vérice a cada chamada recursiva do algoritmo de refinamento. Em

outras palavras, a cada chamada recursiva, o algoritmo de refinamento tem como

parâmetro uma partição obtida em uma etapa anterior do backtracking. Já o algo-

ritmo proposto, por não ser um algoritmo de backtracking, não se utiliza da partição

obtida em uma simulação como informação para realizar uma próxima simulação.

Além disso o PGI possui uma otimização, que é a poda de ramos da árvore,

diminuindo a quantidade de grafos permutados que são obtidos a partir de uma

partição discreta de V (G), e consequentemente haverá uma diminuição do tempo de

cômputo do isomorfo canônico.

Ademais, na etapa de refinamento do PGI, a partição obtida sempre será iguali-

tária, o que não ocorre no algoritmo proposto, uma vez que o processo de simulação

pode se estabilizar sem encontrar uma partição igualitária. Isto ocorre pois a função

f utilizada na simulação não é bijetora, e ao implementarmos uma versão do Mabi

com uma função bijetora, o desempenho se mostrou ainda pior, pois era necessário

armazenar na memória todos os multiconjuntos encontrados durante as simulações.


7.2 Grafos com alto padrão de simetria

McKay, ao testar o Algoritmo PGI, mencionou em seu artigo alguns tipos de grafos

que trariam dificuldades para o PGI resolver o Problema de Isomorfismo de Grafos.

Dentre eles, testamos os grafos fortemente regulares.

É possível demonstrar formalmente que o Mabi é ineficiente para grafos forte-

mente regulares. Um grafo regular G, com v vértices e grau k, é dito fortemente

regular se houver inteiros i e j tal que todo par de vértices adjacentes possua i

vizinhos em comum e todo par de vértices não adjacentes possua j vizinhos em

comum.3

Para efetuar os testes com grafos fortemente regulares, aplicamos uma permuta-

ção aleatória a um grafo obtido na biblioteca de grafos fortemente regulares, e assim

conseguimos um par de grafos fortemente regulares isomorfos. Como no caso dos

grafos aleatórios, executamos os programas Nauty e Mabi por cinco vezes e calcula-

mos a sua média. A seguir, a Tabela 7.3 apresenta os resultados obtidos para grafos

fortemente conexos isomorfos (tempo em segundos):

Tabela 7.3: Grafos fortemente regulares isomorfos.

Características Nauty Mabiv = 25, k = 12, i = 5, j = 6 0.002 0.041v = 36, k = 14, i = 4, j = 6 0.002 16.496

7.2.1 Grafos fortemente regulares não isomorfos

Ao testarmos um par de grafos fortemente regulares não isomorfos com as mes-

mas características (v, k, i e j comum aos dois grafos), detectamos que o processo

de simulação gerava v partições igualitárias com apenas três células, e todas elas

3Para os testes, utilizamos a biblioteca de grafos fortemente regulares, disponível em [23].

69 7.2. Grafos com alto padrão de simetria

compatíveis entre si. Com isso, o grafo bipartido R tornava-se completo, com v!

emparelhamentos perfeitos (lembre-se que uma aresta {p, q} é inserida em R se e

somente se as partições ψG,p e ψH,q são compatíveis), e consequentemente o algo-

ritmo proposto um número exponencial de testes para verificar que G e H não eram

isomorfos, o que deixou o programa Mabi ineficiente.

É possível demonstrar formalmente que o algoritmo proposto é ineficiente para

grafos fortemente regulares. Seja G um grafo fortemente regular e π = ψ(2)G,p uma

partição obtida a partir de uma p-simulação. Pela Proposição 1, π possui apenas

três células e podemos argumentar que π é G-regular. A célula π[3] contém apenas

o vértice p, a célula π[2] possui os vizinhos de p e a célula π[1] contém os vértices

não adjacentes a p. A homegeneidade de π[3] com relação às outras duas células é

óbvia. Cada vértice u ∈ π[2] possui um vizinho em π[3], e pela definição de grafo

fortemente regular, u e p possuem i vizinhos em comum. Como todos os vizinhos

de p estão em π[2], logo u terá i vizinhos em π[2]. Também pela definição, cada

vértice v ∈ π[1] possui j vizinhos em π[2], pois v e p não são adjacentes, e portanto

possuem j vizinhos em comum. Como os vizinhos de p estão em π[2], cada vértice

v terá j vizinhos em π[2]. Como G é k-regular, então todo vértice u ∈ π[2] terá

k − i− 1 vizinhos em π[1] e todo v ∈ π[1] terá k − j vizinhos em π[1]. Portanto π é

G-igualitária, para todo p ∈ V (G). Pelo Teorema 3, a p-simulação se estabiliza ao

encontrar uma partição igualitária. Ao construir o grafo R, ele será completo, pois

todo par de partições ψG,p e ψG,q será compatível, o que torna o algoritmo proposto

ineficiente para grafos fortemente regulares.

A Figura 7.1 ilustra o particionamento obtido após a realização de um p-simulação

em um grafo fortemente regular. Os valores marcados nas setas representam a quan-

tidade de vizinhos que um vértice presente em uma célula possui em relação a uma

outra célula.


π[3]

π[2]π[1]

0

k

1

i

k − i− 1

j

k − j

π

Figura 7.1: Partição π obtida após uma simulação em um grafo fortemente regular.

A seguir, temos a Tabela 7.4 que mostra os resultados obtidos para pares de

grafos fortemente conexos não isomorfos, mas que possuem os mesmos valores de

v, k, i, j em ambos.

Tabela 7.4: Grafos fortemente regulares não isomorfos.

Características Nauty Mabiv = 25k = 12i = 5j = 6 0.001 28.334v = 36k = 14i = 4j = 6 0.004 4929.180

CAPÍTULO 8

Considerações Finais

Neste trabalho apresentamos conceitos básicos sobre teoria dos grafos, estudamos

o Problema do Isomorfismo de Grafos e o algoritmo proposto por McKay. Como

contribuição, apresentamos um algoritmo para o caso geral do PIG e um estudo

detalhado do algoritmo PGI.

Como visto no capítulo anterior, apesar de o algoritmo proposto não ter supe-

rado o algoritmo PGI em desempenho, houve uma contribuição válida, pois não

foi encontrado na literatura um algoritmo para o PIG baseado em emparelhamen-

tos perfeitos em grafo bipartido. Além disso, acreditamos que este algoritmo seja

de fácil paralelização, o que traria um ganho de desempenho. Na próxima seção,

apresentamos quais serão os trabalhos futuros relacionados a esta dissertação.

Capítulo 8. Considerações Finais 72

8.1 Trabalhos futuros

Em um trabalho futuro, pretendemos paralelizar este algoritmo, utilizando a seguinte

estratégia: em primeiro lugar, a simulação seria paralelizada, pois foi verificado

empiricamente que este processo demanda muito tempo de processamento. Em

segundo momento, a paralelização seria na geração de emparelhamentos perfeitos.

Outro trabalho a ser desenvolvido é paralelizar o algoritmo PGI.

Além disso, pretendemos implementar duas melhorias no algoritmo proposto,

com o objetivo de diminuir o tempo de execução: a primeira é modificar o processo de

simulação, para que uma simulação tenha como parâmetro, além do vértice pivô e a

função f , uma partição obtida em uma simulação anterior. A segunda melhoria é na

etapa de verificação do isomorfismo a partir de um emparelhamento perfeito. Se um

emparelhamento perfeitoM não corresponde a um isomorfismo ϕ, certamente haverá

um par de arestas e = {i, j} e a = {u, v} de M em que i = ϕ(j) e u 6= ϕ(v). Com

isso, podemos modificar o algoritmo que gera os emparelhamentos perfeitos, de modo

que as arestas e e a não estejam simultaneamente nos próximos emparelhamentos

perfeitos gerados.

Outras pesquisas a serem desenvolvidas é comparar o consumo de memória dos

dois algoritmos, e testá-los em sistemas com pouca memória RAM e cache inexistente

ou limitado.

Bibliografia

[1] Alon, N. e Spencer, J. (2004). The Probabilistic Method. Wiley-Interscience

series in discrete mathematics e optimization. Wiley.

[2] Arvind, V. e Torán, J. (2005). Isomorphism testing: Perspective e open problems.

Bulletin of the EATCS, 86:66–84.

[3] Babai, L., Grigoryev, D. Y., e Mount, D. M. (1982). Isomorphism of graphs

with bounded eigenvalue multiplicity. In Proceedings of the fourteenth annual

ACM symposium on Theory of computing, STOC ’82, pages 310–324, New York,

NY, USA. ACM.

[4] Babai, L. e Luks, E. M. (1983). Canonical labeling of graphs. In Proceedings

of the Fifteenth Annual ACM Symposium on Theory of Computing, STOC ’83,

pages 171–183, New York, NY, USA. ACM.

[5] Barbosa, R. M. (1975). Combinatória e Grafos. Nobel.

[6] Chen, W.-K. (1997). Graph theory e its engineering applications. Advanced

Series in Electrical e Computer Engineering. World Scientific.

Bibliografia 74

[7] Colbourn, C. J. (1981). On testing isomorphism of permutation graphs.

Networks, 11(1):13–21.

[8] Conte, D., Foggia, P., Sansone, C., e Vento, M. (2004). Thirty Years Of Graph

Matching In Pattern Recognition. International Journal of Pattern Recognition e

Artificial Intelligence.

[9] Farouk, R. M. (2011). Iris recognition based on elastic graph matching e gabor

wavelets. Computer Vision e Image Understanding, 115(8):1239–1244.

[10] Foggia, P., Sansone, C., e Vento, M. (2001). A performance comparison of five

algorithms for graph isomorphism. Proc. of the 3rd IAPR TC-15 Workshop on

Graph-based Representations in Pattern Recognition, pages 188–199.

[11] Foggia, P., Sansone, C., e Vento, M. (2004). A (sub)graph isomorphism algo-

rithm for matching large graphs. IEEETPAMI: IEEE Transactions on Pattern

Analysis e Machine Intelligence, 26.

[12] Gallian, J. (1994). Contemporary abstract algebra. D.C. Heath.

[13] Goldreich, O., Micali, S., e Wigderson, A. (1986). Proofs that yield nothing but

their validity e a methodology of cryptographic protocol design. In Proceedings

of the 27th Annual Symposium on Foundations of Computer Science, SFCS ’86,

pages 174–187, Washington, DC, USA. IEEE Computer Society.

[14] Hopcroft, J. e Karp, R. (1973). An n5/2 algorithm for maximum matchings in

bipartite graphs. SIAM Journal on Computing, 2(4):225–231.

[15] Hopcroft, J. E. e Wong, J. K. (1974). Linear time algorithm for isomorphism

of planar graphs (preliminary report). In Proceedings of the sixth annual ACM

symposium on Theory of computing, STOC ’74, pages 172–184, New York, NY,

USA. ACM.

75 Bibliografia

[16] Jenner, B., Köbler, J., McKenzie, P., e Torán, J. (2003). Completeness results

for graph isomorphism. J. Comput. Syst. Sci., 66(3):549–566.

[17] Jukna, S. (2001). Extremal Combinatorics: With Applications in Computer

Science. Springer.

[18] Köbler, J., Schöning, U., e Torán, J. (1993). The Graph Isomorphism Problem:

Its Structural Complexity. Progress in Theoretical Computer Science. Birkhäuser.

[19] Leiserson, C., Cormen, T., Rivest, R., e Stein, C. (2002). Algoritmos: teoria e

prática. Campus.

[20] Lueker, G. S. e Booth, K. S. (1979). A linear time algorithm for deciding

interval graph isomorphism. J. ACM, 26(2):183–195.

[21] Luks, E. M. (1982). Isomorphism of graphs of bounded valence can be tested

in polynomial time. Journal of Computer e System Sciences, 25(1):42 – 65.

[22] Martin, D. M. (2011). Teoria dos grafos: notas de aula. Online.

[23] McKay, B. (2013). Combinatorial data. [Online; http://cs.anu.edu.au/ bdm/-

data/graphs.html; accessado em 28-Dezembro-2013].

[24] McKay, B. e Piperno, A. (2013). nauty e traces. [Online;

http://cs.anu.edu.au/ bdm/nauty/; accessado em 28-Dezembro-2013].

[25] McKay, B. D. (1981). Practical graph isomorphism. In Congressus Nume-

rantium (10th. Manitoba Conference on Numerical Mathematics e Computing),

volume 30, pages 45–87.

[26] Miller, G. (1980). Isomorphism testing for graphs of bounded genus. In Pro-

ceedings of the twelfth annual ACM symposium on Theory of computing, STOC

’80, pages 225–235, New York, NY, USA. ACM.

Bibliografia 76

[27] Nandi, R. C. (2006). Isomorfismo de grafos aplicado à comparação de impressões

digitais. Mestrado, UFPR.

[28] Netto, P. O. B. (2006). Grafos: Teoria, modelos, algoritmos. Edgard Blucher,

4 edition.

[29] Pedarsani, P. e Grossglauser, M. (2011). On the privacy of anonymized

networks. In Proceedings of the 17th ACM SIGKDD international conference

on Knowledge discovery e data mining, KDD ’11, pages 1235–1243, New York,

NY, USA. ACM.

[30] Raymond, J. W. e Willett, P. (2002). Maximum common subgraph isomorphism

algorithms for the matching of chemical structures. Journal of Computer-Aided

Molecular Design, 16(7):521–533.

[31] Rodrigues, P. M. (2013). Emparelhamentos em grafos. [Online;

http://www.math.ist.utl.pt/ pmartins/EMF/Notas/Grafos5.pdf; accessado em

28-Dezembro-2013].

[32] Schmidt e Druffel (1976). A fast backtracking algorithm to test directed graphs

for isomorphism using distance matrices. JACM: Journal of the ACM, 23.

[33] Sipser, M. (1996). Introduction to the Theory of Computation. International

Thomson Publishing, 1st edition.

[34] Szwarcfiter, J. L. (1988). Grafos e algoritmos computacionais. Campus, Rio de

Janeiro.

[35] Torán, J. (2004). On the hardness of graph isomorphism. SIAM J. Comput.,

33(5):1093–1108.

[36] Ullmann, J. R. (1976a). An algorithm for subgraph isomorphism. JACM:

Journal of the ACM, 23.

77 Bibliografia

[37] Ullmann, J. R. (1976b). An algorithm for subgraph isomorphism. J. ACM,

23(1):31–42.

[38] Uno, T. (2001). A fast algorithm for enumerating bipartite perfect matchings.

In ISAAC, pages 367–379.

CAPÍTULO 9

Anexo

1 #pragma once

2 #i f n d e f CELULA_H_

3 #d e f i n e CELULA_H_

4

5 #inc lude <set >

6

7 us ing namespace std ;

8

9 c l a s s Ce l l {

10 pub l i c :

11 Cel l ( ) ;

12 Cel l ( i n t l a b e l ) ;

13

14 set<int > v e r t i c e s ;

15

16 i n t l a b e l ;

17

79

18 bool operator <( Ce l l c ) {

19 r e tu rn l a b e l < c . l a b e l ;

20 }

21 } ;

22

23 #e n d i f /∗ CELULA_H_ ∗/

codigo/cell.h

1

2 #i f n d e f CELULA_CPP_

3 #d e f i n e CELULA_CPP_

4

5 #inc lude " c e l l . h "

6

7 Cel l : : Ce l l ( ) {

8 l a b e l = 0 ;

9 }

10

11 Cel l : : Ce l l ( i n t l a b e l ) {

12 th i s −>l a b e l = l a b e l ;

13 }

14

15 #e n d i f

codigo/cell.cpp

1 #pragma once

2 #i f n d e f GRAPH_H_

3 #d e f i n e GRAPH_H_

4

5 #inc lude <l i s t >

6 #inc lude <iostream >

7 #inc lude <fstream>

Capítulo 9. Anexo 80

8


10

11 // Uma c l a s s e para r e p r e s e n t a r g r a f o s d i r i g i d o s

12 c l a s s Digraph {

13 protec t ed :

14 i n t n ; // numero de v e r t i c e s

15 i n t m; // numero de a r e s t a s

16

17 // Matriz de ad jacenc ia

18 i n t ∗∗ matrix ;

19

20 // Uma matriz de ad jacenc ia e s p e c i a l

21 /∗ /

22 ∗ | Adj [ u ] . end ( ) i f v i s not in u ’ s ad jacency

l i s t ,

23 ∗ M[ u ] [ v ] = <

24 ∗ | the i t e r a t o r po in t ing to v in u ’ s l i s t

o therwi se .

25 ∗ \

26 ∗/

27 l i s t <int >: : i t e r a t o r ∗∗M;

28

29 pub l i c :

30 l i s t <int > ∗ adj ;

31

32 Digraph ( i n t n) ; // Construtor

33 Digraph ( Digraph ∗G) ; // Construtor ( f a z cop ia de G)

34

35 /∗ Constro i um gra fo d i r i g i d o a p a r t i r do gra fo b i p a r t i d o balan−

36 ∗ ceado R e emparelhamento M. As a r e s t a s de M sÃ£o or i en tadas de

37 ∗ ’ baixo ’ para ’ cima ’ e as a r e s t a s de R \ M sÃ£o or i en tadas de

38 ∗ ’ cima ’ para ’ baixo ’ .

81

39 ∗/

40 ~Digraph ( ) ; // Destrutor

41

42 bool in se r t_arc ( i n t u , i n t v ) ; // I n s e r e o arco (u , v )

43 bool remove_arc ( i n t u , i n t v ) ; // Remove o arco (u , v )

44 bool ex i s t s_arc ( i n t u , i n t v ) ; // V e r i f i c a se (u , v ) e s ta

p re sen te

45 bool invert_arc ( i n t u , i n t v ) ; // Troca orientaÃ§Ã£o do arco (

u , v )

46 bool invert_path ( i n t u , const i n t ∗ parent ) ;

47

48 l i s t <int >: : i t e r a t o r remove_arc_alternative ( i n t u , i n t v ) ; //

Remove o arco (u , v )

49

50 l i s t <int >: : i t e r a t o r arc ( i n t u , i n t v ) ;

51

52 void p r i n t ( ) ; // Imprime o gra fo na t e l a

53 void read_graph (FILE ∗) ; // Le um gra fo nÃ£o d i r i g i d o de

um arqu ivo

54 void read_digraph (FILE ∗) ; // Le um gra fo d i r i g i d o de um

arqu ivo

55

56 i n t get_n ( ) ; // Retorna a quantidade de v e r t i c e s

57 i n t get_m ( ) ; // Retorna a quantidade de a r e s t a s

58

59

60 // Transpoe o gra fo ( in p lace )

61 void t ranspose ( ) ;

62

63 // Retorna uma copia do gra fo t ranspos to

64 Digraph ∗ get_transpose ( ) ;

65

66 // Retorna a matriz de a d j a c e n c i a s


67 const i n t ∗∗ adjacency_matrix ( ) ;

68 } ;

69

70 #e n d i f

codigo/digraph.h

1 #i f n d e f GRAFOS_CPP_

2 #d e f i n e GRAFOS_CPP_

3

4 #inc lude " digraph . h "



7

8 Digraph : : Digraph ( i n t n ) {

9 th i s −>n = n ;

10 adj = new l i s t <int> [ n ] ;

11 matrix = NULL;

12

13 // I n i c i a l i z a a matriz de ad jacenc ia

14 M = new l i s t <int >: : i t e r a t o r ∗ [ n ] ;

15 f o r ( i n t i = 0 ; i < n ; i ++) {

16 M[ i ] = new l i s t <int >: : i t e r a t o r [ n ] ;

17 f o r ( i n t j = 0 ; j < n ; j ++)

18 M[ i ] [ j ] = adj [ i ] . end ( ) ;

19 }

20 }

21

22 Digraph : : Digraph ( Digraph ∗G) {

23 n = G−>n ;

24


26 matrix = NULL;

27

83

28 // Aloca a matriz de ad jacenc ia e i n i c i a l i z a com "0"

29 M = new l i s t <int >: : i t e r a t o r ∗ [ n ] ;

30 f o r ( i n t i = 0 ; i < n ; i ++) {

31 M[ i ] = new l i s t <int >: : i t e r a t o r [ n ] ;

32 f o r ( i n t j = 0 ; j < n ; j ++)

33 M[ i ] [ j ] = adj [ i ] . end ( ) ;

34 }

35

36 // Copia os arcos

37 f o r ( i n t i = 0 ; i < n ; i ++)

38 f o r ( l i s t <int >: : i t e r a t o r j = G−>adj [ i ] . beg in ( ) ; j != G−>adj [ i ] .

end ( ) ; j ++) {

39 adj [ i ] . push_front (∗ j ) ;

40 M[ i ] [ ∗ j ] = adj [ i ] . beg in ( ) ; // Mantem a matriz atua l i zada

41 }

42 }

43

44 void Digraph : : t ran spose ( ) {

45 l i s t <int > ∗ oldAdj = adj ;


47

48 f o r ( i n t i = 0 ; i < n ; i ++)

49 f o r ( i n t j = 0 ; j < n ; j ++)

50 M[ i ] [ j ] = adj [ i ] . end ( ) ;

51

52 f o r ( i n t i = 0 ; i < n ; i ++)

53 f o r ( l i s t <int >: : i t e r a t o r j = oldAdj [ i ] . beg in ( ) ; j != oldAdj [ i ] .

end ( ) ; j ++) {

54 adj [ ∗ j ] . push_front ( i ) ;

55 M[ i ] [ ∗ j ] = j ;

56 }

57

58 d e l e t e [ ] oldAdj ;


59 }

60

61 Digraph : : ~ Digraph ( ) {

62 // Libera memoria

63 f o r ( i n t i = 0 ; i < n ; i ++)

64 d e l e t e [ ] M[ i ] ;

65 d e l e t e [ ] M;

66 d e l e t e [ ] adj ;

67 }

68

69 // I n s e r e o arco (u , v )

70 bool Digraph : : in se r t_arc ( i n t u , i n t v ) {

71 i f (M[ u ] [ v ] == adj [ u ] . end ( ) ) {

72 adj [ u ] . push_front ( v ) ;

73

74 // Atual iza a matriz

75 M[ u ] [ v ] = adj [ u ] . begin ( ) ;

76 r e tu rn t rue ;

77 }

78

79 r e tu rn f a l s e ;

80 }

81

82 // Muda a direcÃ£o de um arco em tempo constante

83 bool Digraph : : invert_arc ( i n t u , i n t v )

84 {

85 i f (M[ u ] [ v ] == adj [ u ] . end ( ) | | M[ v ] [ u ] != adj [ v ] . end ( ) )


87

88 adj [ u ] . e r a s e (M[ u ] [ v ] ) ;

89 M[ u ] [ v ] = adj [ u ] . end ( ) ;

90 adj [ v ] . push_front (u ) ;

91 M[ v ] [ u ] = adj [ v ] . begin ( ) ;

85

92


94 }

95

96 // Muda a direcÃ£o dos arcos em um caminho u , p [ u ] , p [ p [ u ] ] , . . .

97 bool Digraph : : invert_path ( i n t u , const i n t ∗ parent )

98 {

99 bool r e s u l t = t rue ;

100

101 whi le ( parent [ u ] != u) {

102 r e s u l t = r e s u l t && invert_arc ( parent [ u ] , u) ;

103 u = parent [ u ] ;

104 }

105

106 r e tu rn r e s u l t ;

107 }

108

109

110 // Remove o arco (u , v ) em tempo constante

111 bool Digraph : : remove_arc ( i n t u , i n t v ) {

112 i f (M[ u ] [ v ] != adj [ u ] . end ( ) ) {

113 adj [ u ] . e r a s e (M[ u ] [ v ] ) ;

114

115 // Atual iza a matriz

116 M[ u ] [ v ] = adj [ u ] . end ( ) ;


118 }

119


121 }

122

123 l i s t <int >: : i t e r a t o r Digraph : : remove_arc_alternative ( i n t u , i n t v )

124 {


125 l i s t <int >: : i t e r a t o r next_element = adj [ u ] . e r a s e (M[ u ] [ v ] ) ;

126

127 M[ u ] [ v ] = adj [ u ] . end ( ) ;

128

129 r e tu rn next_element ;

130 }

131

132 // V e r i f i c a se o arco (u , v ) per t ence ao gra fo em tempo constante

133 bool Digraph : : ex i s t s_arc ( i n t u , i n t v ) {

134 i f (M[ u ] [ v ] == adj [ u ] . end ( ) )



137 }

138

139 l i s t <int >: : i t e r a t o r Digraph : : arc ( i n t u , i n t v ) {

140 r e tu rn M[ u ] [ v ] ;

141 }

142

143 // Imprime as l i s t a s de v i z inhanca na t e l a

144 void Digraph : : p r i n t ( ) {

145 f o r ( i n t i = 0 ; i < n ; i++) {

146 cout << i << " : " ;

147

148 // Imprime pr ime i ro v i z inho de i

149 l i s t <int >: : i t e r a t o r j = adj [ i ] . beg in ( ) ;

150 i f ( j != adj [ i ] . end ( ) ) {

151 cout << " " << ∗ j ;

152

153 // Percorre o r e s t a n t e dos v i z i n h o s de i , imprimindo−os

154 f o r ( j ++; j != adj [ i ] . end ( ) ; j++)

155 cout << " , " << ∗ j ;

156 }

157

87

158 cout << endl ;

159 }

160 }

161

162 // Le o gra fo da entrada e preenche a e s t r u t u r a de dados na memoria

163 void Digraph : : read_graph (FILE ∗ entrada ) {

164 whi le ( ! f e o f ( entrada ) ) {

165 i n t u , v ;

166

167 f s c a n f ( entrada , "%d" , &u) ;

168 f s c a n f ( entrada , "%d" , &v ) ;

169

170 th i s −>inse r t_arc (u , v ) ;

171 th i s −>inse r t_arc (v , u) ;

172 }

173 }

174

175 // Le o d i g r a f o da entrada e preenche a e s t r u t u r a de dados na memoria

176 void Digraph : : read_digraph (FILE ∗ entrada ) {

177 whi le ( ! f e o f ( entrada ) ) {

178 i n t u , v ;

179

180 f s c a n f ( entrada , "%d" , &u) ;

181 f s c a n f ( entrada , "%d" , &v ) ;

182

183 th i s −>inse r t_arc (u , v ) ;

184 }

185 }

186

187 // Retorna a quantidade de v e r t i c e s

188 i n t Digraph : : get_n ( ) {

189 r e tu rn n ;

190 }


191

192 /∗∗ Retorna a quantidade de a r e s t a s

193 ∗/

194 i n t Digraph : : get_m ( ) {

195 i n t m = 0 ;

196

197 f o r ( i n t i = 0 ; i < n ; i ++) {

198 l i s t <int >: : i t e r a t o r j = adj [ i ] . beg in ( ) ;

199 l i s t <int >: : i t e r a t o r f = adj [ i ] . end ( ) ;

200 f o r ( ; j != f ; j ++)

201 m ++;

202 }

203

204 r e tu rn m;

205 }

206

207 // Retorna um novo gra fo que e o t ranspos to do grafo −ob je to

208 // I am not sure we need t h i s funct ion . . .

209 // s t r o n g l y Conn . comp may simply t ranspose the same graph G a l l a long

210 Digraph ∗ Digraph : : get_transpose ( ) {

211 Digraph ∗T = new Digraph (∗ t h i s ) ;

212

213 T−>transpose ( ) ;

214

215 r e tu rn T;

216 }

217

218 // Aloca e re torna a matriz de ad jacenc ia do gra fo

219 i n t const ∗∗ Digraph : : adjacency_matrix ( ) {

220 i f ( matrix != NULL)

221 r e tu rn ( const i n t ∗∗) matrix ;

222

223 matrix = new i n t ∗ [ n ] ;

89

224 f o r ( i n t i = 0 ; i < n ; i ++)

225 matrix [ i ] = new i n t [ n ] ;

226

227 f o r ( i n t i = 0 ; i < n ; i++)

228 f o r ( i n t j = 0 ; j < n ; j++)

229 matrix [ i ] [ j ] = 0 ;

230

231 f o r ( i n t i = 0 ; i < n ; i++)

232 f o r ( l i s t <int >: : i t e r a t o r j = adj [ i ] . beg in ( ) ; j != adj [ i ] . end ( ) ;

j++)

233 matrix [ i ] [ ∗ j ] = 1 ;

234

235 r e tu rn ( const i n t ∗∗) matrix ;

236 }

237

238 #e n d i f /∗ GRAFOS_CPP_ ∗/

codigo/digraph.cpp

1 #pragma once

2 #i f n d e f ARESTA_H_

3 #d e f i n e ARESTA_H_

4

5 s t r u c t Edge {

6 i n t u , v ;

7 } ;

8

9

10 #e n d i f /∗ ARESTA_H_ ∗/

codigo/edge.h

1 #pragma once

2 #i f n d e f ISOMORPHISM_H


3 #d e f i n e ISOMORPHISM_H

4


6 #inc lude " matching . h "

7 #inc lude " p a r t i t i o n . h "

8

9 c l a s s Isomorphism {

10 pub l i c :

11 i n t n ;

12 Digraph ∗G, ∗H;

13 P a r t i t i o n ∗∗ psiG , ∗∗ psiH ;

14

15 Isomorphism ( Digraph ∗G, Digraph ∗H) {

16 th i s −>G = G;

17 th i s −>H = H;

18 n = G−>get_n ( ) ;

19 }

20

21 ~Isomorphism ( ) {

22 f o r ( i n t p = 0 ; p < n ; p ++)

23 d e l e t e psiG [ p ] ;

24

25 f o r ( i n t q = 0 ; q < n ; q ++)

26 d e l e t e psiH [ q ] ;

27

28 d e l e t e [ ] psiG ;

29 d e l e t e [ ] psiH ;

30 }

31

32 i n t ∗ matching_based_algorithm ( ) ;

33

34 i n t ∗ get_map_from_two_discrete_partitions ( P a r t i t i o n ∗P, Pa r t i t i o n ∗Q)

;

91

35

36 /∗ Supoe |E(G) | = |E(H) | . ∗/

37 bool check_isomorphism ( const i n t ∗ permutation ) ;

38

39 /∗ Remove a r e s t a s de R que nÃ£o estao cont idas em c i r c u i t o s . ∗/

40 Edge trim_edges ( Digraph ∗R) ;

41

42 void re s t r i c t_match ing ( Matching ∗M, i n t p , i n t q ) ;

43 void re s t r i c t_compat ib i l i t y _gra ph ( Digraph ∗R, i n t p , i n t q ) ;

44 Digraph ∗ new_constrained_compatibi l ity_graph ( Digraph ∗R, i n t p , i n t

q ) ;

45

46 i n t ∗ enumerate_isomorphism_candidates ( Digraph ∗D, Matching ∗M) ;

47 } ;

48

49 #e n d i f /∗ ISOMORPHISM_H ∗/

codigo/isomorphism.h

1 #inc lude <c s t d l i b >


3 #inc lude " edge . h "

4 #inc lude " search . h "

5 #inc lude " isomorphism . h "

6 #inc lude " s imu lat ion . h "

7

8 i n t ∗ Isomorphism : : get_map_from_two_discrete_partitions ( P a r t i t i o n ∗P,

P a r t i t i o n ∗Q) {

9 i n t ∗ permutation = new i n t [ n ] ;

10

11 l i s t <Ce l l ∗ >:: i t e r a t o r i = P−>c e l l s . begin ( ) , j = Q−>c e l l s . begin ( ) ,

l a s t _ i = P−>c e l l s . end ( ) ;

12 f o r ( ; i != l a s t _ i ; i ++, j++)

13 permutation [ ∗ ( ( ∗ i )−>v e r t i c e s . begin ( ) ) ] = ∗( (∗ j )−>v e r t i c e s . begin ( ) ) ;


14

15 r e tu rn permutation ;

16

17 }

18

19 /∗ Recebe do i s g r a f o s e uma n−permutaÃ§ao . Supoe que os

20 ∗ g r a f o s r e c e b i d o s tem n v e r t i c e s e supoe que os g r a f o s

21 ∗ r e c e b i d o s possuem o mesmo nÃºmero de a r e s t a s . ∗/

22 bool Isomorphism : : check_isomorphism ( const i n t ∗ permutation ) {

23 i n t n = G−>get_n ( ) ;

24 const i n t ∗∗MH = H−>adjacency_matrix ( ) ;

25 l i s t <int > ∗ adj = G−>adj ;

26

27 f o r ( i n t u = 0 ; u < n ; u++)

28 f o r ( l i s t <int >: : i t e r a t o r v = adj [ u ] . begin ( ) ; v != adj [ u ] . end ( ) ; v

++)

29 i f ( !MH[ permutation [ u ] ] [ permutation [ ∗ v ] ] )


31


33 }

34

35 /∗ Devolve um isomorf i smo de G em H (em forma de um

36 ∗ v etor de permutaÃ§ao ) ou NULL. ∗/

37 i n t ∗ Isomorphism : : matching_based_algorithm ( ) {

38 i f (H−>get_n ( ) != G−>get_n ( ) | | H−>get_m ( ) != G−>get_m ( ) )

39 r e tu rn NULL;

40

41 psiG = new P a r t i t i o n ∗ [ n ] ;

42 psiH = new P a r t i t i o n ∗ [ n ] ;

43

44 // Calcu la a part iÃ§ao da p−simulaÃ§ao para todo p em V(G)

45 f o r ( i n t p = 0 ; p < n ; p++) {

93

46 // Faz a p−simulaÃ§ao para cada p em V(G)

47 psiG [ p ] = Simulat ion (G, p) . ge t_par t i t i on ( ) ;

48

49 // Se a part iÃ§ao obt ida e d i s c r e t a , s e ra rap ido . . .

50 i f ( psiG [ p]−> i s _ d i s c r e t e ( ) ) {

51

52 // Faz a q−simulaÃ§ao para cada q em V(H)

53 f o r ( i n t q = 0 ; q < n ; q++) {

54 psiH [ q ] = Simulat ion (H, q ) . ge t_par t i t i on ( ) ;

55

56 // Se uma part iÃ§ao obt ida e d i s c r e t a , t e s t a por isomorf i smo

57 i f ( psiH [ q]−> i s _ d i s c r e t e ( ) ) {

58 i n t ∗ permutation = get_map_from_two_discrete_partitions ( psiG [

p ] , psiH [ q ] ) ;

59

60 i f ( check_isomorphism ( permutation ) )


62

63 d e l e t e [ ] permutation ;

64 }

65 }

66

67 // Nao e x i s t e i somorf i smo ent re G e H

68 r e tu rn NULL;

69 }

70 }

71

72 // Calcu la a part iÃ§ao da q−simulaÃ§ao para todo q em V(H)

73 f o r ( i n t q = 0 ; q < n ; q++) {

74 psiH [ q ] = Simulat ion (H, q ) . ge t_par t i t i on ( ) ;

75

76 // Se a part iÃ§ao obt ida e d i s c r e t a , nao e x i s t e i somorf i smo ent re G

e H


77 i f ( psiH [ q]−> i s _ d i s c r e t e ( ) )

78 r e tu rn NULL;

79 }

80

81 // Gera gra fo R

82 Digraph ∗R = new Digraph (2 ∗ n) ;

83 f o r ( i n t p = 0 ; p < n ; p++)

84 f o r ( i n t q = 0 ; q < n ; q++)

85 i f ( psiG [ p]−>is_compat ib le ( psiH [ q ] ) )

86 R−>inse r t_arc ( q + n , p) ;

87

88 // R−>p r i n t ( ) ;

89 Matching ∗M = new Matching (n) ;

90 M−>grow_matching_in (R) ;

91 i f (M−>i s _ p e r f e c t ( ) ) {

92 i n t ∗ permutation = enumerate_isomorphism_candidates (R, M) ;

93

94 d e l e t e R;

95 d e l e t e M;

96


98 }

99

100 d e l e t e M;

101 d e l e t e R;

102

103 r e tu rn NULL;

104 }

105

106 void Isomorphism : : r e s t r i c t_match ing ( Matching ∗M, i n t p , i n t q ) {

107 const i n t ∗G_p_cell_of_vertex = psiG [ p]−>cel l_of_vertex_array ( ) ;

108 const i n t ∗H_q_cell_of_vertex = psiH [ q]−>cel l_of_vertex_array ( ) ;

109 const i n t ∗matched = M−>mapping ( ) ;

95

110

111 f o r ( i n t i = 0 ; i < n ; i++) {

112 i f ( matched [ i ] == NOONE)

113 cont inue ;

114

115 i n t j = matched [ i ] ;

116 const i n t ∗ G_i_cell_of_vertex = psiG [ i ]−>cel l_of_vertex_array ( ) ;

117 const i n t ∗ H_j_cell_of_vertex = psiH [ j ]−>cel l_of_vertex_array ( ) ;

118

119 i f ( G_p_cell_of_vertex [ i ] != H_q_cell_of_vertex [ j ] )

120 M−>set_matched ( i , NOONE) ;

121

122 i f ( G_i_cell_of_vertex [ p ] != H_j_cell_of_vertex [ q ] )

123 M−>set_matched ( i , NOONE) ;

124 }

125 }

126

127

128 /∗ p and q must be in the range 0 . . (n−1) . ∗/

129 Digraph ∗ Isomorphism : : new_constrained_compatibi l ity_graph ( Digraph ∗R,

i n t p , i n t q ) {

130 Digraph ∗S = new Digraph (2 ∗ n) ;

131 const i n t ∗G_p_cell_of_vertex = psiG [ p]−>cel l_of_vertex_array ( ) ;

132 const i n t ∗H_q_cell_of_vertex = psiH [ q]−>cel l_of_vertex_array ( ) ;

133

134 f o r ( i n t i = 0 ; i < n ; i++) {

135 const i n t ∗ G_i_cell_of_vertex = psiG [ i ]−>cel l_of_vertex_array ( ) ;

136 l i s t <int > &neighbors = R−>adj [ i ] ;

137

138 f o r ( l i s t <int >: : i t e r a t o r j = neighbors . begin ( ) ; j != neighbors . end

( ) ; j++) {

139 const i n t ∗ H_j_cell_of_vertex = psiH [ ∗ j − n]−>

cel l_of_vertex_array ( ) ;


140

141 i f ( G_p_cell_of_vertex [ i ] == H_q_cell_of_vertex [ ∗ j − n ] )

142 i f ( G_i_cell_of_vertex [ p ] == H_j_cell_of_vertex [ q ] )

143 S−>inse r t_arc ( i , ∗ j ) ;

144 }

145 }

146

147 f o r ( i n t i = 0 ; i < n ; i++) {

148 const i n t ∗ H_i_cell_of_vertex = psiH [ i ]−>cel l_of_vertex_array ( ) ;

149 l i s t <int > &neighbors = R−>adj [ i + n ] ;

150


( ) ; j++) {

152 const i n t ∗ G_j_cell_of_vertex = psiG [ ∗ j ]−>cel l_of_vertex_array ( ) ;

153

154 i f ( G_p_cell_of_vertex [ ∗ j ] == H_q_cell_of_vertex [ i ] )

155 i f ( G_j_cell_of_vertex [ p ] == H_i_cell_of_vertex [ q ] )

156 S−>inse r t_arc ( i + n , ∗ j ) ;

157 }

158 }

159

160 r e tu rn S ;

161 }

162

163 /∗ Remove a r e s t a s que nao es tao em c i r c u i t o s e r e torna a

164 ∗ Ãºltima a r e s t a que nao f o i removida . ∗/

165 Edge Isomorphism : : trim_edges ( Digraph ∗D) {

166 Edge e = {NOONE, NOONE} ;

167

168 Search S(D) ;

169 S . strongly_connected_components_algorithm ( ) ;

170 i n t const ∗ scc = S . get_scc_array ( ) ;

171

97

172 f o r ( i n t i = 0 ; i < n ; i++) {

173 l i s t <int > &neighbors = D−>adj [ i ] ;

174


( ) ; j ++)

176 i f ( s c c [ i ] != scc [ ∗ j ] ) {

177 j = D−>remove_arc_alternative ( i , ∗ j ) ;

178 i f ( j == neighbors . end ( ) )

179 break ;

180 }

181 e l s e {

182 e . u = i ;

183 e . v = ∗ j ;

184 }

185 }

186

187 r e tu rn e ;

188 }

189

190 /∗ Recebe um gra fo b i p a r t i d o balanceado R e um emp . p e r f e i t o M. ∗/

191 i n t ∗ Isomorphism : : enumerate_isomorphism_candidates ( Digraph ∗D, Matching

∗M) {

192

193 i f ( check_isomorphism (M−>mapping ( ) ) ) {

194 i n t ∗ permutation = new i n t [ n ] ;

195 const i n t ∗mapping = M−>mapping ( ) ;

196

197 f o r ( i n t i = 0 ; i < n ; i ++)

198 permutation [ i ] = mapping [ i ] ;

199


201 }

202


203 Edge e , e_prime = trim_edges (D) ;

204

205 i f ( e_prime . u == NOONE)

206 r e tu rn NULL;

207

208 /∗ Acha c i r c u i t o C. ∗/

209 Search S(D) ;

210 S . find_path ( e_prime . v , e_prime . u ) ;

211 i n t const ∗path = S . get_parent_array ( ) ;

212

213 /∗ Escolhe a a r e s t a e . ∗/

214 i f ( e_prime . u < e_prime . v )

215 e = e_prime ;

216 e l s e {

217 e . v = e_prime . u ;

218 e . u = path [ e_prime . u ] ;

219 }

220

221 Matching ∗M_prime = new Matching (M, e_prime . u , path ) ;

222

223 Digraph ∗D_plus = new_constrained_compatibi l ity_graph (D, e . u , e . v − n

) ;

224

225 r e s t r i c t_match ing (M, e . u , e . v − n) ;

226

227 M−>grow_matching_in ( D_plus ) ;

228

229 i f (M−>i s _ p e r f e c t ( ) ) {

230

231 i n t ∗ permutation = enumerate_isomorphism_candidates ( D_plus , M) ;

232

233 i f ( permutation ) {

234 d e l e t e D_plus ;

99

235 d e l e t e M_prime ;

236


238 }

239

240 }

241

242 d e l e t e D_plus ;

243

244 D−>invert_path ( e_prime . u , path ) ;

245 D−>invert_arc ( e_prime . u , e_prime . v ) ;

246

247 /∗ Remove o arco r e v e r s o de e ( po i s e f o i r e v e r t i d o ) . ∗/

248 D−>remove_arc_alternat ive ( e . v , e . u ) ;

249

250 i n t ∗ permutation = enumerate_isomorphism_candidates (D, M_prime ) ;

251

252 d e l e t e M_prime ;

253

254 i f ( permutation )


256

257 r e tu rn NULL;

258 }

codigo/isomorphism.cpp

1 #inc lude <c s t d l i b >



4 #inc lude " isomorphism . h "

5


7


8 i n t main ( i n t ac , char ∗∗av ) {

9 i n t n ;

10

11 // MABI −− matching based isomorphism

12 i f ( ac != 3) {

13 cout << " Usage : \ n\n\tmabi <graph f i l e #1> <graph f i l e #2>\n\n" ;

14 cout << " \ t \t−− the format o f a graph f i l e i s : \ n\ t \ t " ;

15 cout << "n a_1 b_1 a_2 b_2 . . . a_m b_m EOF, \ n\ t \ t " ;

16 cout << " where a_i b_i encodes an edge , and numbers\n\ t \ t " ;

17 cout << " are separated by whitespaces \n\n" ;

18

19 r e tu rn EXIT_FAILURE ;

20 }

21

22 // Entrada dos g r a f o s G e H

23 FILE ∗ graph1 = fopen ( av [ 1 ] , " r t " ) ;

24 i f ( graph1 == NULL) {

25 cout << " Could not open graph f i l e " << av [ 1 ] << endl ;


27 }

28

29 f s c a n f ( graph1 , "%d" , &n) ;

30 Digraph ∗G = new Digraph (n) ;

31 G−>read_graph ( graph1 ) ;

32 f c l o s e ( graph1 ) ;

33

34 FILE ∗ graph2 = fopen ( av [ 2 ] , " r t " ) ;

35 i f ( graph2 == NULL) {

36 cout << " Could not open graph f i l e " << av [ 2 ] << endl ;


38 }

39

40 f s c a n f ( graph2 , "%d" , &n) ;

101

41 Digraph ∗H = new Digraph (n) ;

42 H−>read_graph ( graph2 ) ;

43 f c l o s e ( graph2 ) ;

44

45 Isomorphism I (G, H) ;

46

47 i n t ∗ permutation = I . matching_based_algorithm ( ) ;

48 i f ( permutation ) {

49 f o r ( i n t i = 0 ; i < n − 1 ; i ++)

50 cout << permutation [ i ] << " " ;

51 cout << permutation [ n − 1 ] << endl ;

52 }

53

54 d e l e t e G;

55 d e l e t e H;

56

57 r e tu rn 0 ;

58 }

codigo/main.cpp

1

2 #pragma once

3 #i f n d e f MATCHING_H

4 #d e f i n e MATCHING_H

5

6 #i f n d e f NOONE

7 #d e f i n e NOONE −1

8 #e n d i f

9

10 #i f n d e f NULL

11 #d e f i n e NULL 0

12 #e n d i f

13


14 #inc lude " edge . h "

15

16 c l a s s Digraph ;

17

18 /∗ Clas se r e sponsav e l por encontrar um emparelhamento

19 ∗ p e r f e i t o num gra fo b i p a r t i d o balanceado ( possu indo

20 ∗ v e r t i c e s de 0 a ( k − 1) de um lado , e de k a (2 k −

21 ∗ 1) do outro . ∗/

22 c l a s s Matching {

23 p r i v a t e :

24 /∗ n = 2k ∗/

25 i n t k , n ;

26

27 Digraph ∗D;

28

29 /∗ Vetor com k posiÃ§oes : matched [ i ] = v e r t i c e ao qual

30 ∗ i e s ta emparelhado ou NOONE caso c o n t r a r i o . ∗/

31 i n t ∗matched ;

32

33 /∗ Vetor com 2k elementos usado para guardar

34 ∗ caminhos da busca . ∗/

35 i n t ∗ parent ;

36

37 /∗ FunÃ§ao r e c u r s i v a de busca em profundidade : a

38 ∗ busca termina quando encontrar um v e r t i c e i

39 ∗ nao saturado ( sem arco saindo ) do lado menor

40 ∗ ( i . e . com i < k ) . ∗/

41 i n t d f s _ v i s i t ( i n t i ) ;

42

43 pub l i c :

44 /∗ Supoe que o gra fo H e b ipar t ido , com v e r t i c e s

45 ∗ de 0 ate (k−1) de um dos lados . ∗/

46 Matching ( i n t k ) ;

103

47

48 Matching ( const Matching &M) ;

49

50 Matching ( Matching ∗M, i n t edge_bottom , const i n t ∗path ) ;

51

52 ~Matching ( ) ;

53

54 /∗ Encontra um emparelhamento maximo no gra fo . ∗/

55 void grow_matching_in ( Digraph ∗H) ;

56

57 /∗ V e r i f i c a se o emparelhamento e p e r f e i t o . ∗/

58 bool i s _ p e r f e c t ( ) ;

59

60 /∗ Imprime emparelhamento . ∗/

61 void p r i n t ( ) ;

62

63 /∗ Retorna mapa correspondente ao emparelhamento . ∗/

64 const i n t ∗mapping ( ) ;

65

66 /∗ Ajusta manualmente um v e r t i c e emparelhado a outro

67 ∗ ( so no v etor matched) . ∗/

68 void set_matched ( i n t i , i n t j ) ;

69 } ;

70

71

72 #e n d i f /∗ MATCHING_H ∗/

codigo/matching.h


2 #inc lude <vector>



5 #inc lude " matching . h "


6

7 Matching : : Matching ( i n t k ) {

8 D = NULL;

9 th i s −>k = k ;

10 n = 2 ∗ k ;

11 matched = new i n t [ k ] ;

12 parent = NULL;

13

14 f o r ( i n t i = 0 ; i < k ; i++)

15 matched [ i ] = NOONE;

16 }

17

18 Matching : : Matching ( const Matching &M) {

19 D = NULL;

20 k = M. k ;

21 n = M. n ;


23 parent = NULL;

24

25 f o r ( i n t i = 0 ; i < k ; i++)

26 matched [ i ] = M. matched [ i ] ;

27 }

28

29 /∗ Faz uma copia do emparelhamento M e f a z M = M ds C, onde

30 ∗ ds denota a ’ d i f e r e n c a s i m e t r i c a ’ e C e o c i r c u i t o codi−

31 ∗ f i c a d o pe lo v e r t i c e edge_bottom e pe lo caminho c o d i f i c a −

32 ∗ do na arvore de busca ’ path ’ . ∗/

33 Matching : : Matching ( Matching ∗M, i n t edge_bottom , const i n t ∗ path ) {

34 D = NULL;

35 k = M−>k ;

36 n = M−>n ;


38 parent = NULL;

105

39

40 f o r ( i n t i = 0 ; i < k ; i++)

41 matched [ i ] = M−>matched [ i ] ;

42

43 /∗ ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗ CHECK CHECK CHECK CHECK ∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗∗

∗/

44 i n t x = edge_bottom ;

45 whi le ( path [ x ] != x ) {

46 matched [ x ] = path [ x ] − k ;

47 x = path [ path [ x ] ] ;

48 }

49 }

50

51 Matching : : ~ Matching ( ) {

52 d e l e t e [ ] matched ;

53 i f ( parent != NULL)

54 d e l e t e [ ] parent ;

55 }

56

57 /∗ Funcao r e c u r s i v a de busca em profundidade .

58 ∗ Busca termina quando encontrar um v e r t i c e

59 ∗ i < k , sem arco de saÃ da . ∗/

60 i n t Matching : : d f s _ v i s i t ( i n t i ) {

61 i f ( i < k && matched [ i ] == NOONE)

62 r e tu rn i ;

63

64 l i s t <int >: : i t e r a t o r j = D−>adj [ i ] . beg in ( ) ;

65 l i s t <int >: : i t e r a t o r end = D−>adj [ i ] . end ( ) ;

66 f o r ( ; j != end ; j++)

67 i f ( parent [ ∗ j ] == NOONE) {

68 parent [ ∗ j ] = i ;

69 i n t r = d f s _ v i s i t (∗ j ) ;

70 i f ( r != NOONE)


71 r e tu rn r ;

72 }

73

74 r e tu rn NOONE;

75 }

76

77 /∗ Encontra um emparelhamento maximo no gra fo H dado . Caso o

78 ∗ emparelhamento ja tenha s ido encontrado anter iormente sobre o mesmo

79 ∗ gra fo ou sobre um supergra fo de le , ou ainda , se o emparelhamento

80 ∗ f o i c r i ado a p a r t i r de uma cop ia de outro emparelhamento

81 ∗ ( pos s iv e lmente desatua l i za do ) , e f e i t a uma v e r i f i c a c a o para

82 ∗ encontrar p o s s Ã v e i s i r r e g u l a r i d a d e s . Por exemplo , se um v e r t i c e

83 ∗ es ta emparelhado com um c e r t o v e r t i c e segundo o v etor ’ matched ’ ,

84 ∗ mas com um v e r t i c e d i f e r e n t e no gra fo H, i s s o deve s e r c o r r i g i d o

85 ∗ ( atual iando−se o v etor matched) . Caso um v e r t i c e i e s t e j a

86 ∗ emparelhado com um v e r t i c e j segundo o v etor ’ matched ’ mas nao

87 ∗ e s t e j a emparelhado com ninguem no gra fo H, entao tudo bem , desde

88 ∗ que i e j nao tenham arcos i n c i d e n t e s no gra fo . Essa v e r i f i c a c a o

89 ∗ nao e f e i t a atualmente . Tambem supoe−se que o gra fo H nao possu i

90 ∗ v e r t i c e na parte de baixo ( de 0 a ( k − 1) ) com mais de um arco

91 ∗ de saÃ da . ∗/

92 void Matching : : grow_matching_in ( Digraph ∗H) {

93 D = H;

94

95

96 f o r ( i n t i = 0 ; i < k ; i++) {

97 l i s t <int > &neighbors = D−>adj [ i ] ;

98

99 // pensar se i s s o pode o c o r r e r :

100 i f ( ne ighbors . begin ( ) != neighbors . end ( ) )

101 matched [ i ] = ∗( ne ighbors . begin ( ) ) − k ;

102

103 /∗ Se o gra fo de entrada nao t i v e r no maximo um arco saindo

107

104 ∗ de cada v e r t i c e da parte de ’ baixo ’ , entao a l i n h a acima

105 ∗ e onde corre −se o r i s c o de t e r matched [ i ] = matched [ j ]

106 ∗ com i != j . ∗/

107 }

108

109

110

111 i f ( parent == NULL)

112 parent = new i n t [ n ] ;

113

114 bool augmented ;

115

116 /∗ Guarda se um v e r t i c e de k ate n − 1 es ta saturado ou nao . ∗/

117 i n t ∗ s = new i n t [ k ] ;

118

119 f o r ( i n t i = 0 ; i < k ; i ++)

120 s [ i ] = NOONE;

121

122 f o r ( i n t i = 0 ; i < k ; i++)

123 i f ( matched [ i ] != NOONE)

124 s [ matched [ i ] ] = i ;

125

126 do {

127 augmented = f a l s e ;

128

129 f o r ( i n t i = 0 ; i < n ; i ++)

130 parent [ i ] = NOONE;

131

132 f o r ( i n t i = 0 ; i < k ; i ++) {

133 i n t j = i + k ;

134

135 i f ( s [ i ] == NOONE) {

136 parent [ j ] = j ;


137 s [ i ] = d f s _ v i s i t ( j ) ;

138 }

139 }

140

141 f o r ( i n t i = 0 ; i < k ; i ++) {

142 i f ( s [ i ] == NOONE | | matched [ s [ i ] ] == i )

143 cont inue ;

144

145 /∗ R ea l i za a inv er sao da or i en tacao dos arcos num caminho

146 ∗ aumentador de i ate s [ i ] . ∗/

147 f o r ( i n t j = s [ i ] ; parent [ j ] != j ; j = parent [ j ] ) {

148 i f ( j < k ) {

149 matched [ j ] = parent [ j ] − k ;

150 s [ matched [ j ] ] = j ;

151 }

152 D−>invert_arc ( parent [ j ] , j ) ;

153 }

154

155 augmented = true ;

156 }

157 } whi le ( augmented ) ;

158

159 d e l e t e [ ] s ;

160 }

161

162 void Matching : : p r i n t ( ) {

163 f o r ( i n t i = 0 ; i < k ; i++)

164 cout << i << " : " << matched [ i ] << endl ;

165 }

166

167 bool Matching : : i s _ p e r f e c t ( ) {

168 f o r ( i n t i = 0 ; i < k ; i++)

169 i f ( matched [ i ] == NOONE)

109


171


173 }

174

175 const i n t ∗Matching : : mapping ( ) {

176 r e tu rn ( const i n t ∗) matched ;

177 }

178

179 void Matching : : set_matched ( i n t i , i n t j ) {

180 matched [ i ] = j ;

181 }

codigo/matching.cpp

1 #pragma once

2 #i f n d e f PARTICAO_H_

3 #d e f i n e PARTICAO_H_

4

5 #inc lude " c e l l . h "

6 #inc lude <map>


8


10

11 // Clas se para armazenar dados de uma p a r t i c a o

12 c l a s s P a r t i t i o n {

13 p r i v a t e :

14 i n t n ;

15 i n t ∗ ce l l_o f_v er t ex ;

16 bool cell_of_vertex_array_up_to_date ;

17

18 pub l i c :

19 l i s t <Ce l l ∗> c e l l s ; // Guarda a l i s t a ordenada de c e l u l a s


20

21 const i n t ∗ ce l l_of_vertex_array ( ) ;

22 bool i s _ d i s c r e t e ( ) ;

23 bool i s_compat ib le ( P a r t i t i o n ∗P) ;

24 bool r e f in e_ordered_par t i t i on_us ing_ labe l s ( i n t ∗) ;

25 void p r i n t ( ) ;

26 i n t s i z e ( ) ;

27

28 P a r t i t i o n ( i n t n) ;

29 ~ P a r t i t i o n ( ) ;

30 } ;

31

32

33

34 #e n d i f /∗ PARTICAO_H_ ∗/

codigo/partition.h

1 #i f n d e f PARTICAO_CPP_

2 #d e f i n e PARTICAO_CPP_

3

4 #i f n d e f NULL

5 #d e f i n e NULL 0

6 #e n d i f

7


9 #inc lude <set >

10 #inc lude <map>


12


14

15 /∗ I n i c i a l i z a uma p a r t i c a o u n i t a r i a do conjunto { 0 , . . . , n − 1} ∗/

16 P a r t i t i o n : : P a r t i t i o n ( i n t n ) {

111

17 Cel l ∗C = new Ce l l ( 0 ) ;

18 th i s −>n = n ;

19

20 f o r ( i n t i = 0 ; i < n ; i ++)

21 C−>v e r t i c e s . i n s e r t ( i ) ;

22

23 c e l l s . push_back (C) ;

24 ce l l_o f_v er t ex = NULL;

25 cell_of_vertex_array_up_to_date = f a l s e ;

26 }

27

28 P a r t i t i o n : : ~ P a r t i t i o n ( ) {

29 i f ( c e l l_o f_v er t ex )

30 d e l e t e [ ] c e l l_o f_v er t ex ;

31

32 whi le ( ! c e l l s . empty ( ) ) {

33 Cel l ∗C = c e l l s . f r o n t ( ) ;

34 c e l l s . pop_front ( ) ;

35

36 d e l e t e C;

37 }

38 }

39

40 bool P a r t i t i o n : : i s_compat ib le ( P a r t i t i o n ∗P) {

41 i f ( c e l l s . s i z e ( ) != P−>c e l l s . s i z e ( ) )


43

44 l i s t <Ce l l ∗ >:: i t e r a t o r i , j ;

45 f o r ( i = c e l l s . begin ( ) , j = P−>c e l l s . begin ( ) ; i != c e l l s . end ( ) ; i

++, j ++) {

46 i f ( ( ∗ i )−>l a b e l != (∗ j )−>l a b e l )


48 i f ( ( ∗ i )−>v e r t i c e s . s i z e ( ) != (∗ j )−>v e r t i c e s . s i z e ( ) )



50 }

51


53 }

54

55 bool P a r t i t i o n : : i s _ d i s c r e t e ( ) {

56 r e tu rn ( c e l l s . s i z e ( ) == ( unsigned ) n ) ;

57 }

58

59 const i n t ∗ P a r t i t i o n : : ce l l_of_vertex_array ( ) {

60 i f ( c e l l_o f_v er t ex == NULL)

61 ce l l_o f_v er t ex = new i n t [ n ] ;

62

63 i f ( ! cell_of_vertex_array_up_to_date ) {

64 i n t k = 0 ;

65 f o r ( l i s t <Ce l l ∗ >:: i t e r a t o r i = c e l l s . begin ( ) ; i != c e l l s . end ( )

; i ++, k++)

66 f o r ( set<int >: : i t e r a t o r j = (∗ i )−>v e r t i c e s . begin ( ) ; j != (∗

i )−>v e r t i c e s . end ( ) ; j ++)

67 ce l l_o f_v er t ex [ ∗ j ] = k ;

68

69 cell_of_vertex_array_up_to_date = true ;

70 }

71

72 r e tu rn ( const i n t ∗) ce l l_o f_v er t ex ;

73 }

74

75 /∗ Devolve ’ t rue ’ se o re f inamento induz ido pe lo v e tor ’ l a b e l ’

76 ∗ e nao t r i v i a l e ’ f a l s e ’ caso c o n t r a r i o ∗/

77 bool P a r t i t i o n : : r e f in e_ordered_par t i t i on_us ing_ labe l s ( i n t ∗ l a b e l ) {

78 bool r e f i n e d = f a l s e ;

79 l i s t <Ce l l ∗> new_cells ;

113

80

81 f o r ( l i s t <Ce l l ∗ >:: i t e r a t o r i = c e l l s . begin ( ) ; i != c e l l s . end ( ) ; i

++) {

82 map<int , Ce l l ∗> c h i l d r e n ;

83

84 f o r ( set <int >: : i t e r a t o r j = (∗ i )−>v e r t i c e s . begin ( ) ; j != (∗ i )−>

v e r t i c e s . end ( ) ; j ++)

85 c h i l d r e n [ l a b e l [ ∗ j ] ] = NULL;

86

87 f o r ( set<int >: : i t e r a t o r j = (∗ i )−>v e r t i c e s . begin ( ) ; j != (∗ i )−>

v e r t i c e s . end ( ) ; j ++) {

88 // O operador [ ] da c l a s s e ’map ’ c r i a uma ’ Ce l l ’ se a chave

nao e s t i v e r l a

89 i f ( c h i l d r e n [ l a b e l [ ∗ j ] ] == NULL) {

90 c h i l d r e n [ l a b e l [ ∗ j ] ] = new Ce l l ( l a b e l [ ∗ j ] ) ;

91 }

92

93 c h i l d r e n [ l a b e l [ ∗ j ]]−> v e r t i c e s . i n s e r t (∗ j ) ;

94 }

95

96 i f ( c h i l d r e n . s i z e ( ) > 1)

97 r e f i n e d = true ;

98

99 d e l e t e ∗ i ;

100

101 f o r (map<int , Ce l l ∗ >:: i t e r a t o r k = c h i l d r e n . begin ( ) ; k != c h i l d r e n

. end ( ) ; k ++)

102 new_cells . push_back (k−>second ) ;

103 }

104

105 c e l l s = new_cells ;

106

107 i f ( r e f i n e d )


108 cell_of_vertex_array_up_to_date = f a l s e ;

109 r e tu rn r e f i n e d ;

110 }

111

112 // Retorna a quantidade de c e l u l a s da p a r t i c a o

113 i n t P a r t i t i o n : : s i z e ( ) {

114 r e tu rn c e l l s . s i z e ( ) ;

115 }

116

117 #e n d i f

codigo/partition.cpp

1 #pragma once

2 #i f n d e f DFS_H_

3 #d e f i n e DFS_H_

4



7

8 #i f n d e f NOONE

9 #d e f i n e NOONE −1

10 #e n d i f

11

12 c l a s s Search {

13 p r i v a t e :

14 i n t n ;

15 Digraph ∗G;

16

17 i n t component_counter ;

18

19 /∗ Vetor contendo o nÃºmero da componente fortemente

20 ∗ conexa contendo cada v e r t i c e . ∗/

21 i n t ∗ scc ;

115

22

23 /∗ Guarda arvore de busca . ∗/

24 i n t ∗ parent ;

25

26 /∗ Guarda l i s t a de v e r t i c e s por tempo de f i n a l i z a c a o . ∗/

27 l i s t <int > vert ices_sorted_by_fin ish_t ime ;

28

29 /∗ Funcao r e c u r s i v a da busca em profundidade . ∗/

30 void v i s i t ( i n t ) ;

31

32 /∗ Usada na busca por um caminho ( funcao find_path ) . ∗/

33 bool visit_u_look_for_v ( i n t u , i n t v ) ;

34

35 pub l i c :

36 /∗ Retorna um v etor c com n elementos , onde c [ i ] denota o nÃºmero

37 ∗ da componente da arvore de busca que contem o v e r t i c e i . ∗/

38 i n t const ∗ get_scc_array ( ) ;

39

40 /∗ Retorna um v etor p com n elementos , onde p [ i ] denota o v e r t i c e

41 ∗ que e pai do v e r t i c e i na arvore de busca em profundidade . ∗/

42 i n t const ∗ get_parent_array ( ) ;

43

44 Search ( Digraph ∗G) ;

45 ~ Search ( ) ;

46

47 /∗ I n i c i a l i z a parÃ¢metros da busca . Limpa a l i s t a de v e r t i c e s

48 ∗ ordenados por tempo de f i n a l i z a c a o . ∗/

49 void r e s e t ( ) ;

50

51 /∗ Executa busca em profundidade . Processa os v e r t i c e s no laco

52 ∗ p r i n c i p a l segundo a ordem dese jada . ∗/

53 void d f s ( l i s t <int> &order ) ;

54 void d f s ( ) ;


55

56 /∗ Executa o algor i tmo que encontra as componentes fortemente

57 ∗ conexas do gra fo . Estas sao armazenadas no v etor scc

58 ∗ que pode s e r acessado pe lo metodo get_scc_array ( ) . ∗/

59 void strongly_connected_components_algorithm ( ) ;

60

61 /∗ Encontra um caminho de x a y . Retorna t rue se achou caminho . ∗/

62 bool find_path ( i n t x , i n t y ) ;

63 } ;

64

65

66 #e n d i f

codigo/search.h

1 #i f n d e f DFS_CPP_

2 #d e f i n e DFS_CPP_

3


5


7

8 i n t const ∗ Search : : get_scc_array ( ) {

9 r e tu rn ( i n t const ∗) scc ;

10 }

11

12 i n t const ∗ Search : : get_parent_array ( ) {

13 r e tu rn ( i n t const ∗) parent ;

14 }

15

16 void Search : : strongly_connected_components_algorithm ( ) {

17 Digraph ∗H = new Digraph (G) ;

18 H−>transpose ( ) ;

19

117

20 Search S(H) ;

21 S . d f s ( ) ;

22

23 d f s (S . vert ices_sorted_by_fin ish_t ime ) ;

24

25 d e l e t e H;

26 }

27

28 Search : : Search ( Digraph ∗G) {

29 th i s −>G = G;

30 n = G−>get_n ( ) ;

31

32 s cc = new i n t [ n ] ;

33 parent = new i n t [ n ] ;

34 }

35

36 Search : : ~ Search ( ) {

37 d e l e t e [ ] parent ;

38 d e l e t e [ ] s c c ;

39 }

40

41 void Search : : d f s ( ) {

42 r e s e t ( ) ;

43

44 f o r ( i n t u = 0 ; u < n ; u ++)

45 i f ( parent [ u ] == NOONE) {

46 component_counter ++;

47 parent [ u ] = u ;

48 v i s i t (u) ;

49 }

50 }

51

52 void Search : : d f s ( l i s t <int > &order ) {


53 r e s e t ( ) ;

54

55 f o r ( l i s t <int >: : i t e r a t o r u = order . begin ( ) ; u != order . end ( ) ; u ++)

56 i f ( parent [ ∗ u ] == NOONE) {

57 component_counter ++;

58 parent [ ∗ u ] = ∗u ;

59 v i s i t (∗u) ;

60 }

61 }

62

63 void Search : : v i s i t ( i n t u ) {

64 l i s t <int > &neighbors = G−>adj [ u ] ;

65

66 s cc [ u ] = component_counter ;

67 f o r ( l i s t <int >: : i t e r a t o r v = neighbors . begin ( ) ; v != neighbors . end

( ) ; v ++) {

68 i f ( parent [ ∗ v ] == NOONE) {

69 parent [ ∗ v ] = u ;

70 v i s i t (∗ v ) ;

71 }

72 }

73

74 vert ices_sorted_by_fin ish_t ime . push_front (u ) ;

75 }

76

77 void Search : : r e s e t ( ) {

78 f o r ( i n t i = 0 ; i < n ; i++) {

79 parent [ i ] = NOONE;

80 s cc [ i ] = NOONE;

81 }

82

83 component_counter = 0 ;

84 vert ices_sorted_by_fin ish_t ime . c l e a r ( ) ;

119

85 }

86

87 bool Search : : find_path ( i n t x , i n t y ) {

88 r e s e t ( ) ;

89

90 parent [ x ] = x ;

91 r e tu rn visit_u_look_for_v (x , y ) ;

92 }

93

94 bool Search : : visit_u_look_for_v ( i n t u , i n t v ) {

95 i f (u == v )


97

98 l i s t <int > &neighbors = G−>adj [ u ] ;

99

100 f o r ( l i s t <int >: : i t e r a t o r z = neighbors . begin ( ) ; z != neighbors . end

( ) ; z ++) {

101 i f ( parent [ ∗ z ] == NOONE) {

102 parent [ ∗ z ] = u ;

103 i f ( visit_u_look_for_v (∗ z , v ) )


105 }

106 }

107


109 }

110

111 #e n d i f

codigo/search.cpp

1 #pragma once

2 #i f n d e f SIMULATION_H

3 #d e f i n e SIMULATION_H


4



7

8

9 c l a s s S imulat ion {

10 pub l i c :

11 Simulat ion ( Digraph ∗G, i n t seed ) ;

12 v i r t u a l ~ S imulat ion ( ) ;

13

14 P a r t i t i o n ∗ get_par t i t i on ( ) ;

15

16 p r i v a t e :

17 Digraph ∗graph ;

18 P a r t i t i o n ∗ p a r t i t i o n ;

19 i n t seed ;

20 i n t n , n_squared ;

21

22 i n t labe l_ funct ion ( mu l t i s e t<int >) ;

23 } ;

24

25 #e n d i f /∗ SIMULATION_H ∗/

codigo/simulation.h

1 #inc lude <set >

2 #inc lude " s imu lat ion . h "

3

4 i n t S imulat ion : : l abe l_ funct ion ( mu l t i s e t<int> M) {

5 i n t sum = 0 ;

6

7 f o r ( mu l t i s e t<int >: : i t e r a t o r i = M. begin ( ) ; i != M. end ( ) ; i ++)

8 sum += ∗ i ;

9

121

10 sum %= n_squared ;

11

12 r e tu rn sum ;

13 }

14

15 Simulat ion : : S imulat ion ( Digraph ∗G, i n t s ) {

16 graph = G;

17 seed = s ;

18 n = G−>get_n ( ) ;

19 n_squared = n ∗ n ;

20

21 i n t ∗ o ld_ labe l = new i n t [ n ] , ∗ l a b e l = new i n t [ n ] ;

22

23 // I n i c i a l i z a todos os r o t u l o s com 0 e o r o t u l o de ’ seed ’ com 1

24 f o r ( i n t i = 0 ; i < n ; i++)

25 o ld_ labe l [ i ] = 0 ;

26 o ld_ labe l [ seed ] = 1 ;

27

28 // Cria uma p a r t i c a o ordenada u n i t a r i a contendo nÃºmeros de 1 a n

29 P a r t i t i o n ∗P = new P a r t i t i o n (n ) ;

30

31 // Ref ina a p a r t i c a o ordenada P de acordo com os r o t u l o s i n i c i a i s

32 P−>re f in e_ordered_par t i t i on_us ing_ labe l s ( o ld_ labe l ) ;

33

34 f o r ( bool s t a b i l i z e d = f a l s e ; ! s t a b i l i z e d ; ) {

35 s t a b i l i z e d = true ;

36 f o r ( i n t i = 0 ; i < n ; i ++) {

37 mult i s e t<int > neighborhood ;

38 neighborhood . i n s e r t ( o ld_ labe l [ i ] ) ;

39 l i s t <int> &neighbors = G−>adj [ i ] ;

40

41 f o r ( l i s t <int >: : i t e r a t o r j = neighbors . begin ( ) ; j !=

neighbors . end ( ) ; j ++)


42 neighborhood . i n s e r t ( o ld_ labe l [ ∗ j ] ) ;

43 l a b e l [ i ] = labe l_ funct ion ( neighborhood ) ;

44 }

45

46 // Ref ina a p a r t i c a o ordenada P de acordo com os novos r o t u l o s

47 s t a b i l i z e d = ! ( P−>re f in e_ordered_par t i t i on_us ing_ labe l s ( l a b e l ) )

;

48

49 i n t ∗tmp = old_ labe l ;

50 o ld_ labe l = l a b e l ;

51 l a b e l = tmp ;

52 }

53

54 d e l e t e [ ] o ld_ labe l ;

55 d e l e t e [ ] l a b e l ;

56

57 p a r t i t i o n = P;

58 }

59

60

61 Simulat ion : : ~ S imulat ion ( ) {

62 /∗ Ver porque es ta assim , e pq e ’ v i r t u a l ’ . . . ∗/

63 }

64

65 P a r t i t i o n ∗ S imulat ion : : ge t_par t i t i on ( ) {

66 r e tu rn p a r t i t i o n ;

67 }

codigo/simulation.cpp

Documents

Um Algoritmo para o Problema do Isomorﬁsmo de Grafosposcomp.ufabc.edu.br/images/uploaded_files/dissertacoesDefendidas/... · No Capítulo 3, é apresentado o Problema do Isomorﬁsmo