X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Edge search number
para grafos com muitas simetrias
R. T. Paulino, R. P. Paes Leme,
T. S. Pereira, C. M. Justel
Instituto Militar de Engenharia
Departamento de Engenharia de Sistemas
Praça General Tibúrcio 80
CEP 22290-270 - Rio de Janeiro - RJ
e-mail: {rtpaulino,rpleme,tspereira,cjustel }@ime.eb.br
RESUMO
Neste trabalho apresentamos um algoritmo para resolver o problema edge search number.
O problema em questão consiste em determinar o menor número de guardas necessários para
capturar um fugitivo que se movimenta pelas arestas de um grafo G. O problema edge search
number é NP-Completo. Nosso algoritmo é baseado na idéia do algoritmo Bucket-Dijkstra,
fazendo uma busca num espaço de estados associado ao problema. Além disso, propomos podar
a busca utilizando o grafo de grupos de automorsmos associado ao grafo de estados. Foram
realizados testes para avaliar o resultado da implementação do algoritmo proposto em grafos
completos e grafos gride.
PALAVRAS-CHAVE:
grafos, algoritmos, problemas de busca. Teoria de Grafos.
ABSTRACT
We give an algorithm for the Edge-Search Number problem. It consists on nding the minimum number of searchers to capture a fugitive tha moves along the edges of a graph G. It
is known to be NP-Complete. The algorithm is based on a Bucket Dijkstra search through a
state space. We propose pruning the search using information from the graphs group of automorphism. To determine the conditions in which it provides a performance gain, we have made
experiments on complete and grid-like graphs.
KEYWORDS:
XXXIX SBPO
graphs, algorithms, edge search number. Graph Theory.
[2577]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
1 Introdução
O problema de determinar edge search number de um grafo G, esn(G), foi introduzido por
Parsons em 1976. Supor que o grafo representa um sistema de túneis no qual um fugitivo
encontra-se escondido. O intruso movimenta-se livremente pelas arestas do grafo contaminandoas. Uma equipe de guardas percorre o túnel com a missão de encurralar o fugitivo, capturá-lo e
limpar todo o grafo. O problema consiste em determinar o menor número de guardas que garanta
a limpeza de todas as arestas do grafo. Um plano de busca é uma seqüência de operações
utilizando no máximo k > 0 guardas, que garante a limpeza total de um grafo inicialmente
contaminado. O edge search number de um grafo G, esn(G), é o menor número de guardas
utilizado por um plano de busca de G. Chamamos de plano de busca ótimo ao plano de busca
que utiliza esn(G) guardas para limpar todas as arestas de G. O problema de determinar o edge
+
search number é NP-completo para grafos em geral ([MHG 88]) e grafos planares com vértices
+
de grau máximo igual a 3 ([PHH 00]). No entanto pode ser resolvido em tempo linear para
árvores ([MHG+ 88]). A determinação do plano de busca ótimo para árvores pode ser obtida
em tempo linear ([PHH+ 00]). Em [KJ06] é apresentado um algoritmo para determinar o valor
do edge search number e do plano de busca ótimo para árvores binárias cheias, a partir de uma
adaptação das idéias propostas em [EST94]. Em [PHH+ 00] é tratado o problema para algumas
subfamilias de grafos cordais (grafos split, grafos de intervalo e grafos k -star like com k xo)
obtendo algoritmos ecientes. Uma referência recente sobre problemas de busca incluindo o
problema edge search number é [Als04].
O objetivo deste trabalho é apresentar um algoritmo exato para calcular o valor de edge
search number de grafos de tamanho limitado. Será tratado o caso particular de grafo de entrada apresentando forte simetria mostrando uma otimização do algoritmo neste caso. Os testes
realizados para grafos completos e grafos gride mostram a melhora obtida.
Na Seção 2 é apresentada a denição do problema. A Seção 3 traz a abordagem do problema
apresentado na seção anterior. A Seção 4 introduz um algoritmo exato para resolver o problema
edge search number. Na Seção 5 é apresentada uma melhora do algoritmo proposto na Seção 4.
A Seção 6 traz os resultados da implementação dos algoritmos para os grafos completos e gride.
Finalmente, a Seção 7 traz as conclusões do trabalho e as propostas de continuação do mesmo.
A terminologia de grafos usada nas seções a seguir é similar à denida em [Die00] e [Szw88].
2 Denição do problema
O problema da perseguição e evasão foi proposto por Parsons [Par76]. Considere uma rede de
túneis interconectados por onde escapa um fugitivo. O problema consiste em, usando o menor
número de guardas possível, criar uma estratégia de busca nessa rede de túneis de forma que o
fugitivo seja sempre capturado, não importa o quão inteligente sua estratêgia de fuga seja. Esse
problema tem uma série de variantes, que diferem basicamente em uma das seguintes naturezas:
(i) modelagem do cenário onde ocorre a fuga, (ii) o modo como o fugitivo e os guardas se movem
e (iii) a visão que os guardas têm do fugitivo. O cenário onde acontece a fuga poder ser contínuo
ou discreto. O tipo de movimento que os guardas e o fugitivo adotam pode ser contínuo ou
discreto. No caso contínuo os guardas e o fugitivo apresentam velocidades que podem ser iguais
ou diferentes. No caso discreto podemos considerar que a cada clock, os guardas e o fugitivo se
movimentam discreta e simultaneamente. Uma abordagem interessante é considerar o fugitivo
com velocidade innita, isso garante que ele realmente terá que ser cercado por guardas para
XXXIX SBPO
[2578]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
ser capturado. Um bom modelo para o fugitivo com velocidade innita é o agente tóxico. Ao
invés de um fugitivo e guardas, considere que uma região foi infectada por um agente tóxico,
e temos que limpá-la. Temos que ir limpando aos poucos, tendo cuidado para que não haja
recontaminação. O interessante dessa abordagem é que o agente tóxico está simultaneamente
em todos os lugares ainda não limpos, e ela se espalha instantaneamente se for "deixada uma
fresta". Voltando à abordagem do fugitivo e do guarda, o agente tóxico pode ser interpretado
como todos os possíveis lugares para o fugitivo estar. Dependendo do tipo de cenário, a visão
dos guardas pode ser considerada de maneira diferente. No modelo contínuo, podemos assumir
um modelo geométrico de visibilidade, considerando o cone de visão de cada guarda e como as
paredes e quinas obstruem a visão. No modelo discreto, temos três possibilidades: (a) o guarda
onisciente: que sabe exatamente onde o fugitivo está - ele só tem que caçá-lo de forma eciente,
(b) a visibilidade local, onde o guarda só consegue enxergar os vértices adjacentes a ele e (c) o
guarda cego, em que o guarda só consegue capturar o fugitivo quando ele está na mesma posição
que ele. Neste trabalho, vamos adotar o modelo discreto e consideraremos o pior caso dos demais
aspectos: o guarda cego e o fugitivo possui velocidade innita (equivalente ao agente tóxico).
3 Descrição da solução
Trataremos o problema descrito na seção anterior como um jogo denido num grafo. O objetivo
é, partindo de um estado onde todas as arestas do grafo estão contaminadas, chegar a um estado
em que todas as arestas do grafo estejam limpas, utilizando o menor número possível de guardas.
O menor número de guardas nessa situação é conhecido como edge search number do grafo. E
o plano de busca que permite atingir o estado nal com o menor número de guardas é o plano
de busca ótimo. Consideramos um grafo não direcionado conexo G = (V, E). Para cada aresta
associaremos um rótulo que assume dois valores possíveis: limpa ou contaminada. Um vértice
do grafo é dito limpo se todas as arestas nele incidentes estão limpas, contaminado se todas as
arestas incidentes estão contaminadas e parcialmente limpo caso contrário. Serão utilizados
k guardas para limpar o grafo. A cada instante de tempo podemos ter no máximo k guardas no
grafo. Se um guarda está alocado em um vértice do grafo, dizemos que ele está ocupado, caso
contrário, dizemos que ele está livre. Para cada guarda ocupado, associamos o vértice onde ele
está localizado. Quando um vértice está ocupado por um guarda, dizemos que ele está vigiado.
Chamamos de estado a um conjunto de rótulos que podem ser limpo ou contaminado para
cada uma das arestas, e a localização dos guardas ocupados. Um estado aceitável é aquele
em que todos os vértices parcialmente limpos estão vigiados. Note que isso reete nosso modelo
do agente tóxico. Os vértices parcialmente limpos são aqueles que têm potencial de dispersar o
agente tóxico das arestas contaminadas para as arestas limpas.
3.1
Movimentos dos guardas
A partir de um estado serão executados movimentos dos guardas. Existem três tipos de movimentos possíveis para os guardas:
P (Place) - colocar um guarda que estava livre em um vértice;
R (Remove) - remover um guarda de um vértice;
M (Move) - mover um guarda ao longo de uma aresta.
O movimento M pode limpar uma aresta. Digamos que um guarda se movimenta do vértice u
para o vértice v (onde u, v ∈ V ). A aresta (u, v) ∈ E é considerada limpa caso:
1. exista outro guarda em u,
XXXIX SBPO
[2579]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
2. todas as arestas incidentes em u, com possível exceção de (u, v), já estavam limpas.
Os movimentos R e M podem causar recontaminação. Se, após um movimento, chegarmos em
um estado não-aceitável, ocorre um movimento automático chamado recontaminação que leva
o jogo novamente a um estado aceitável. Se existe um caminho da aresta (u1 , u2 ) limpa para a
aresta (uk−1 , uk ) contaminada sem guardas nos vértices u2 , u3 , . . . , uk−1 então o agente tóxico
vai se espalhar por todas as arestas (ui , ui+1 ) para 1 ≤ i ≤ k − 1. Note que toda a propagação de
contaminante entre duas arestas ocorre através de um vértice com as seguintes características:
• parcialmente limpo
• não vigiado
Em [BS91] e [LaP93] foi mostrado que se existe um plano de busca ótimo com k guardas para o
grafo G, então também existe um plano de busca ótimo para G que não admite recontaminação
ainda com k guardas. Este plano de busca é considerado uma estratégia monótona. Vale ainda
comentar que os movimentos P e R parecem estranhos do ponto de vista da perseguição de um
fugitivo. O guarda está desaparecendo em um vértice do grafo e aparecendo em seguida em outro
vértice, como se ele tivesse tomado um helicóptero de um vértice para o outro. Note que, como
o grafo é conexo, podemos traduzir um desaparecimento de u e um reaparecimento em v como o
guarda caminhando calmamente de u para v enquanto os demais guardas permanecem parados.
Assim, a disponibilidade de um helicóptero não torna o problema mais fácil ou mais difícil.
3.2
Estados
O jogo é composto de um tabuleiro (que no nosso caso é representado pelo grafo) que pode
assumir vários estados diferentes. De fato, cada movimento dos guardas (P, M ou R) leva o
tabuleiro de um estado para outro. Como vimos, os estados são representados pelos rótulos
das arestas, indicando se estas estão limpas ou contaminadas, e a posição dos guardas. No
estado inicial do jogo, todas as arestas estão contaminadas e todos os guardas estão livres.
Chamamos esse estado de s0 . Veremos, que a menos de uma equivalência, podemos considerar
os estados compostos exclusivamente dos rótulos das arestas. Dado um estado s, denimos o
0
estado padrão associado a s, digamos s como o estado obtido através das seguintes regras:
1. os rótulos das arestas são mantidos os mesmos,
2. os guardas dos vértices completamente limpos ou completamente contaminados são retirados,
3. é mantido um e somente um guarda nos vértices parcialmente limpos.
Note que este é o número mínimo de guardas para manter a conguração das arestas e o estado
ainda ser considerado aceitável. Dizemos ainda que dois estados s1 e s2 (denotamos s1 ∼ s2 )
são equivalentes quando têm o mesmo estado padrão associada. Não é difícil de observar que
s1 e s2 são equivalentes se e somente se têm os mesmos rótulos nas arestas. Assim, se S é
o conjunto de possíveis estados aceitáveis, denimos o conjunto dos estados reduzidos como
S
S0 = ∼
. Pode-se obter S 0 a partir de S , simplesmente identicando os estados equivalentes.
Assim, os elementos de S 0 podem ser identicados unicamente pelos rótulos das arestas.
4 Algoritmo proposto
O problema edge search number é NP-completo para grafos em geral. Propomos uma solução
para este problema que determina o menor número de guardas necessários para limpar as arestas
de um grafo conexo e um plano de busca ótimo. O algoritmo a seguir, permite determinar a
solução do problema em tempo razoável para grafos de tamanho limitado. Na Seção 5 será
apresentada uma melhora deste algoritmo para grafos que apresentam forte simetria.
XXXIX SBPO
[2580]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Seja G = (V (G), E(G)) o grafo para o qual deseja-se obter o valor de edge search number. A
notação que será utilizada no algoritmo proposto é a seguinte:
• V (G) é o conjunto de vértices, n = |V (G)|.
• E(G) é o conjunto de arestas, m = |E(G)|.
• Dado v ∈ V (G), Adj[v] = {u ∈ V (G)|(v, u) ∈ E(G)}.
• grau(v) = |Adj[v]|.
• c(v) é o número de arestas contaminadas incidentes em v (0 ≤ c(v) ≤ grau(v)).
• v ∈ V (G) está limpo se, e somente se, c(v) = 0. Dizemos que v é do tipo l.
• v ∈ V (G) está contaminado, se e somente se, c(v) = grau(v). Dizemos que v é do tipo c.
• v ∈ V (G) está parcialmente limpo, se e somente se, 0 < c(v) < grau(v). Dizemos que v é do
tipo pl.
• Se v ∈ V (G) está contaminado e c(v) = grau(v) = 1, dizemos que v é do tipo c1 .
• Se v ∈ V (G) está contaminado e c(v) = grau(v) > 1, dizemos que v é do tipo cn .
• Se v ∈ V (G) está parcialmente limpo e c(v) = 1, dizemos que v é do tipo pl1 .
• Se v ∈ V (G) está parcialmente limpo e c(v) > 1, dizemos que v é do tipo pln .
• Seja s um estado, denimos g(s) = |{v ∈ V (G) : v parcialmente limpo}| que é o número de
guardas necessários para manter essa situação aceitável.
Devido a existência de um plano de busca ótimo que não permite recontaminação, podemos
analisar unicamente os movimentos dos guardas que não levam à recontaminação.
Dado um grafo G = (V (G), E(G)) com m = |E(G)|, representaremos um estado s (de agora
em diante, estados serão sempre considerados estados reduzidos) por uma string de tamanho m
dada por s = a1 a2 ...am onde ai ∈ {L, C} representando o estado s onde a i-ésima aresta está
limpa quando ai = L e contaminada caso contrário.
Consideremos um movimento para limpar uma aresta como composto de três partes: (i) alguns
guardas são colocados no grafo, se necessário. (ii) um guarda se move ao longo de uma aresta
necessariamente limpando-a e (iii) são retirados os guardas necessários para se voltar a um estado
padrão.
Em [LaP93] foi mostrado que toda estratégia de busca pode ser descrita utilizando unicamente
movimentos como aquele descrito acima. Assim, a limpeza das aresta de um grafo G com m
arestas pode ser realizada em exatamente m movimentos para limpar arestas. A cada movimento
uma aresta é limpa.
Considere uma seqüência de movimentos que limpa o grafo, passando pelos estados:
s0 → s1 → s2 → ... → sm
Para determinar o número de guardas necessários para executar a seqüência anterior, observamos
que para fazer a transição si → si+1 evitando a recontaminação são necessários g(si ) guardas,
enquanto se executa a limpeza de uma aresta adicional. O número de guardas necessários para
executar a limpeza da aresta, depende das extremidades da mesma.
pl 1 c 1
pl
n
cn
pl 1
0
0
0
0
c1
0
1
1
1
pl
0
1
1
1
0
1
1
2
n
cn
Figura 1: Custo de transição τ
XXXIX SBPO
[2581]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Baseado na tabela da Figura 1, denimos uma função τ que, dado um estado s e uma aresta
e = (a, b) ∈ E(G), determina o número de guardas "extras" necessários para limpar a aresta e
a partir do estado s. Assim, o cálculo de τ (s, e) é feito avaliando a situação das extremidades da
aresta e (c1 , cn , pl1 ou pln ) conforme a tabela.
Se um dos vértices nas extremidade da aresta que vai ser limpa é do tipo pl1 , basta mover o
guarda que está lá para a outra extremidade. Não precisamos gastar nenhum guarda adicional.
Se um dos vértices é do tipo c1 , basta colocar lá um guarda adicional e movê-lo para a outra
extremidade. Analogamente, sendo uma das extremidades do tipo pln , podemos colocar um
guarda lá e movê-lo para a outra extremidade. O guarda que já está no vértice do tipo pln é
usado para guardar aquela extremidade para evitar recontaminação. Por m, se os dois são do
tipo cn , então só resta a opção de colocar ambos em uma mesma extremidada da aresta e mandar
um deles se mover ao longo desta.
SG
CCC
LCC
CLC
LLC
LCL
CCL
G
CLL
LLL
Figura 2: Grafo de estados de um grafo com |E(G)| = 3
Dado um grafo G = (V (G), E(G)), seja V (SG ) o conjunto de possíveis estados (reduzidos)
de G. Assim, |V (SG )| = 2m . Seja SG o grafo direcionado com pesos nas arestas cujo conjunto
de vértices é dados por V (SG ). As arestas de SG são denidas da seguinte forma:
(s1 , s2 ) ∈ E(SG ) ⇐⇒ ∃e ∈ E(G) | s1 [e] = c, s2 [e] = l e s1 [e0 ] = s2 [e0 ], ∀e0 ∈ E(G), e0 6= e
ou seja, se s2 pode ser obtido a partir de s1 limpando unicamente uma aresta. A Figura 2 mostra
um exemplo de um grafo G contendo 3 arestas e o correspondente grafo de estados SG . Denimos
os pesos das arestas da seguinte forma: Se e ∈ E(G) é a aresta que, após limpa, leva o estado s1
ao estado s2 :
w(s1 , s2 ) = g(s1 ) + τ (s1 , e).
Assim, uma estratégia de limpeza no grafo G corresponde a um caminho em SG dado por:
s0 s1 s2 ... sm ,
onde s0 = CCC...C e sm = LLL...L. O número de guardas necessários para executar essa
estratégia de limpeza s0 → ... → sm é dado por:
custo(s0 → ... → sm ) = max w(si−1 , si ).
i=1...m
Portanto, para achar o edge search number de G, basta aplicar um algoritmo de caminhos
mínimos (Dijkstra, por exemplo) no grafo direcionado SG . A única diferença em relação a
um algoritmo de Dijkstra clássico é que, quando atualizamos o custo de um vértice, ao invés
de usarmos soma, usamos a operação de máximo. O Algoritmo 1 apresenta a descrição em
pseudocódigo do algoritmo proposto.
XXXIX SBPO
[2582]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Algoritmo 1: Dijkstra em SG
Entrada: G Saída: esn(G)
P [u] = ∞ para todo u
cor[u] = 0 para todo u
FilaPrioridades.inserir(s0 = CCC...C )
cor[s0 ] = 1
P [s0 ] = 0
Enquanto (FilaPrioridades.estaVazia() 6= falso)
v = FilaPrioridades.retirarMinimo()
Se v = LLL...L
retorna P [v]
cor[v] = 2
Para todo u ∈ Adj[v], com cor[u] 6= 2
Se max{P [v], w[v][u]} < P [u]
P [u] = max{P [v], w[v][u]}
pai[u] = v
Se cor[u] = 0
cor[u] = 1
FilaPrioridades.inserir(u)
A saída do Algoritmo 1 é dada pelo valor do edge search number do grafo G, esn(G) = P [sm ]
e o vetor de dimensão M , pai, contendo a seqüência de estados que determina a limpeza de todas
as arestas do grafo G. A complexidade de pior caso do algoritmo de Dijkstra é O((N +M )·log N )
onde N é o número de vértices do grafo direcionado SG . Como o grafo sobre o qual estamos
aplicando Dijkstra é SG , que tem N = 2m e M = m·2m−1 , então temos complexidade do pior caso
da ordem O(m2 · 2m ). Como todos os pesos das arestas são inteiros e limitados por n = |V (G)|,
não precisamos usar uma heap no algoritmo de Dijkstra, podemos usar uma seqüência de buckets,
fazendo assim a inserção e a remoção em O(1), dessa forma, Dijkstra passa a ter complexidade
O(N + M ) = O(m · 2m )
5 Melhora do algoritmo proposto
O algoritmo proposto na Seção 4 utiliza o conceito de estado padrão para evitar redundâncias.
Agora observamos que, se o grafo para o qual deseja-se determinar o valor de edge search number apresentar forte simetria, podemos otimizar o algoritmo anterior utilizando uma rotina que
determina estados correspondentes a situações equivalentes ao respeito da limpeza de uma aresta.
LCCCCC
CLCCCC
CCLCCC
CCCLCC
CCCCLC
CCCCL
Figura 3: Alguns estados e suas classes de equivalência
O exemplo da Figura 3 apresenta 6 situações de limpeza de arestas correspondente a estados
padrão para a árvore binária cheia contendo 7 vértices com uma única aresta limpa. Desses seis
XXXIX SBPO
[2583]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
casos podemos observar que existem dois grupos que podem ser considerados estados isomorfos:
os dois primeiros e os 4 últimos. Em termos de limpeza de uma única aresta, os estados agrupados
serão tratados da mesma maneira pelo algoritmo da seção anterior. Propomos então utilizar o
algoritmo apresentado por McKay para determinar automorsmos e dessa forma reduzir o número
de operações realizadas pelo algoritmo anterior. O algoritmo de McKay apresenta complexidade
do pior caso exponencial, mas nos casos práticos foi mostrado ser eciente [McK81]. O programa
Nauty (No AUTomorphism, Yes?) [McK] implementa uma solução do problema isomorsmo de
grafos com vértices coloridos e será utilizado para melhorar o desempenho do nosso algoritmo.
Para utilizar automorsmos do grafo G que representem a mesma situação de arestas limpas
introduziremos a idéia de grafo colorido associado ao estado s do grafo G. Dado um estado s
correspondente ao grafo G, dene-se o grafo Gs da maneira seguinte:
Subdividem-se todas as arestas do grafo G pela adição de um vértice de grau dois em cada aresta.
Colorem-se todos os vértices do grafo obtido da maneira seguinte: a cor preto é utilizada para
colorir todos os vértices originais do grafo G, a cor cinza para todos os vértices adicionados nas
arestas contaminadas de acordo com o estado s e a cor branca para todos os vértices adicionados
nas arestas limpas de acordo com o estado s. Assim, podemos denir que dois estados s1 e s2
do grafo G contendo o mesmo número de arestas limpas e arestas contaminadas são equivalentes
se os grafos coloridos Gs1 e Gs2 são isomorfos. Dessa forma podemos determinar se dados dois
estados eles correspondem a situações equivalentes de limpeza de arestas do grafo G (como no
exemplo da Figura 3).
Um automorsmo σ : V (G) −→ V (G) leva estados s em estados equivalentes sσ usando a
seguinte regra: a aresta (u, v) está limpa em s se, e somente se, (σu, σv) está limpa em sσ . Assim,
um vértice v tem no estado s o mesmo tipo (pl1 , pln , c1 , cn , ...) que o vértice σv tem no estado
sσ . Note que a permutação dos vértices de Gs1 que leva a Gs2 , restrita aos vértices originais do
grafo G gera uma permutação σ tal que s1 σ = s2 . Assim, se s0 = s0 → ... → sm = s1 é um
caminho de s0 até s1 , então: s0 = sσ0 = (s0 )σ → ... → (sm )σ = (s1 )σ = s2 é um caminho de
mesmo custo até s2 . Portanto, o custo de s1 e o custo de s2 são os mesmos.
Desejamos alterar ligeiramente o algoritmo de Dijkstra para evitar percorrer caminhos equivalentes aos já percorridos. Assim evitamos que o algoritmo analise um caminho s0 → ... → sm
se já foi percorrido um caminho s0 0 → ... → s0 m onde si e s0 i são equivalentes para todo i.
Considere uma rotina projeção, que a cada estado asssocie um estado equivalente tal que,
se s1 e s2 sejam equivalentes, então a projeção de s1 é igual à projeção de s2 . Dessa forma,
basta colorir e atribuir custos aos estados projetados. Assim, se encontramos um estado s1 que
é equivalente a um estado já encontrado s2 então, temos 3 possibilidades:
• A cor de s2 é 2, então todos os caminhos de menor custo até s2 já foram encontrados.
Podemos descartar s1 pois seu custo atual é maior ou igual ao de s2 .
• A cor de s2 é 1 e o custo de s2 é menor que o de s1 . Nesse caso, podemos descartar s1 ,
pois um caminho melhor já foi encontrado até um vértice equivalente.
• A cor de s2 é 1 e o custo de s2 é maior que o de s1 . Nesse caso, abandonamos s2 , e
adicionamos s1 na la de prioridades.
Considere que, dado um grafo colorido G, temos uma função λG , que permuta os vértices de
G de tal forma que, se G1 é isomorfo a G2 , então λ−1
G2 ◦λG1 nos dá esse isomorsmo. A geração de
λG a partir de G é implementada no pacote nauty desenvolvido por McKay ([McK]). Usando-a,
podemos construir a projeção de estados, seguindo o algoritmo projeção apresentado a seguir:
XXXIX SBPO
[2584]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
Projeção de um estado:
Entrada: (G, s) Saída: s0
Calcular o grafo Gs
Chamar nauty para calcular λGs
Construir Gp usando λGs
Chamar nauty para calcular λGp
−1
Calcular ϕ = λ−1
Gs ◦ λGp ◦ λG
Para toda (u, v) ∈ E(G) faça:
s0 (u, v) = s(ϕ(u), ϕ(v))
Retornar s0
πG
G
0
λG
2
1
3
4
4
5
6
λG p
6
5
0
Gp
5
3
1
2
6
2
0
3
1
4
LCLLCL
5
0
7
11
1
8
3
9 12
4
5
s
G
2
10
6
7
λG s
11
6
8
3
2
10
9 12
4
0
1
π Gs
Figura 4: Construção do estado projetado de s
A permutação λGs renomeia os vértices do grafo Gs gerando um grafo πGs , que é o mesmo
para todos os membros de uma mesma classe de equivalencia. Note que λGs restrito aos vértices
pretos de Gs dene uma permutação dos vértices de G que gera um grafo isomorfo GP . Claramente, os grafos πGs e Gp são independentes do representante de sua classe de equivalência,
logo λ−1
Gp ◦ λG também independe do representante. Essa aplicação leva (u, v) ∈ E(G) em uma
aresta de πGs . Assim, o estado padrão pode ser obtido simplesmente analisando a cor do vértice
s
s
intermediário a imagem de (u, v) por λ−1
Gp ◦ λG em πG . Como λG é um isomorsmo, essa cor é
s
a mesma do vértice intermediário entre (ϕ(u), ϕ(v)) em G , que é exatamente s(ϕ(u), ϕ(v)).
O procedimento de projeção de McKay é exponencial (o problema de determinar isomorsmos de subgrafos é NP-Completo), no entanto tem-se conseguido implementações que funcionam
bem na prática para esse problema. Além disso, existem algoritmos polinomiais para determinadas classes de grafos (árvores, grafos planares e grafos com grau máximo menor ou igual a 3)
([KHC04]). Assim, ao resolver o problema do edge search number para uma classe especíca de
grafos, podemos substituir o procedimento que mapeia o grafo G na permutação λG por uma
implementação especíca que seja mais eciente para aquela classe de grafos.
Assim, o algoritmo da Seção 4 pode ser modicado para obter o menor número de guardas
necessários para limpar todas as arestas do grafo G evitando automorsmos. Note que a variável
"cor"
armazena agora a cor dos estados projetados. E há uma função P 0 que armazena os
XXXIX SBPO
[2585]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
custos dos estados projetados (estados equivalentes têm, obrigatoriamente, o mesmo custo). O
Algoritmo 2 apresenta a descrição em pseudocódigo da nova versão do algoritmo.
Algoritmo 2: Dijkstra em SG evitando automorsmos
Entrada: G Saída: esn(G)
P [u] = ∞ para todo u
cor[u] = 0 para todo u
FilaPrioridades.inserir(s0 = CCC...C )
cor[s0 ] = 1
P 0 [s0 ] = P [s0 ] = 0
Enquanto (FilaPrioridades.estaVazia() 6= falso)
v = FilaPrioridades.retirarMinimo()
Se v = LLL...L
retorna P [v]
0
v = projeção(G, v)
cor[v 0 ] = 2
Para todo u ∈ Adj[v]
u0 = projeção(G, u)
Se cor[u0 ] 6= 2
Se cor[u0 ] = 0
P 0 [u0 ] = P [u] = max{P [v], w[v][u]}
FilaPrioridades.inserir(u)
pai[u] = v
cor[u0 ] = 1
Senão
Se max{P [v], w[v][u]} < P 0 [u0 ]
P 0 [u0 ] = P [u] = max{P [v], w[v][u]}
pai[u] = v
FilaPrioridades.inserir(u)
6 Resultados
Nas tabelas a seguir comparamos as implementações dos Algoritmos 1 e 2, tanto em termos de
quantidade de loops do algoritmo de Dijkstra como em tempo de execução.
O código foi implementado na linguagem C++ e os resultados são apresentados em termos de
número de loops, (aqui, loops do algoritmo de Dijkstra representa execuções do laço "Enquanto"
mais externo) e em termos do tempo de execução - medido em milisegundos. Os testes foram
realizado em um computador AMD 64bits de 3.2GHz com 1GB de memória RAM. As variáveis
"loopi " e "tempoi " representam o número de loops e tempo de execução do Algoritmo i = 1, 2.
A primeira tabela mostra os resultados obtidos para os testes com grafos completos de até 10
vértices. A segunda tabela mostra os testes para grafos gride (ver [Die00] capítulo 12 para a
denição) com no máximo 30 vértices. As linhas com um traço indicam valores não calculados.
XXXIX SBPO
[2586]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
|E(Kn )|
3
6
10
15
21
28
36
45
n
3
4
5
6
7
8
9
10
p
2
2
2
2
2
3
3
3
3
4
4
4
5
q
3
4
5
6
7
4
5
6
7
5
6
7
6
|E(Gpq )|
7
10
13
16
19
17
22
27
32
31
38
45
49
loops1
3
28
261
4819
130562
loops1
18
24
30
36
42
113
133
157
181
1453
1896
2388
20995
tempo1
0
0
0.02
0.97
48.42
tempo1
0
0
0
0.01
0.01
0.04
0.07
0.12
0.18
1.44
2.72
4.67
53.39
loops2
3
6
14
51
141
712
5453
78858
loops2
9
13
17
21
25
69
91
115
139
416
547
686
6304
tempo2
0
0
0
0.05
0.24
2.24
27.31
592.21
tempo2
0
0
0.01
0.02
0.03
0.08
0.18
0.37
0.69
2
4.13
8.43
97.81
No caso dos grafos completos Kn , o Algoritmo 2 teve melhores resultados. No caso dos grafos
gride Gpq mesmo tendo menos loops, a identicação dos automorsmos tornou o processo mais
custoso para o Algoritmo 2 - aumentando o tempo de execução em relação ao Algoritmo 1. Devemos lembrar, no entanto, que o algoritmo de McKay usado não levava em conta características
especiais dos grafos gride - o fato de serem planares, por exemplo.
7 Conclusão
Neste trabalho foi apresentado um algoritmo exato para determinar o valor do parâmetro edge
para grafos. Dado um grafo, o algoritmo proposto procura um caminho mínimo
num grafo de estados correspondente ao grafo de entrada. Uma otimização do algoritmo anterior
para o caso de grafos de entrada apresentando simetrias foi introduzida. Nesse caso, foi utilizado
o algoritmo proposto por McKay para identicar estados isomorfos e dessa forma reduzir os
tempos de execução do algoritmo que determina o edge search number.
search number
Os algoritmos propostos não apresentam complexidade do pior caso polinomial, os testes
realizados com o algoritmo otimizado mostram-se promissores para os grafos testados (completos
com no máximo 10 vértices e gride com no máximo 30 vértices) em vista da melhora de tempo
de execução, quando comparados à versão do algoritmo que não evita isomorsmos.
Propomos como trabalhos futuros fazer novos testes do algoritmo otimizado em outras classes
de grafos com simetrias para vericar se introduzir uma rotina para detectar estados isomorfos no
XXXIX SBPO
[2587]
X X X I X SBPO
28 a 31/08/07 Fortaleza, CE
A Pesquisa Operacional e o Desenvolvimento Sustentável
grafo de estados melhora o tempo de execução do mesmo. E analisar outros tipos de algoritmos
para detectar isomorsmos para classes particulares de grafos (por exemplo planares).
Referências
[Als04]
Alspach. Searching and sweeping graphs: A brief survey.
Technical Report, Depart-
ment of Mathematics and Statistics, University of Regina, Canada
, 2004.
[BS91]
Bienstock and Seymour. Monotonicity in graph searching.
12:239245, 1991.
[Die00]
Diestel.
[EST94]
Ellis, Sudborough, and Turner. The vertex separation and search number of a graph.
Information and Computation, 113:5079, 1994.
[KHC04]
Graph Theory
Journal of Algorithms
,
. Springer-Verlag, 2000.
Kukluk, Holder, and Cook. Algorithm and experiments in testing planar.
, pages 313356, 2004.
Journal
of Graph Algorithms and Applications
[KJ06]
[LaP93]
Kawasaki and Justel. Determinação de edge search number para árvores binárias
cheias. Anales del XIII Congreso Latino-Iberoamericano de Investigación Operativa.
Montevideo : Facultad de Ingenieria - Universidad de la Republica, pages 16, 2006.
LaPaugh. Recontamination does not help to search a graph.
, 40:224245, 1993.
Journal of the Associ-
ation for Computing Machinery
. disponível em cs.anu.edu.au/bdm/nauty/nug.pdf.
[McK]
McKay.
[McK81]
McKay. Practical graph isomorphism.
nauty User's Guide
, 30:4587, 1981.
Congressus Numerantium
[MHG+ 88] Megiddo, Hakimi, Garey, Johnson, and Papadimitriou. The complexity of searching
a graph. Journal of the Association for Computing Machinery, 35:1844, 1988.
[Par76]
Parsons. Pursuit-evasion in a graph.
Verlag, pages 426441, 1976.
Theory and Applications of Graphs, Springer
[PHH+ 00] Peng, Ho, Hsu, Ko, and Tang. Graph searching on some subclasses of chordal graphs.
Algorithmica, 27:395426, 2000.
[Szw88]
XXXIX SBPO
Szwarcter.
. Editora Campus, 1988.
Grafos e algoritmos computacionais
[2588]