ads:
INSTITUTO MILITAR DE ENGENHARIA
SIMONE KIMIHE KAWASAKI DE OLIVEIRA
ALGORITMOS DEDICADOS PARA CÁLCULO DE
VERTEX SEPARATION / LAYOUT ÓTIMO E
EDGE SEARCH NUMBER / PLANO DE BUSCA ÓTIMO
EM ÁRVORES BINÁRIAS CHEIAS
Dissertação de Mestrado apresentada ao Curso de
Mestrado em Sistemas e Computação do Instituto Militar
de Engenharia, como requisito parcial para a obtenção do
título de Mestre em Ciências em Sistemas e Computação.
Orientadora: Prof
a
. Claudia Marcela Justel – D. Sc.
Rio de Janeiro
2006
ads:
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
2
c2006
INSTITUTO MILITAR DE ENGENHARIA
Praça General Tibúrcio, 80 – Praia Vermelha
Rio de Janeiro - RJ CEP: 22290-270
Este exemplar é de propriedade do Instituto Militar de Engenharia, que poderá incluí-lo em base
de dados, armazenar em computador, microfilmar ou adotar qualquer forma de arquivamento.
É permitida a menção, reprodução parcial ou integral e a transmissão entre bibliotecas deste
trabalho, sem modificação de seu texto, em qualquer meio que esteja ou venha a ser fixado, para
pesquisa acadêmica, comentários e citações, desde que sem finalidade comercial e que seja feita a
referência bibliográfica completa.
Os conceitos expressos neste trabalho são de responsabilidade do(s) autor(es) e do(s)
orientador(es).
005.1 Oliveira, Simone Kimihe Kawasaki
048 Algoritmos dedicados para cálculo de Vertex Separation / Layout Ótimo e
Edge Search Number / Plano de Busca Ótimo em Árvores Binárias Cheias /
Simone Kimihe Kawasaki de Oliveira. – Rio de Janeiro : Instituto Militar de
Engenharia, 2006.
138p.: il., graf., tab.
Dissertação (mestrado) – Instituto Militar de Engenharia – Rio de Janeiro,
2006.
1. Algoritmos. 2. Grafos. I. Institulo Militar de Engenharia. II. Título.
CDD 005.1
ads:
3
INSTITUTO MILITAR DE ENGENHARIA
SIMONE KIMIHE KAWASAKI DE OLIVEIRA
ALGORITMOS DEDICADOS PARA CÁLCULO DE VERTEX
SEPARATION / LAYOUT ÓTIMO E EDGE SEARCH NUMBER / PLANO
DE BUSCA ÓTIMO EM ÁRVORES BINÁRIAS CHEIAS
Dissertação de Mestrado apresentada ao Curso de Mestrado em Sistemas e Computação
do Instituto Militar de Engenharia, como requisito parcial para a obtenção do título de Mestre
em Ciências em Sistemas e Computação.
Orientadora: Prof
a
. Claudia Marcela Justel – D. Sc.
Aprovada em 17 de fevereiro de 2006 pela seguinte Banca Examinadora:
_______________________________________________________________
Prof
a
. Claudia Marcela Justel – D. Sc. do IME - Presidente
_______________________________________________________________
Prof. Jayme Luiz Szwarcfiter – Ph.D. do NCE, COPPE/UFRJ
_______________________________________________________________
Prof
a
. Lilian Markenzon – D.Sc. do NCE/UFRJ
_______________________________________________________________
Prof
a
. Nair Maria Maia de Abreu – D.Sc. do COPPE/UFRJ
Rio de Janeiro
2006
4
À Deus, minha verdadeira fonte de força e direção.
Aos meus pais, Raquel e Isamu e minhas irmãs que sempre
acreditaram em mim.
Ao meu querido marido Marcus e ao meu amado filhinho
Lucas que me inspiraram a cada dia.
5
AGRADECIMENTOS
À Prof
a
. Claudia Marcela Justel pela eficiente orientação, pela compreensão, incentivo e
amizade. Agradeço também a todos os professores que possibilitaram a realização deste curso.
Aos meus familiares, ao meu marido Marcus que foi sempre meu principal incentivador,
e ao meu filhinho Lucas, que também merece esta titulação pelo belo comportamento ao
frequentar todas as aulas do curso ainda em meu ventre.
Aos amigos que fiz dentro e fora do IME.
Ao Departamento de Engenharia de Sistemas do Instituto Militar de Engenharia pela
oportunidade de ampliar meus conhecimentos.
À CAPES, pela concessão de bolsas de estudos para a pesquisa no Brasil.
À todos aqueles que, direta ou indiretamente, contribuíram para que este trabalho fosse
concluido.
6
“ Ao único Deus, nosso Salvador, mediante Jesus Cristo,
Senhor nosso, glória, majestade, império e soberania,
antes de todas as eras, e agora, e por todos os séculos.
Amém.”
JUDAS 24
7
SUMÁRIO
LISTA DE ILUSTRAÇÕES ................................................................................................ 10
LISTA DE TABELAS ......................................................................................................... 13
1. INTRODUÇÃO .............................................................................................. 16
1.1. Apresentação .................................................................................................... 16
1.2. Conceitos básicos ............................................................................................. 18
2. VERTEX SEPARATION E EDGE SEARCH NUMBER........................... 20
2.1. Introdução ........................................................................................................ 20
2.2. Vertex separation.............................................................................................. 20
2.2.1. Histórico, complexidade e aplicações................................................................ 20
2.2.2. Definição do problema...................................................................................... 22
2.3. Edge search number.......................................................................................... 25
2.3.1. Histórico, complexidade e aplicações................................................................ 25
2.3.2. Definição do problema...................................................................................... 26
2.4. Complexidade................................................................................................... 30
2.5. Relação entre vertex separation e edge search number ...................................... 31
3. VERTEX SEPARATION E LAYOUT ÓTIMO PARA ÁRVORES.......... 36
3.1. Introdução ........................................................................................................ 36
3.2. Vertex separation.............................................................................................. 36
3.2.1. Caracterização recursiva do vertex separation das subárvores de uma árvore .... 37
3.2.2. Cálculo do vertex separation de uma árvore ...................................................... 39
3.2.2.1. Criticalidade de um vértice ............................................................................... 39
3.2.2.2. Sequenciamento dos vértices............................................................................. 42
3.2.2.3. Algoritmo de Ellis............................................................................................. 46
3.3. Layout ótimo .................................................................................................... 49
3.3.1. Árvores simples, partes de uma árvore.............................................................. 49
3.3.2. Layouts extensíveis à esquerda e à direita, coarse layout................................... 51
3.3.3. Determinação de um layout ótimo a partir do coarse layout .............................. 57
8
3.3.4. Construção de um coarse layout........................................................................ 58
3.3.5. Algoritmo de Skodinis ...................................................................................... 60
4. EDGE SEARCH NUMBER E PLANO DE BUSCA ÓTIMO PARA
ÁRVORES ...................................................................................................... 64
4.1. Introdução ........................................................................................................ 64
4.2. Solução de Meggido para árvores ..................................................................... 64
4.2.1. Conceitos iniciais.............................................................................................. 65
4.2.2. Algoritmo de Meggido para calcular o edge search number .............................. 67
4.2.3. Algoritmo de Meggido para determinar um plano de busca ótimo..................... 76
4.3. Solução de Ellis para árvores ............................................................................ 80
4.3.1. Transformação 2-expansão, layout padrão de um grafo..................................... 80
4.3.2. Algoritmo de Ellis para calcular o edge search number baseado no vertex
separation da 2-expansão .................................................................................. 89
4.3.3. Algoritmo de Ellis para determinar um plano de busca ótimo baseado em um
layout ótimo da 2-expansão............................................................................... 90
5. VERTEX SEPARATION E LAYOUT ÓTIMO PARA ÁRVORES
BINÁRIAS CHEIAS....................................................................................... 94
5.1. Introdução ........................................................................................................ 94
5.2. Vertex separation.............................................................................................. 94
5.2.1. Algoritmo proposto........................................................................................... 94
5.2.2. Determinação do valor do vertex separation em função da altura da árvore binária
cheia................................................................................................................. 98
5.3. Layout ótimo .................................................................................................. 100
5.3.1. Conceitos iniciais............................................................................................ 101
5.3.2. Algoritmo proposto......................................................................................... 106
6. EDGE SEARCH NUMBER E PLANO DE BUSCA ÓTIMO PARA
ÁRVORES BINÁRIAS CHEIAS................................................................. 109
6.1. Introdução ...................................................................................................... 109
6.2. Edge search number........................................................................................ 109
6.2.1. Algoritmo proposto......................................................................................... 109
9
6.2.2. Determinação do edge search number em função do vertex separation............ 112
6.3. Plano de busca ótimo ...................................................................................... 114
6.3.1. Algoritmo proposto......................................................................................... 114
7. CONCLUSÃO............................................................................................... 120
7.1. Trabalhos futuros............................................................................................ 122
8. REFERÊNCIAS BIBLIOGRÁFICAS......................................................... 123
9. APÊNDICES................................................................................................. 126
9.1. APÊNDICE 1: implementações de algoritmos estudados para árvores em geral e
árvores binárias cheias .................................................................................... 127
9.1.1. Introdução ...................................................................................................... 127
9.1.2. Implementações em árvores: vertex separation, layout ótimo, edge search number
....................................................................................................................... 128
9.1.2.1. Dados de entrada e saída................................................................................. 128
9.1.2.2. Verificação do layout ótimo............................................................................ 131
9.1.2.3. Classes implementadas ................................................................................... 132
9.1.3. Implementações em árvores binárias cheias .................................................... 133
9.1.3.1. Vertex separation e edge search number.......................................................... 133
9.1.3.1.1. Dados de entrada e saída................................................................................. 134
9.1.3.1.2. Classes implementadas ................................................................................... 135
9.1.3.2. Layout ótimo e plano de busca ótimo.............................................................. 136
9.1.3.2.1. Dados de entrada e saída................................................................................. 136
9.1.3.2.2. Classes implementadas ................................................................................... 138
10
LISTA DE ILUSTRAÇÕES
FIG. 2.1 Dois layouts, L e L’, para o grafo K
3,3
............................................................ 23
FIG. 2.2 Conjuntos Esq
L
(3) e Dir
L
(3) do layout L da FIG. 2.1.................................... 23
FIG. 2.3 Para o layout L da FIG. 2.1 são apresentados os layouts parciais L
i
e os
conjuntos A
L
(i) de vértices ativos para 1 i 6............................................. 24
FIG. 2.4 Limpeza da aresta (D,C) do grafo da FIG. 2.1. ............................................. 27
FIG. 2.5 Recontaminação da aresta (F,C) do grafo da FIG. 2.1.................................... 28
FIG. 2.6 Exemplo da árvore T1 para o Teorema 2.1, onde esn(T1) = vs(T1). ............... 33
FIG. 2.7 Exemplo da árvore T2 para o Teorema 2.1, onde esn(T2) = vs(T2). ............... 34
FIG. 2.8 Exemplo de uma árvore T3 para o Teorema 2.1 onde esn(T3) = vs(T3) + 2.... 34
FIG. 2.9 Plano de busca com 6 guardas gerado pelo Algoritmo 2.1 para o grafo
da FIG. 2.1.................................................................................................... 35
FIG. 3.1 Cálculo do vertex separation de dois layouts da árvore T............................... 37
FIG. 3.2 Subárvores induzidas por x............................................................................ 38
FIG. 3.3 Vértice x induz três subárvores, T’
i
, de T tais que vs(T’
i
) = 2, 1 i 3. ......... 39
FIG. 3.4 Criticalidade do vértice u em T...................................................................... 40
FIG. 3.5 Árvore T possui 2 vértices 1-crítico, logo vs(T) = 2. ...................................... 41
FIG. 3.6 Significado das seqüências das raízes de duas árvores................................... 43
FIG. 3.7 Aplicação da técnica de sequenciamento numa árvore T................................ 44
FIG. 3.8 Aplicação da técnica de sequenciamento numa árvore T................................ 45
FIG. 3.9 Execução do Algoritmo 3.1 para cálculo do vertex separation....................... 48
FIG. 3.10 (a) um layout extensível à esquerda que não é extensível à direita, (b) um
layout extensível à direita que não é extensível à esquerda, (c) um layout que
não é extensível à esquerda e nem extensível à direita................................... 52
FIG. 3.11 (a) Um layout esparso de T, (b) um layout que não é esparso....................... 53
FIG. 3.12 Determinação dos layouts extensíveis à esquerda e à direita de duas árvores
utilizando o Lema 3.6.................................................................................... 55
FIG. 3.13 Determinação do layout esparso da árvore T utilizando o Lema 3.8............... 56
FIG. 3.14 Árvore T e os coarse layouts de cada subárvore de T..................................... 63
FIG. 4.1. Ramos de uma árvore T................................................................................. 65
FIG. 4.2 Árvores genéricas dos tipos H, E, I e M. ....................................................... 67
11
FIG. 4.3 Caso 1 da rotina fusão................................................................................... 71
FIG. 4.4 Caso 2 da rotina fusão................................................................................... 71
FIG. 4.5 Caso 3 da rotina fusão................................................................................... 72
FIG. 4.6 Caso 4 da rotina fusão................................................................................... 72
FIG. 4.7 Caso 5 da rotina fusão para: (a) T
1
tipo I e T
2
tipo E, (b) T
1
e T
2
tipo I, (c) T
1
tipo M e T
2
tipoH. ......................................................................................... 74
FIG. 4.8 Caso 6 da rotina fusão
.
.................................................................................. 74
FIG. 4.9 Caso 7 da rotina fusão: (a) quando sn’ < sn
1
e (b) quando sn’ = sn
1.
.............. 75
FIG. 4.10 Resultado do Algoritmo 4.1 em uma árvore T de esn(T) = 2.......................... 76
FIG. 4.11 Resultado do Algoritmo 4.1 em uma árvore T de esn(T) = 3.......................... 76
FIG. 4.12 Algoritmo 4.1 com função fusão_1 encontrando path = (B,B)....................... 78
FIG. 4.13 Algoritmo 4.1 com função fusão_1 encontrando path = (A,A). ..................... 78
FIG. 4.14 Árvore 2-expansão de T ................................................................................ 81
FIG. 4.15 Três layouts padrão para o grafo G e dois layouts não padrão para G. ........... 81
FIG. 4.16 Possíveis posições dos vértices adicionados a e b em relação aos vértices
originais x e y, tal que, de #1 a #5 b precede a, e de #6 a #10 a precede b...... 83
FIG. 4.17 Algoritmo 4.2 determina plano de busca que utiliza 3 guardas, no entanto
quantidade ótima é esn(G’) = 2 guardas, portanto plano de busca encontrado
não é ótimo. .................................................................................................. 87
FIG. 4.18 Algoritmo 4.2 determina plano de busca que utiliza 2 guardas, portanto plano
de busca encontrado é ótimo pois a quantidade ótima é esn(G’) = 2 guardas. 88
FIG. 4.19 Esquema para cálculo do edge search number de uma árvore qualquer.......... 89
FIG. 4.20 Aplicação do Algoritmo 4.3 na árvore T da FIG. 4.14, onde esn(T) = 2......... 90
FIG. 4.21 Modelo para determinar um plano de busca ótimo para uma árvore qualquer.91
FIG. 4.22 Execução do Algoritmo 4.4 para árvore T da FIG. 4.14................................. 93
FIG. 5.1 Árvores binárias cheias de alturas h = 0, 1, 2 e 3, todas com raiz A e com as
seqüências de cada vértice............................................................................. 95
FIG. 5.2 Execução do Algoritmo 5.2 para uma árvore binária cheia T
3
de altura 3....... 97
FIG. 5.3 Árvores binárias cheias de alturas h e h’= h-2........................................... 100
FIG. 5.4 Esquema da execução do Algoritmo 3.2 para a árvore da FIG. 5.1(d).......... 102
FIG. 5.5 Transformação de T
h’
em T
h
........................................................................ 105
FIG. 5.6 Layout ótimo para a árvore T
3
da FIG. 5.2 (d)............................................. 108
12
FIG. 6.1 Execução do Algoritmo 6.1 para uma árvore 2-expansão 2-T
2
de uma árvore
binária cheia T
2
de altura 2.......................................................................... 111
FIG. 6.2 Ramos em u
1
, filho da raiz de T
h
. ................................................................ 114
FIG. 6.3 Plano de busca com 2 guardas gerado pelo Algoritmo 6.2 ........................... 118
FIG. 9.1 Cálculo de um layout ótimo (com verificação) para a árvore da FIG. 3.9(c). 130
FIG. 9.2 Cálculo do vertex separation para a árvore da FIG. 3.9(c). .......................... 131
FIG. 9.3 Cálculo do vertex separation para árvores binárias cheias desde
altura 11 até 29............................................................................................ 134
FIG. 9.4 Cálculo do edge search number para árvores binárias cheias desde
altura 1 até 19. ............................................................................................ 135
FIG. 9.5 Determinação de um plano de busca ótimo para a árvore da FIG. 5.1(c)...... 137
FIG. 9.6 Determinação de um layout ótimo (com verificação) para a árvore da
FIG. 5.1(c).................................................................................................. 137
13
LISTA DE TABELAS
TAB. 1.1 Quadro com as complexidades dos problemas estudados......................... 17
TAB. 2.1 Relação do vertex separation com outros problemas em grafos ............... 22
TAB. 2.2 Um plano de busca para o grafo da FIG. 2.1 que utiliza 5 guardas........... 29
TAB. 4.1 Plano de busca ótimo para a árvore da FIG. 4.13..................................... 80
TAB. 6.1 Quantidade de guardas utilizados no plano de busca ótimo da FIG. 6.3. 119
TAB. 7.1 Soluções encontradas na literatura para árvores..................................... 120
TAB. 7.2 Soluções construídas para as árvores binárias cheias. ............................ 121
TAB. 7.3 Relação do vertex separation com outros problemas para
árvores binárias cheias........................................................................... 122
TAB. 9.1 Algoritmos implementados para árvores................................................ 128
TAB. 9.2 Resumo das classes implementadas....................................................... 133
TAB. 9.3 Algoritmos implementados para árvores binárias cheias. ....................... 133
TAB. 9.4 Resumo das classes implementadas....................................................... 135
TAB. 9.5 Resumo das classes implementadas....................................................... 138
14
RESUMO
Um layout linear L é a numeração dos vértices de um grafo. Dado um layout linear L,
o vertex separation de G = (V, E) com relação a L, vs
L
(G), é a máxima quantidade de vértices
que encontram-se à esquerda de um vértice qualquer, e que possuem alguma aresta incidente à
direita deste vértice. O vertex separation de G, vs(G), consiste em encontrar o menor valor
possível de vs
L
(G) considerando todos os layouts L de G. O layout que efetiviza o mínimo é
chamado de layout ótimo.
O edge search number de um grafo G, esn(G), envolve encontrar a menor quantidade
de guardas necessária para capturar um fugitivo móvel que encontra-se escondido em uma
aresta de G. Um plano de busca ótimo é uma seqüência de movimentações de guardas que
utiliza esn(G) guardas para capturar o fugitivo.
Vertex separation, layout ótimo, edge search number e plano de busca ótimo são
problemas NP-completos em grafos. No entanto, todos estes problemas possuem algoritmos
de tempo polinomial para árvores.
O principais resultados deste trabalho são quatro algoritmos que foram adaptados a partir
dos seus algoritmos lineares em árvores para o caso particular das árvores binárias cheias.
Esta dissertação também apresenta e prova dois novos teoremas. O primeiro deles mostra
que o vertex separation de uma árvore binária cheia T
h
depende de sua altura h, ou seja, vs(T
h
)
= (h+1)/2. Para as árvores binárias cheias, o segundo teorema melhora o resultado para
grafos obtido por Ellis em 1994, onde vs(G)
esn(G) vs(G) + 2. Este novo teorema
determina que o edge search number de uma árvore binária cheia T
h
é igual ao seu valor de
vertex separation mais 1, mais precisamente, esn(T
h
) = vs(T
h
) + 1.
15
ABSTRACT
A linear layout L is a labeling of the vertices of a graph. Given a linear layout L, the
vertex separation of G = (V,E) with respect to L, vs
L
(G), is the maximum number of vertices
to the left of a vertex that are adjacent to vertices to the right of that vertex. The vertex
separation of G, vs(G), consists of finding the minimum vs
L
(G) value considering all of G
layouts. The layout that determines this minimum is called optimal layout.
The edge search number of a graph G, esn(G), involves finding the minimum number of
guards required to capture a mobile fugitive hiding in an edge of G. An optimal search plan is
a sequence of guards movements that uses esn(G) guards to capture the fugitive.
Vertex separation, optimal layout, edge search number and optimal search plan are NP-
complete problems on general graphs. However all of these problems have polynomial-time
algorithms for trees.
The main results of this work are four algorithms that are a refined version of these trees
linear time algorithms specific for the particular case of full binary trees.
This dissertation also presents and proves two new theorems. The first one shows that vertex
separation of a full binary tree T
h
depends on its height h, more precisely, vs(T
h
) = (h+1)/2.
For full binary trees the second theorem improves the graphs result obtained by Ellis in 1994
where vs(G) esn(G) vs(G) + 2. This new theorem says that edge search number of a full
binary tree T
h
is equal its vertex separation plus 1, more precisely, esn(T
h
) = vs(T
h
) + 1.
16
1. INTRODUÇÃO
1.1. APRESENTAÇÃO
O problema de layout em grafos tem como objetivo identificar uma ordenação linear dos
vértices, ou um layout dos vértices do grafo, de forma a otimizar uma certa função ou custo do
grafo (DÍAZ et all., 2002).
O problema de busca em grafos foi inicialmente proposto por Parsons 1976 e 1978
(MEGIDDO et all., 1988). Neste tipo de problema, um grafo representa um sistema de túneis
onde todas as arestas estão contaminadas. O objetivo é encontrar o número mínimo de guardas
com os quais é possível construir uma seqüência de movimentos que limpe (ou visite) todas as
arestas do grafo simultaneamente.
Esta dissertação concentra seus estudos em dois problemas da teoria de grafos. O
primeiro deles, vertex separation, é um problema de layout em grafos. O segundo problema,
edge search number, classifica-se como um problema de busca em grafos. Além do problema
de cálculo do vertex separation, vs, pode-se também identificar, dentre todos layouts possíveis
de um grafo, aquele que determina o valor do vertex separation, denominado layout ótimo do
grafo. Da mesma forma, o problema de calcular o parâmetro edge search number de um
grafo, esn, está associado ao subproblema de determinar um plano de busca (seqüência de
movimentos) que utilize esn guardas para pesquisar ou limpar todo o grafo, a esse plano de
busca denomina-se plano de busca ótimo.
As versões de decisão dos quatro problemas vertex separation / layout ótimo e edge
search number / plano de busca ótimo são NP-completos para grafos em geral, no entanto
todos possuem algoritmo polinomial para a classe particular das árvores. O vertex separation
(ELLIS et all., 1994), o layout ótimo (SKODINIS, 2003), o edge search number (MEGIDDO
et all., 1988) e o plano de busca ótimo (PENG et all., 2000) de uma árvore com n vértices
podem ser calculados em tempo O(n). A tabela TAB. 1.1 apresenta as complexidades dos
problemas para as classes de grafos e árvores.
17
Grafos Árvores
vertex separation
NP-completo
(SKODINIS, 2003)
O(n) (ELLIS et all., 1994)
layout ótimo
NP-completo
(SKODINIS, 2003)
O(n log n) (ELLIS et all.,
1994);
O(n) (SKODINIS, 2003)
edge search number
NP-completo
(MEGIDDO et all., 1988)
O(n) (MEGIDDO et all., 1988)
plano de busca ótimo
NP-completo
(MEGIDDO et all., 1988)
O(n log n) (MEGIDDO et all.,
1988);
O(n) (PENG et all., 2000)
TAB. 1.1 Quadro com as complexidades dos problemas estudados.
Uma variedade de trabalhos sobre vertex separation e edge search number já foram
publicados. Nossa revisão bibliográfica encontrou artigos recentes e antigos, mostrando o
interesse nestes conceitos. Dentre eles podemos mencionar (KIROUSIS et all., 1985),
(MEGIDDO et all., 1988), (KINNERSLEY, 1992), (ELLIS et all., 1994), (PENG et all.,
2000), (DÍAZ et all., 2002), (SKODINIS, 2003), (ELLIS et all., 2004), etc.
O objetivo deste trabalho é primeiramente estudar os conceitos de vertex separation,
layout ótimo, edge search number e plano de busca ótimo para grafos. Analisar os algoritmos
existentes na literatura para árvores. Investigar o comportamento destes algoritmos para
classes particulares de árvores.
Essa dissertação está dividida da seguinte forma.
O primeiro capítulo, além da introdução, apresenta alguns conceitos básicos da teoria de
grafos que auxiliarão no entendimento deste texto.
O Capítulo 2 aborda as definições de vertex separation e edge search number para grafos.
As complexidades e aplicações destes problemas também são apresentados neste capítulo.
O Capítulo 3 tem enfoque no detalhamento dos algoritmos lineares que resolvem os
problemas de vertex separation e layout ótimo para árvores.
O Capítulo 4 é exclusivamente dedicado ao estudo dos algoritmos lineares que calculam o
edge search number e plano de busca ótimo para árvores.
18
O Capítulo 5 trata da especificação dos algoritmos do Capítulo 3 para a classe particular
das árvores binárias cheias resolvendo os problemas de vertex separation e layout ótimo para
esta classe de árvores. Apresenta também um resultado novo que determina o valor do vertex
separation de uma árvore binária cheia em função de sua altura.
O Capítulo 6 mostra a adaptação dos algoritmos do Capítulo 4 para as árvores binárias
cheias determinando o edge search number e o plano de busca ótimo. Como conseqüência
deste estudo foi obtido um resultado novo que especifica o edge search number de uma árvore
binária cheia em função do seu valor de vertex separation.
Por fim o Capítulo 7 traz comentários conclusivos sobre o estudo desenvolvido e são
sugeridos alguns trabalhos futuros para a continuidade da pesquisa realizada.
Antes de apresentar os resultados obtidos veremos alguns conceitos e terminologias
básicas apresentados em (SZWARCFITER, 1988) que serão necessários para a compreensão
dos problemas e algoritmos discutidos nos capítulos seguintes.
1.2. CONCEITOS BÁSICOS
Um grafo G = (V,E) é formado por um conjunto finito não vazio de vértices V e um
conjunto E de pares não ordenados de elementos distintos desses vértices, chamados de
arestas. Consideraremos grafos sem laços e sem arestas múltiplas. Para este grafo, define-se a
cardinalidade dos conjuntos de vértices, |V| = n e de arestas, |E| = m. Seja a aresta e = (u, v)
V. Os vértices u e v são os extremos de e e são denominados vértices adjacentes. Neste caso, a
aresta e é dita incidente a ambos os vértices u e v. Duas arestas que possuem um extremo em
comum são chamadas de adjacentes. O grau de um vértice v V é o número de arestas
incidentes a v. Um vértice que possui grau igual a zero é chamado isolado.
Uma seqüência de vértices v
1
, ...., v
k
tal que (v
j
, v
j+1
) E, 1 j k-1, é denominado
caminho de v
1
a v
k
. Um caminho de k vértices é formado por k-1 arestas. O valor k-1 é o
comprimento do caminho. Um ciclo é um caminho v
1
,...., v
k
, v
k+1
sendo v
1
= v
k+1
e k 3. Um
grafo que não possui ciclos é chamado de acíclico. Um grafo G = (V,E) é conexo se existe
caminho entre todos os pares de vértices do mesmo. Caso contrário G é desconexo. O grafo G
de n vértices é completo, K
n
, se todo vértice v V existe uma aresta conectando v a cada um
dos demais vértices de G. Um grafo completo K
n
possui n(n-1)/2 arestas.
19
Seja S um conjunto e S’ S. Diz-se que S’ é maximal em relação a uma certa propriedade
P, quando S’ satisfaz à propriedade P e não existe subconjunto S’’ S’, que também satisfaz
P. Observe que a definição acima não implica necessariamente em que S’ não está
propriamente contido em nenhum subconjunto de S que satisfaça P.
Uma árvore é um grafo T = (V,E) conexo e acíclico. Se o vértice v V tem grau menor
ou igual a 1, então v é uma folha. Caso contrário, se grau de v é maior que 1, então v é um
vértice interior. Uma árvore é denominada enraizada em v V, quando um vértice v é
escolhido como especial, e chamado de raiz da árvore. Sejam u e v vértices de uma árvore de
raiz z. Suponha que u pertence ao caminho de z a v em T. Então u é ancestral de v, e v é
descendente de u. Se u v então u é ancestral próprio de v, e v é descendente próprio de u. Se
(u,v) é aresta de T então u é pai de v, sendo v filho de u. Dois vértices com mesmo pai são
irmãos. A raiz de uma árvore não possui pai. Da mesma forma, uma folha é um vértice que
não possui filhos.
Seja T = (V,E) uma árvore enraizada e v V um vértice de T. O nível de v em T é o
comprimento do caminho da raiz até o vértice v. A altura de uma árvore é igual ao valor
máximo de nível dentre todos os seus vértices. Uma subárvore de T é uma árvore enraizada
em algum vértice de T.
Uma árvore binária é uma árvore enraizada na qual todos os vértices exceto as folhas (que
não tem filhos) tem um ou dois filhos. Cada filho de um vértice de uma árvore binária pode
ser identificado como filho esquerdo ou filho direito, os quais são raízes de subárvores
também binárias, denominadas subárvore binária esquerda e subárvore binária direita. O
filho esquerdo de um vértice pode existir sem o direito e vice versa.
Uma árvore binária cheia T
h
de altura h, é uma árvore binária na qual o número de
vértices é 2
h+1
-1. Numa árvore binária cheia o filho esquerdo de qualquer vértice não pode
existir sem o direito. Além disso verifica que todo vértice que possui alguma subárvore
binária (esquerda ou direita) vazia localiza-se no último nível da árvore.
20
2. VERTEX SEPARATION E EDGE SEARCH NUMBER
2.1. INTRODUÇÃO
Neste capítulo são apresentados os dois problemas objeto de estudo desta dissertação, os
problemas vertex separation e edge search number, assim como a relação existente entre os
mesmos.
A Seção 2.2. apresenta uma visão geral do problema de vertex separation para grafos. A
Subseção 2.2.1. define o problema informalmente, aborda seu histórico, complexidade e
algumas áreas de aplicação. Além disso, mostra a relação existente entre o vertex separation e
alguns problemas importantes de grafos, como edge search number, node serach number,
interval thickness e pathwidth. Já a Subseção 2.2.2. apresenta a definição formal dos
problemas de vertex separation e layout ótimo, que são feitas em termos do layout de um
grafo.
A Seção 2.3. posiciona o problema de edge search number para grafos. A Subseção 2.3.1.
apresenta sua origem histórica, uma definição intuitiva, complexidade e alguns cenários de
aplicações. Na Subseção 2.3.2. formaliza-se a definição dos conceitos de edge search number
e plano de busca ótimo para grafos.
A Seção 2.4 descreve a complexidade dos problemas para grafos em geral.
A Seção 2.5 relaciona os problemas de vertex separation e edge search number, mostrando
que o parâmetro edge search number está limitado superiormente e inferiormente em função
do valor de vertex separation.
2.2. VERTEX SEPARATION
2.2.1. HISTÓRICO, COMPLEXIDADE E APLICAÇÕES
O conceito de vertex separation em grafos foi introduzido por Lengauer em 1981 que
descreveu o problema segundo vertex separator game (SKODINIS, 2003). Possui importante
valor prático e teórico mantendo uma relação próxima com o problema black-white pebble
game (SKODINIS, 2003).
Vertex separation pertence a uma classe particular de problemas de otimização
combinatória, chamados de problemas de layout, cujo objetivo é encontrar um layout linear
21
que otimize um determinado custo do grafo. Um layout linear é uma ordenação dos vértices
numa disposição linear do grafo. Existem variantes de problemas de layout em diferentes
áreas dentre as quais podemos mencionar otimização de redes, recuperação de informação,
análise numérica, álgebra linear, biologia computacional, teoria de grafos, arqueologia e
processamento paralelo (DÍAZ et all., 2002).
Aplicações específicas de vertex separation podem ser encontradas no desenho de
circuitos VLSI em LENGAUER, 1981 (SKODINIS, 2003) e (DÍAZ et all., 2002), na
descrição de algoritmos eficientes que utilizam a técnica “dividir para conquistar” (LIPTON
et all., 1980) e no mapeamento físico de DNA (DINNEEN, 1995).
A maior parte dos problemas de layout em grafos são problemas NP-completo, no entanto
muitas de suas aplicações utilizam algoritmos aproximados ou heurísticos que atingem um
custo próximo do valor ótimo. Determinar o vertex separation de um grafo é um problema
NP-completo (SKODINIS, 2003). Já para o caso particular de árvores existe um algoritmo
linear apresentado em (ELLIS et all., 1994) que calcula o parâmetro vertex separation.
O conceito vertex separation está relacionado direta ou indiretamente a vários outros
conceitos importantes de grafos, tais como edge search number, node serach number, interval
thickness e pathwidth.
O problema de determinar edge search number de um grafo G, esn(G), foi introduzido por
Parsons em 1976 (MEGIDDO et all., 1988). O mesmo consiste em determinar o menor
número de guardas que desenvolvam um plano de busca para limpar as arestas do grafo G.
Uma aresta é limpa quando uma extremidade da mesma recebe um guarda e percorre a aresta
até a outra extremidade. Um plano de busca permite três tipos de operações: colocar um
guarda em um vértice, remover um guarda de um vértice, movimentar o guarda ao longo de
uma aresta. Um plano de busca que utiliza o menor número de guardas é um plano de busca
ótimo (MEGIDDO et all., 1988). Este conceito será definido com maiores detalhes na
Subseção 2.3.
O problema de determinar o node search number de um grafo G, ns(G), é uma versão do
problema anterior e foi introduzido por Kirousis e Papadimitriou em 1986. Neste caso a
movimentação de um guarda ao longo de uma aresta não é permitida (KIROUSIS et all.,
1986).
O problema de determinar interval thickness,
(G), foi introduzido por Kirousis e
Papadimitriou em 1985. Dado um conjunto de intervalos I na reta, o grafo de intervalos de I é
22
obtido representando cada intervalo por um vértice e cada interseção de dois intervalos por
uma aresta entre os vértices correspondentes.
Interval thickness de um grafo é a menor clique máxima obtida dentre todos os grafos que
são supergrafos de G (KIROUSIS et all., 1985).
O problema de determinar pathwidth de um grafo G, pw(G), foi introduzido por Robertson
e Seymour em seus trabalhos sobre teoria de menores, publicados desde 1983. Uma
decomposição em caminho de um grafo é uma seqüência de subconjuntos de vértices, D =
X
1
,... X
r
, que verificam:
i) cada aresta do grafo G tem as duas extremidades em algum conjunto X
i
, e
ii) se um vértice do grafo G pertence aos conjuntos X
i
e X
j
onde i < j, então o vértice
deve pertencer a todos os conjuntos X
k
onde i < k < j.
A largura do grafo G com respeito a D é o maior número de vértices nos conjuntos X
i
, 1 i
r, menos 1 unidade. Pathwidth de G é definida como a menor largura de G considerando todas
as possíveis decomposições em caminho de G (ROBERTSON et all., 1983) e (ROBERTSON
et all., 1985).
A tabela TAB. 2.1 mostra a relação do valor do vertex separation de um grafo com os
valores de edge search number, node search number, interval thickness e pathwidth.
Parâmetro relação com vertex separation
edge search number vs (G)
esn (G) vs (G) + 2 (ELLIS et all., 1994)
node search number ns (G)= vs (G) + 1 (KIROUSIS et all., 1986)
path width Pw (G)= vs (G) (KINNERSLEY, 1992)
interval thickness
(G)= vs (G) + 1 (KIROUSIS et all., 1985)
gate matrix layout gml (G) = vs (G) + 1 (ELLIS et all., 1994)
TAB. 2.1 Relação do vertex separation com outros problemas em grafos
2.2.2. DEFINIÇÃO DO PROBLEMA
O problema de vertex separation é um problema definido em grafos.
Seja G = (V, E) um grafo conexo e não direcionado, onde |V| = n e |E| = m.
Um layout linear L, ou simplesmente um layout L de G é uma função bijetora L: V
{1,...n}. A FIG. 2.1 mostra dois possíveis layouts lineares para o grafo G = K
3,3
.
23
A função inversa L
-1
identifica o vértice que se encontra em determinada posição do
layout L, L
-1
: {1,2,...,n} V.
u
A B C D E F
L’
(
u
)
1 2 3 4 5 6
u
A B C D E F
L
(
u
)
1 3 6 2 4 5
FIG. 2.1 Dois layouts, L e L’, para o grafo K
3,3
.
Cada layout corresponde a uma ordenação dos vértices do grafo. Portanto existem n!
layouts distintos para um grafo G com n vértices. O conjunto de todos os layouts do grafo G é
denotado por (G).
Intuitivamente, cada valor i, 1 i n, divide o layout L de G em dois conjuntos de
vértices:
Esq
L
(i) = {u V : L(u) i} e Dir
L
(i) = {u V : L(u) > i}.
A FIG. 2.2 mostra os conjuntos Esq
L
(i) e Dir
L
(i), onde i = 3, para o grafo G e o layout L
da FIG. 2.1.
!
!
FIG. 2.2 Conjuntos Esq
L
(3) e Dir
L
(3) do layout L da FIG. 2.1.
Um layout parcial L
i
de L, para 1 i n é uma função bijetora L
i
: V’ {1,2,...,|V’|},
onde V’ é um subconjunto de V dado por V’ = { u V : L(u) i }.
Um vértice u é ativo num layout parcial L
i
se u pertence ao conjunto Esq
L
(i) e possui
aresta que incide em algum vértice do conjunto Dir
L
(i). O conjunto de vértices ativos num
layout parcial L
i
é definido a seguir.
24
A
L
(i) = { u Esq
L
(i) : (u,v) E com v Dir
L
(i) }
A FIG. 2.3 apresenta os layouts parciais L
i
e os conjuntos ativos A
L
(i), 1 i 6, para o
grafo G e o layout L da FIG. 2.1.
O vertex separation do layout L de G ou simplesmente o vertex separation de L, vs
L
(G), é
a máxima cardinalidade dentre todos os conjuntos de vértices ativos de L:
vs
L
(G) = max
1 i n
|A
L
(i)|
No caso do grafo G e do layout L da FIG. 2.1, tem-se vs
L
(G) = max
1 i 6
|A
L
(i)| = 4, como
apresenta a FIG. 2.3.
O vertex separation do grafo G, vs(G), é o menor valor de vertex separation dentre todos
os possíveis layouts de G:
vs(G) = min
L (G)
{ vs
L
(G) } = min
L (G)
{ max
1 i n
|A
L
(i)| }
Um layout L de G é ótimo se vs
L
(G) = vs(G). Ou seja, é um dos layouts L (G)
cujo valor vs
L
(G) é o mínimo.
FIG. 2.3 Para o layout L da FIG. 2.1 são apresentados os layouts parciais L
i
e os conjuntos
A
L
(i) de vértices ativos para 1 i 6.
25
2.3. EDGE SEARCH NUMBER
2.3.1. HISTÓRICO, COMPLEXIDADE E APLICAÇÕES
Também conhecido como problema de contaminação de arestas, o cálculo do edge search
number pertence a classe de problemas de busca em grafos e foi originalmente proposto e
estudado por T. Parsons em 1976 (MEGIDDO et all., 1988).
Intuitivamente o edge search number de um grafo G é o menor número de guardas
necessários para garantir a captura de um fugitivo que se movimenta ao longo das arestas de
G. Diretamente relacionado com o valor do edge search number, pode-se determinar um
plano de busca, ou seja uma seqüência de movimentações dos guardas no grafo a fim de
capturar o fugitivo.
Diversos cenários de aplicação têm utilizado este conceito considerando espaço contínuo,
tais como controle de tráfego aéreo, estratégia militar, e planejamento de trajetórias (GUIBAS
et all., 1999). A robótica é outra área importante de aplicação (GUIBAS et all., 1999). Por
exemplo, suponha que o sistema de segurança de um edifício possua alguns robôs com
câmeras ou sensores para detecção de intrusos. A fim de minimizar custos, seria importante
conhecer o número mínimo de robôs necessários para percorrer todo o prédio e capturar o
intruso. Outra utilização seria um plano de busca otimizado para localizar itens de estoque
num armazém ou fábrica, ou outra forma de busca.
O edge search number relaciona-se com outros parâmetros de um grafo tais como largura
de banda topológica (KIROUSIS et all., 1986), pebble demand (MEGIDDO et all., 1988) e
interval thickness (MAKEDON et all., 1985).
O problema de determinar o edge search number de um grafo G, esn(G), é um problema
NP-completo (MEGIDDO et all., 1988). Em 1976, Parsons provou que este problema
pertence às classes NP e co-NP para o caso particular de árvores (MEGIDDO et all., 1988). E
em (MEGIDDO et all., 1988) é mostrado que o edge search number pode ser obtido em
tempo linear para árvores.
Segundo (PENG et all., 2000) o edge search number é equivalente ao problema de corte
mínimo para grafos com grau máximo igual a 3. Além disso, é um problema NP-completo não
somente para grafos, mas também para grafos planares com vértices de grau máximo igual a 3
e grafos starlike. No entanto o edge search number pode ser resolvido em tempo polinomial
26
para grafos completos, árvores, grafos de intervalo, grafos split e grafos k-starlike para k 2
(PENG et all., 2000).
Mais recentemente o trabalho de (ALSPACH, 2004) estabelce novas nomenclaturas para
os problemas de edge search number e node search number.
Em (DYER, 2004) examina-se o problema de sweeping para grafos direcionados.
2.3.2. DEFINIÇÃO DO PROBLEMA
Nesta seção apresentamos formalmente o problema de edge search number para grafos.
Seja G = (V,E) um grafo conexo e não direcionado, onde |V| = n e |E| = m.
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. Uma equipe de guardas
percorre o túnel com a missão de encurralar o fugitivo e por conseguinte, capturá-lo. De modo
alternativo podemos pensar que a movimentação do fugitivo pelas arestas do grafo contamina
estas arestas, por outro lado, a movimentação dos guardas descontamina ou limpa as arestas
contaminadas. A missão da equipe de guardas é limpar todas as arestas do grafo e capturar o
fugitivo. O problema consiste em determinar o menor número de guardas que garanta a
limpeza de todas as arestas do grafo.
Para definir melhor o problema edge search number, supor inicialmente que todas as
arestas do grafo estão contaminadas. São permitidos unicamente três tipos de operações no
grafo:
(1) colocar 1 guarda em um vértice;
(2) movimentar 1 guarda ao longo de uma aresta;
(3) remover 1 guarda de um vértice.
Uma aresta (u,v) pode ser limpa utilizando 1 ou 2 guardas da seguinte forma:
2 guardas: Colocar um guarda em u. Colocar um segundo guarda em u e movimentá-lo
de u para v;
1 guarda: Quando todas as arestas incidentes a u estiverem limpas, com exceção de
(u,v), então basta colocar um guarda em u e movimentar este mesmo guarda de u para
v.
A FIG. 2.4 mostra a limpeza da aresta (D,C) para o grafo da FIG. 2.1 no seguinte cenário:
27
i. somente as arestas (A,D) e (D,B) estão limpas;
ii. o grafo possui 2 guardas, o primeiro no vértice A e o segundo no vértice B.
Para limpar a aresta (D,C) um novo guarda é inicialmente colocado no vértice D. Após isso,
este terceiro guarda é movimentado ao longo da aresta (D,C) até chegar ao vértice C.
FIG. 2.4 Limpeza da aresta (D,C) do grafo da FIG. 2.1.
Uma aresta (u,v) permanece limpa quando todo caminho entre uma extremidade de (u,v) e
uma extremidade de uma aresta contaminada estiver bloqueado pela presença de pelo menos
um guarda.
Uma aresta (u,v) é recontaminada se existir um caminho sem guardas entre uma
extremidade da aresta e a extremidade de alguma outra aresta contaminada. Logo, uma aresta
limpa pode voltar a ser contaminada através da movimentação ou retirada de um guarda que
resulte em um caminho desprotegido (sem guardas) desde uma extremidade da aresta limpa
até uma extremidade de uma aresta contaminada. A FIG. 2.5 mostra o efeito da
recontaminação no grafo da FIG. 2.1 quando um guarda é removido do vértice F no seguinte
cenário:
i) somente as arestas (A,D), (D,B), (D,C) e (F,C) estão limpas;
ii) o grafo possui 1 guarda em cada um dos vértices A, B, C e F, totalizando 4 guardas.
O guarda do vértice F é retirado do grafo. A aresta (F,C) é recontaminada pois existe um
caminho sem guardas entre a extremidade F desta aresta limpa e a extremidade F da aresta
contaminada (F,B).
28
FIG. 2.5 Recontaminação da aresta (F,C) do grafo da FIG. 2.1.
Em (MEGIDDO et all., 1981) foi proposta a questão: “A recontaminação em um grafo
pode melhorar o seu valor de edge search number?”. LaPaugh 1993, mostrou que numa busca
em grafo G a recontaminação não altera o valor do edge search number, ou seja, sempre
existe um plano de busca para G que utiliza o número mínimo de guardas, esn(G), e que não
envolve recontaminação de arestas (MEGIDDO et all., 1981).
O grafo torna-se totalmente limpo quando todas as suas arestas estiverem limpas
simultaneamente.
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 edge search number resume-se então em responder a pergunta: Qual a
menor quantidade de guardas para a qual existe um plano de busca que garanta a limpeza
total do grafo?
A tabela TAB. 2.2 apresenta um plano de busca para o grafo G da FIG. 2.1 que utiliza 5
guardas para limpar totalmente G.
29
guardas
utilizados
plano de busca
1 colocar 1 guarda em A;
2 colocar 1 guarda em A;
mover 1 guarda de A para D;
3 colocar 1 guarda em A;
mover 1 guarda de A para E;
mover 1 guarda de A para F;
4 colocar 1 guarda em D;
mover 1 guarda de D para B;
mover 1 guarda de D para C;
5 colocar 1 guarda em E;
mover 1 guarda de E para B;
4 remover 1 guarda de B;
mover 1 guarda de E para C;
3 remover 1 guarda de C;
mover 1 guarda de B para F;
2 remover 1 guarda de F;
mover 1 guarda de F para C;
1 remover 1 guarda de C;
0 remover 1 guarda de C.
TAB. 2.2 Um plano de busca para o grafo da FIG. 2.1 que utiliza 5 guardas.
30
2.4. COMPLEXIDADE
Os problemas vertex separation e edge search number são NP-completo para grafos
(SKODINIS, 2003; MEGIDDO et all., 1988).
A seguir descreveremos a idéia utilizada por Megiddo para provar que o problema de
determinar o menor número de guardas que limpe todas as arestas de um grafo (edge search
number) é NP-completo.
A prova é baseada numa transformação polinomial a partir do problema NP-completo
CORTE MÍNIMO EM SUBCONJUNTOS DE IGUAL TAMANHO (GAREY et all, 1999).
Sejam os problemas de decisão.
CORTE MÍNIMO EM SUBCONJUNTOS DE IGUAL TAMANHO
Dados: G = ( V, E ), | V | para K > 0 inteiro.
Pergunta: Existe partição de V em subconjuntos V
1
e V
2
, tal que | V
1
| = | V
2
| = ½ | V | e |{
(u,v) E : u V
1
e v
V
2
}| K?
EDGE SEARCH NUMBER
Dados: G = ( V , E ), | V | = n , s
0 inteiro.
Pergunta: O grafo G pode ser limpado usando no máximo s guardas?
(Existe um plano de busca para descontaminar o grafo G utilizando no máximo s guardas?)
Sejam também as variáveis:
n = | V |, K > 0,
d = max
v
V
{grau(v)},
N = 6( d + K ) e M = n ( n + 2 ) N.
Um grafo H = ( U, F ) é então construído a partir de G da seguinte forma:
1. No conjunto U existirá 1 clique C
i
de tamanho M para cada vértice v
i
V, 1
i
n, e
mais 1 clique especial C
A
de tamanho M, ou seja, existirão n+1 cliques de tamanho M;
2. No conjunto F, entre cada par de cliques C
i
,C
j
de tamanho M,
adicionar nN arestas;
adicionar mais N arestas se i = A ou j = A;
adicionar mais 3 arestas se (v
i
,v
j
)
E.
31
A prova consiste em mostrar que o grafo H pode ser descontaminado utilizando s guardas.
Conclui-se que existe um plano de busca para o grafo H que usa s guardas, s(H) s, se e
somente se o grafo G admite um CORTE EM SUBCONJUNTOS DE IGUAL TAMANHO
menor ou igual a K. Como H e s podem ser construídos facilmente a partir de G e K, temos
uma transformação polinomial e portanto o problema edge search number também é NP-
completo.
2.5. RELAÇÃO ENTRE VERTEX SEPARATION E EDGE SEARCH NUMBER
O Teorema 2.1 a seguir, que foi apresentado em (ELLIS et all., 1994) estabelece limite
superior e inferior para o edge search number de um grafo em função do valor de vs(G). A
prova deste teorema consiste de dois lemas, cada um dos quais mostra um dos limites do edge
search number. Incluímos neste documento a prova de um dos lemas, Lema 2.2, pois nele é
descrito o Algoritmo 2.1 cuja idéia será utilizada no Capítulo 6 para determinar um plano de
busca ótimo de uma árvore binária cheia.
Teorema 2.1 (ELLIS et all., 1994) Seja o grafo G = (V,E).
Então vs(G) esn(G) vs(G) + 2.
Prova: Este teorema é provado pelos Lemas 2.1 e 2.2 descritos a seguir.
Lema 2.1 (ELLIS et all., 1994) Seja o grafo G = (V,E). Então vs(G) esn(G).
Lema 2.2 (ELLIS et all., 1994) Seja o grafo G = (V,E). Então esn(G) vs(G) + 2.
Prova:
Primeiramente mostraremos que é possível, a partir de um layout L de G, construir um
plano de busca que utilize w guardas para limpar G, de tal forma que w vs
L
(G) + 2 guardas.
O plano de busca é gerado pelo seguinte algoritmo.
32
Algoritmo 2.1 (Ellis et all., 1994)
Algoritmo busca (G, L)
(1) para i := 1 to |V| faça
início
x := L
-1
(i);
(2) colocar um guarda em x;
para (cada vizinho y à esquerda de x e cada aresta (x, y) ) faça
início
(3) colocar um guarda em y;
movimentar o guarda de y para x;
remover um guarda de x;
fim;
para (cada laço (x, x) ) faça
início
(4) colocar um guarda em x;
movimentar um guarda ao longo do laço;
remover um guarda de x;
fim;
remover os guardas dos vértices que não estão ativos em L
i
;
fim;
Pode-se mostrar, por indução em i, que no início da i-ésima iteração do laço para mais
externo (linha 1), as duas condições a seguir são satisfeitas:
i) todas as arestas conectando vértices no domínio do layout parcial L
i-1
estão limpas, e
ii) há exatamente um guarda em cada vértice ativo do layout parcial L
i-1
, e não existe
guarda em qualquer vértice não ativo.
Pela condição i) anterior concluímos que ao final da última iteração da linha 1 o algoritmo
terá limpado todas as arestas de G.
Já pela condição ii) obtemos que, no início da i-ésima iteração, w = |A
L
(i-1)|. Pela
definição vs
L
(G) = max
1 i |V|
{ |A
L
(i)| : L (G)}. Portanto podemos afirmar que no início
da i-ésima iteração da linha 1, w vs
L
(G). Resta analisar a variação de w durante a execução
da i-ésima iteração da linha 1. Observa-se que somente 2 guardas extras poderão ser
33
adicionados ao grafo durante a i-ésima iteração. O primeiro guarda será incluído na linha 2 e
permanecerá no grafo até o final da i-ésima iteração da linha 1, alterando o limite superior de
w para w vs
L
(G) + 1. Um segundo guarda poderá ser adicionado ou não dentro de um laço
na linha 4, tornando w vs
L
(G) + 2. No entanto, antes que a linha 4 volte a ser executada, a
linha 5 remove este segundo guarda extra impedindo que o limite superior de w atinja vs
L
(G)
+ 3. Desta forma, após as execuções necessárias do laço da linha 3, w vs
L
(G) + 2. De
maneira análoga, o laço da linha 6 adiciona um outro guarda na linha 7, no entanto este guarda
também é removido na linha 8 antes do início de uma nova iteração do laço, mantendo o
limite superior de w em w
vs
L
(G) + 2.
Portanto provou-se que dado um layout L de um grafo G, o Algoritmo 2.1 constrói um
plano de busca para G que utiliza w guardas de tal forma que w
vs
L
(G) + 2.
Supor agora que L seja um layout ótimo do grafo G. Neste caso sabemos que vs
L
(G) =
vs(G). Aplicando o Algoritmo 2.1 para um layout ótimo L, obtemos que w vs(G) + 2.
É imediato constatar que o número de guardas w utilizado pelo plano de busca não é
necessariamente o número ótimo de guardas esn(G), logo, esn(G)
w. Portanto podemos
concluir que esn(G) vs(G) + 2.
As FIG. 2.6, FIG. 2.7 e FIG. 2.8 mostram 3 árvores, T1, T2 e T3, que ilustram a
desigualdade apresentada pelo Teorema 2.1. Na FIG. 2.6, a árvore T1 verifica que esn(T1) =
vs(T1). Na FIG. 2.7 temos a árvore T2 com esn(T2) = vs(T2) + 1. E finalmente pela árvore T3
da FIG. 2.8 constatamos que esn(T3) = vs(T3) + 2.
FIG. 2.6 Exemplo da árvore T1 para o Teorema 2.1, onde esn(T1) = vs(T1).
34
"#
FIG. 2.7 Exemplo da árvore T2 para o Teorema 2.1, onde esn(T2) = vs(T2).
FIG. 2.8 Exemplo de uma árvore T3 para o Teorema 2.1 onde esn(T3) = vs(T3) + 2.
A FIG. 2.9 apresenta o Algoritmo 2.1 aplicado no layout L do grafo G da FIG. 2.1. O
resultado obtido é um plano de busca que utiliza 6 guardas para limpar todo o grafo G.
35
FIG. 2.9 Plano de busca com 6 guardas gerado pelo Algoritmo 2.1 para o grafo da FIG. 2.1.
36
3. VERTEX SEPARATION E LAYOUT ÓTIMO PARA ÁRVORES
3.1. INTRODUÇÃO
Neste capítulo será tratado o problema vertex separation e a determinação do layout ótimo
para o caso particular de árvores.
A Seção 3.2 descreve o algoritmo linear de Ellis para cálculo do vertex separation para
árvores. A Subseção 3.2.1. caracteriza recursivamente o vertex separation das subárvores de
uma árvore. O Teorema 3.1 relaciona o vertex separation de uma árvore com os valores de
vertex separation das suas subárvores do mesmo. A Subseção 3.2.2 descreve o algoritmo
linear de Ellis que calcula o vertex separation de uma árvore baseado na criticalidade dos
vértices, obtida pela técnica de sequenciamento dos vértices de uma árvore.
A Seção 3.3 é dedicada à descrição do algoritmo linear de Skodinis que determina o
layout ótimo para árvores. As Subseções 3.3.1 e 3.3.2 definem uma árvore simples, as partes
de uma árvore, layouts extensíveis à esquerda, à direita e coarse layout, conceitos úteis para
obter o layout ótimo. A Subseção 3.3.3 mostra como calcular um layout ótimo a partir do
coarse layout de uma árvore. Na Subseção 3.3.4 são abordados os detalhes da construção de
um coarse layout. Finalmente a Subseção 3.3.5 apresenta o algoritmo linear de Skodinis, que
resolve o cálculo do layout ótimo de uma árvore.
3.2. VERTEX SEPARATION
Nesta subseção é apresentado um algoritmo de tempo linear para cálculo do vertex
separation de árvores gerais. Este algoritmo está baseado na possibilidade de caracterizar
recursivamente o vertex separation das subárvores da raiz de uma árvore qualquer.
Primeiramente vamos lembrar o conceito vertex separation. Seja T a árvore da FIG. 3.1.
Como T possui 7 vértices então existem 7! layouts diferentes para T.
A FIG. 3.1 apresenta dois layouts de T, L e L’. Para o layout L temos vs
L
(T) = max
1 i 7
{|A
L
(i)|} = 2. Como o vertex separation da árvore T é igual a 2 então L é um layout ótimo de
T, pois vs
L
(T) = vs(T). Para o segundo layout L’ temos vs
L’
(T) = max
1 i 7
{|A
L’
(i)|} = 3,
logo L’ não é um layout ótimo de T, pois vs
L’
(T) vs(T).
37
O vertex separation de T será o menor valor de vertex separation dentre todos os 7!
layouts de T, ou seja, vs(T) = min
L (T)
{ vs
L
(T) }.
i A
L
(i) |A
L
(i)|
1 {A} 1
2 {A,B} 2
3 {A} 1
4 {A,C} 2
5 {A} 1
6 {D} 1
7
0
i A
L’
(i) |A
L’
(i)|
1 {B} 1
2 {B,F} 2
3 {B,B} 2
4 {B,C,G}
3
5 {B,C,D}
3
6 {B,C,D}
3
7
0
FIG. 3.1 Cálculo do vertex separation de dois layouts da árvore T
3.2.1. CARACTERIZAÇÃO RECURSIVA DO VERTEX SEPARATION DAS
SUBÁRVORES DE UMA ÁRVORE
Nesta seção é apresentada a caracterização recursiva de árvores com vertex separation
igual a k dada por (ELLIS et all., 1994) que é análoga às descritas por Parsons em 1976
(ELLIS et all., 1994) para edge search number e (CHUNG et all., 1985) para cutwidth de
árvores gerais.
Definição 3.1 (ELLIS et all., 1994): Sejam a árvore T = (V,E) e x V. As subárvores
induzidas por x são aquelas que resultam da retirada do vértice x da árvore T.
38
A FIG. 3.2 mostra uma árvore T de onde é retirado o vértice x, produzindo desta forma 4
subárvores chamadas de subárvores induzidas por x. Neste caso também dizemos que o
vértice x induz 4 subárvores.
FIG. 3.2 Subárvores induzidas por x
O teorema a seguir é semelhante aos teoremas de Parsons, 1976 (ELLIS et all., 1994) e
(CHUNG et all., 1985), e relaciona o vertex separation de uma árvore com os valores de
vertex separation das subárvores induzidas pela raiz desta árvore.
Teorema 3.1 (ELLIS et all., 1994): Seja T uma árvore e seja k 1. vs(T) k se e somente
se para todo vértice x em T existem no máximo duas subárvores induzidas por x com vertex
separation k e todos as demais subárvores possuem vertex separation k-1.
O corolário a seguir é obtido pela negação do Teorema 3.1.
Corolário 3.1 (ELLIS et all., 1994): Sejam uma árvore T e k número inteiro, vs(T) > k se e
somente se existe um vértice em T que induza 3 ou mais subárvores T’
i
, i 3, tais que vs(T’
i
)
k.
A FIG. 3.3 ilustra o Corolário 3.1. A árvore T possui um vértice x que ao ser retirado de T
induz três subárvores, cada uma delas com vertex separation igual a 2, portanto o vertex
separation de T é igual a 3.
39
FIG. 3.3 Vértice x induz três subárvores, T’
i
, de T tais que vs(T’
i
) = 2, 1 i 3.
3.2.2. CÁLCULO DO VERTEX SEPARATION DE UMA ÁRVORE
Nesta seção será descrito um algoritmo com complexidade de tempo linear apresentado
em (ELLIS et all., 1994) para calcular o vertex separation de árvores. Primeiramente serão
definidos alguns conceitos que auxiliarão no entendimento do algoritmo.
3.2.2.1.CRITICALIDADE DE UM VÉRTICE
As árvores utilizadas neste documento devem sempre ser consideradas como árvores
enraizadas em algum vértice, desta forma é bem definida a relação pai e filho para os vértices
da árvore.
A subárvore de T com raiz u será denotada por T[u]. Seja T[u; v
1
, ..., v
i
] a árvore
resultante da remoção das subárvores enraizadas em v
1
, ..., v
i
na árvore de raiz u.
Pode-se definir a criticalidade de um vértice u, no caso em que vs(T[u]) = k e u possua no
máximo 2 filhos com vertex separation igual a k. Ou seja, se existir um terceiro filho de u
40
com vertex separation igual a k então o vertex separation de T[u] passa a valer k+1, pelo
Corolário 3.1. A seguir a definição formal de vértice k-crítico.
Definição 3.2 (ELLIS et all., 1994): Um vértice u é k-crítico ou simplesmente crítico
numa árvore enraizada T se e somente se u possui dois filhos v
1
e v
2
tais que vs(T[v
1
]) =
vs(T[v
2
]) = k.
A FIG. 3.4 mostra uma árvore T cujo vértice u possui três filhos, v
1
, v
2
, v
3
. Os filhos v
1
e
v
2
são tais que vs(T[v
1
]) = vs(T[v
2
]) = 1, e o vértice v
3
verifica vs(T[v
3
]) = 0, logo o vértice u é
1-crítico.
FIG. 3.4 Criticalidade do vértice u em T
Desta forma, pode-se concluir o seguinte corolário.
Corolário 3.2 (SKODINIS, 2003): Toda árvore cujo valor de vertex separation é igual a k
possui no máximo um vértice k-crítico.
O Corolário 3.2 é válido, pois caso não fosse válido existiria uma árvore T com vs(T) = k
contendo dois vértices k-críticos. Neste caso existiriam 3 subárvores induzidas por algum
vértice de T com vertex separation igual a k. Isto é um absurdo pelo Corolário 3.1, pois
contradiz o fato de que vs(T) = k. A FIG. 3.5 mostra uma árvore T que possui dois vértices 1-
críticos, u
1
e u
2
. O vértice u
1
de T induz 4 subárvores, T1, T2, T3 e T4, onde T1, T2 e T3
possuem vertex separation igual a 1, e para T4, vs(T4) = 0. Logo, pelo Corolário 3.1 o vertex
separation da árvore T é igual a 2.
41
FIG. 3.5 Árvore T possui 2 vértices 1-crítico, logo vs(T) = 2.
O corolário seguinte é imediato do Teorema 3.1 e determina, através de 6 casos, o valor
do vertex separation de T[u] a partir dos valores de vertex separation das subárvores
enraizadas nos filhos de u. O Corolário 3.3 é a base do algoritmo para cálculo do vertex
separation em árvores.
Corolário 3.3 (ELLIS et all., 1994): Seja T[u] uma árvore com raiz u, numa árvore
enraizada T, possuindo os filhos v
1
, ..., v
d
e seja k = max
i
{ vs(T[v
i
]) }.
(1) Se mais que duas árvores T[v
i
], 1 $ i $ d, possuem vertex separation igual a k, então
vs(T[u]) = k+1.
(2) Se exatamente duas das árvores T[v
i
], 1 $ i $ d, possuem vertex separation igual a k e
pelo menos uma delas contem um vértice k-crítico, então vs(T[u]) = k+1.
(3) Se exatamente duas das árvores T[v
i
], 1 $ i $ d, possuem vertex separation igual a k e
nenhuma delas contem um vértice k-crítico, então vs(T[u]) = k.
(4) Se exatamente uma das árvores T[v
i
], 1 $ i $ d, possui vertex separation igual a k e esta
árvore contém um vértice k-crítico x e vs(T[u,x]) = k, então vs(T[u]) = k+1.
(5) Se exatamente uma das árvores T[v
i
], 1 $ i $ d, possui vertex separation igual a k e esta
árvore contém um vértice k-crítico x e vs(T[u,x]) < k, então vs(T[u]) = k.
(6) Se exatamente uma das árvores T[v
i
], 1 $ i $ d, possui vertex separation igual a k e esta
árvore não contem um vértice k-crítico, então vs(T[u]) = k.
Pelo exposto até aqui, é claro que a criticalidade é a principal característica dos vértices de
uma árvore a fim de se determinar o parâmetro vertex separation. Examinando
42
adequadamente a criticalidade dos filhos de um vértice u e utilizando o Teorema 3.1 pode ser
determinado o valor do vertex separation.
3.2.2.2.SEQUENCIAMENTO DOS VÉRTICES
A técnica de sequenciamento que será utilizada no Algoritmo 3.1 é similar às técnicas
utilizadas por (YANNAKAKIS, 1995), (CHUNG et all., 1985) e (MEGIDDO et all., 1988)
para calcular edge search number e cutwidth no caso particular de árvores.
O sequenciamento constrói a seqüência correspondente a raiz de um árvore atribuindo
uma subseqüência para cada vértice da árvore. A seguir daremos uma idéia intuitiva do
sequenciamento da raiz de uma árvore. Supor que para a árvore T enraizada em u são
conhecidos o valor vs(T) = k e um vértice k-crítico v, caso exista. Considera-se o seguinte
processo em T: enquanto o vértice k-crítico v de T é diferente da raiz u, remover a subárvore
T[v] de T. Considerar agora a árvore resultante como T e repetir o processo até que o vértice v
seja igual a u ou não exista vértice v em tais condições. Ao final do processo obtemos uma
árvore com valor de vertex separation igual a r, e se existir um vértice r-crítico este será a raiz
u. As figuras FIG. 3.7 e FIG. 3.8 ilustram o conceito intuitivo do sequenciamento.
A seqüência s de u é uma lista ordenada com: os valores de vertex separations das árvores
consideradas no processo seguidos do valor do vertex separation igual a r da árvore final. Os
vértices críticos v das árvores consideradas no processo e a raiz u da árvore final são
chamados vértices da seqüência s. A seguir apresentamos a definição formal da seqüência de
um vértice introduzido por Ellis.
Definição 3.3 (ELLIS et all., 1994): Seja T uma árvore enraizada no vértice u com vs(T) =
k
1
.Uma lista de inteiros s = (k
1
, ... ,k
p
), com k
1
> k
2
> ... > k
p
0, é uma seqüência de u se
existir um conjunto de vértices {v
1
, ... ,v
p-1
,v
p
= u} tal que:
i) vs(T[u]) = k
1
.
ii) para 1 $ i < p, vs(T[u; v
1
, ..., v
i
]) = k
i+1
,
iii) para 1 $ i < p, v
i
é um vértice k
i
-crítico em T[u; v
1
, ..., v
i-1
],
iv) para u = v
p
:
- se v
p
não estiver marcado em s com o símbolo (‘) então u é vértice k
p
-crítico em T[u;
v
1
, ..., v
p-1
],
43
- se v
p
estiver marcado em s com o símbolo (‘) então não existe vértice k
p
-crítico em
T[u; v
1
, ..., v
p-1
].
exemplo 1
Sejam T a árvore da FIG. 3.6(a) com raiz u, e a seqüência s = (k
1
) = (2) do vértice u. Pela
Definição 3.3 tem-se:
pela parte (i) vs(T[u]) = k
1
= 2, portanto o vertex separation de T[u] é 2;
por (iv) u é vértice 2-crítico.
exemplo 2
Sejam T a árvore da FIG. 3.6(b) com raiz u, e a seqüência s = (k
1
, k
2
) = (2, 0) do vértice u.
Pela Definição 3.3 tem-se:
pela parte (i) vs(T[u]) = k
1
= 2, portanto T[u] possui vertex separation igual a 2;
por (ii) vs(T[u; v
1
]) = k
2
= 0, portanto T[u; v
1
] é uma subárvore de único vértice;
por (iii) tem-se para i = 1 que v
1
é um vértice 2-crítico em T[u; v
1
];
por (iv) u não é vértice crítico.
"#
% %
&'('
)"#
% %
&'('
*
FIG. 3.6 Significado das seqüências das raízes de duas árvores
As figuras FIG. 3.7 e FIG. 3.8 apresentam o conceito intuitivo da técnica de
sequenciamento aplicada em duas árvores. Na FIG. 3.7 a árvore T tem raiz com seqüência s =
(2,1,0). O vértice C é 2-crítico e diferente da raiz A, portanto devemos remover a subárvore
T[C] de T. Desta forma é originada uma nova árvore T’ com raiz A. O vértice B é 1-crítico em
44
T’ e diferente da raiz A de T’ logo remove-se a subárvore T’[B] de T’. Gera-se então uma
nova árvore T’’ com único vértice A, terminando assim o processo de sequenciamento de T.
Observamos que a seqüência s da raiz A de T é uma lista com os valores dos vertex
separation das subárvores removidas T[C] e T’[B] seguidos do vertex separation da árvore
final T’’, ou seja, s = (2,1,0). Chamamos de vértices correspondentes à seqüência s de T aos
vértices críticos das árvores removidas T[C] e T’[B] seguidos da raiz da árvore final T’’, ou
seja, ao conjunto de vértices {C,B,A}.
FIG. 3.7 Aplicação da técnica de sequenciamento numa árvore T.
No exemplo da FIG. 3.8 a árvore T tem raiz A cuja seqüência é s = (3,2,1). O vértice E é
3-crítico em T e diferente da raiz A, logo devemos remover a subárvore T[E] de T. É gerada
uma nova árvore T’ com raiz A. O vértice D é 2-crítico em T’ e diferente da raiz A de T’
portanto remove-se a subárvore T’[D] de T’. Origina-se nova árvore T’’ com raiz A, no
entanto, o vértice A é também o vértice 1-crítico de T’’. Desta forma finaliza-se o processo de
sequenciamento de T.
Observamos que a seqüência s da raiz A de T é uma lista com os valores dos vertex
separations das árvores removidas T[E] e T’[D] seguidos do vertex separation da árvore final
T’’, ou seja, s = (3,2,1). Chamamos de vértices correspondentes à seqüência s de T aos
vértices críticos das árvores removidas T[E] e T’[D] seguidos da raiz da árvore final T’’, ou
seja, ao conjunto de vértices {E,D,A}.
45
FIG. 3.8 Aplicação da técnica de sequenciamento numa árvore T.
É imediato verificar que T[u; v
1
, ..., v
p
] é uma árvore vazia. Nota-se também que pela
simples observação da seqüência de um vértice de T, podem-se concluir facilmente
informações importantes que serão utilizadas no algoritmo que determina o vertex separation
de uma árvore, são elas:
46
o valor do vertex separation de T é dado pelo maior valor inteiro da seqüência da raiz de
T, de maneira análoga, o vertex separation de uma subárvore T[v] de T enraizada num
vértice v é igual ao maior valor da seqüência correspondente ao vértice v;
seja k
p
o último elemento inteiro da seqüência de v. O vértice v será crítico se k
p
não
estiver marcado com o símbolo (‘), da mesma forma o vértice v será não-crítico caso k
p
esteja marcado com o símbolo (‘);
se v
i
é k
i
-crítico em T[u; v
1
, ..., v
i-1
] então diz-se que k
i
é crítico em s, caso contrário k
i
é
não-crítico em s. Pela definição, todos os k
i
são críticos em s exceto k
p
que pode ou não ser
crítico sendo por isso marcado ou não com (‘), portanto este símbolo é usado apenas no
último elemento de uma seqüência.
Definição 3.4 (ELLIS et all., 1994): Um elemento crítico de uma seqüência é um
elemento da seqüência que está associado a um vértice crítico.
3.2.2.3.ALGORITMO DE ELLIS
O algoritmo proposto por (ELLIS et all., 1994) determina em tempo linear o vertex
separation de uma árvore T. A idéia utilizada por Ellis é aplicar a técnica de sequenciamento
recursivamente para determinar as seqüências de todos os vértices de T. Quando a seqüência
da raiz da árvore T for calculada podemos obter o valor do vertex separation da árvore. Basta
identificar o maior número inteiro contido na seqüência da raiz de T que será o valor do vertex
separation de T.
Para iniciar a execução do algoritmo deve-se escolher arbitrariamente um vértice como
raiz da árvore T. A seqüência da raiz de T é calculada pela recursivamente percorrendo todos
os vértices de T a partir das folhas. Utilizando o Corolário 3.3, a seqüência correspondente a
cada vértice da árvore é calculada combinando as seqüências correspondentes aos seus filhos.
Pela definição, o vertex separation de uma árvore com único vértice é igual a 0. Logo,
numa subárvore enraizada num folha de T a seqüência correspondente a esta folha é (0).
Utilizamos o símbolo “&” para representar a operação de concatenação de duas seqüências.
47
Algoritmo 3.1 (ELLIS et all., 1994)
função vertex_separation (T: árvore): inteiro;
Escolher um vértice u como raiz de T;
vertex_separation := maior elemento de calcula_seqüência(T,u);
função calcula_seqüência(T: árvore; u: raiz): seqüência;
se u é o único vértice da árvore T[u] então
calcula_seqüência = (0);
senão início
para todos os filhos de u, v
i
1 i d faça
s
i
:= calcula_seqüência (T, v
i
);
//calcula a seqüência de u combinando as seqüências s
i
dos d filhos, 1 i d
calcula_seqüência := combina_seqüências(s
1
,..., s
d
)
fim;
função combina_seqüências (s
1
,..., s
d
: seqüência): seqüência;
se existe uma ou mais seqüências contendo o elemento zero então s = (1’)
senão s = (0);
//seja p o maior elemento contido nas seqüências s
1
,..., s
d
para k = 1 até p faça
início
// q o número de seqüências que contém o elemento k, considerando as seqüências s
1
,..., s
d
caso 1: {q 3} s = (k+1’);
caso 2: {q = 2 e pelo menos um elemento k é crítico} s = (k +1’);
caso 3: {q = 2 e nenhum elemento k é crítico} s = (k);
caso 4: {q = 1, elemento k é crítico e k s } s = (k +1’);
caso 5: {q = 1, elemento k é crítico e k s } s = (k) & s;
caso 6: {q = 1, elemento k não é crítico } s = (k’);
fim;
combina_seqüências := s;
A complexidade do Algoritmo 3.1 é da ordem de O(n).
48
A FIG. 3.9 mostra um exemplo das seqüências geradas pelo algoritmo em uma árvore
particular.
)
'
)
)
'
'
'
'
'
'
*%
%
*%
%
*%
%
*%
%
*%
%
%
*%
%
*%
*%
%
%
%
*%
++,-'#.'/01
)
%%
)
*++#2#34
)
2 ++//33567'3%%*%
28
5 ++53567'3'/
++
,#.'333'33567'3
#.'3
939'('3
:;,
)
++#
)
'
'
'
'
%%%
'
'
'
'
'
%%
'
%
'
*++#2#34
'
2 ++//33567'3%*
28
5 ++53567'3'/
#.''
.'(' ++'
,#.'33'3567'%
892'
'
*
:;,
'
*% ++#
'
'
*%
'
++#2#34
'
2 ++//3567'3*%
28
5 ++53567'3'/
#.''
.'(' ++'
,#.'33'3567'%
:;,
'
% ++#
'
'
%%
'
*++#2#34
'
2 ++//33567'3%%
28
5* ++53567'3'/
28
5 ++53567'3'/
++'
'
,#.'333'33567'3
#.'3'
'
939'('3
:;,
'
++#
'
35'#.'%
//3567'%
<
*%
++#2#34
2 ++//33567'3*%
28
5 ++53567'3'/
#.'.'(' ++,#.'33'3567'
:;,
% ++#2#34
28
5 ++53567'3'/
#.'.'(' ++,#.'33'3567'
:;,
% ++#
FIG. 3.9 Execução do Algoritmo 3.1 para cálculo do vertex separation
49
3.3. LAYOUT ÓTIMO
Em (ELLIS et all., 1994) também é apresentada a idéia de um algoritmo para determinar o
layout ótimo para qualquer árvore com complexidade do pior caso de O(n log(n)). No entanto
neste capítulo detalhamos o algoritmo de (SKODINIS, 2003) que resolve o mesmo problema
para árvores com complexidade O(n).
A idéia do algoritmo de (SKODINIS, 2003) consiste em representar o layout ótimo de
uma árvore por uma lista de layouts ótimos (extensíveis ou esparsos) das chamadas partes da
árvore. A esta lista dá-se o nome de coarse layout de uma árvore. O cálculo do layout ótimo
de uma árvore contém semelhanças com o Algoritmo 3.1. Ao invés de calcular e manipular as
seqüências dos vértices da árvore T devemos trabalhar com os coarses layouts das subárvores
de T. Inicialmente são calculados de forma recursiva os coarses layouts das subárvores
enraizadas nos filhos de um vértice u e posteriormente estas listas são combinadas a fim de se
obter o coarse layout de T[u], até que seja calculado o coarse layout de T. Finalizado este
processo, é simples determinar em tempo linear um layout ótimo de T a partir do coarse
layout da árvore T.
Antes da apresentação do algoritmo de (SKODINIS, 2003) será necessário definir alguns
conceitos e lemas utilizados na construção do layout ótimo de uma árvore qualquer.
3.3.1. ÁRVORES SIMPLES, PARTES DE UMA ÁRVORE
Definição 3.5 (SKODINIS, 2003): Uma árvore T é simples se a seqüência s
correspondente a sua raiz possui um único inteiro.
Notação 3.1 (SKODINIS, 2003): Uma árvore simples T é chamada k-simples se o único
inteiro da seqüência s de sua raiz é igual a k, s = (k).
Notação 3.2 (SKODINIS, 2003): Seja T uma árvore k-simples e s a seqüência de sua raiz.
A árvore T é chamada k-simples não-crítica se k é não-crítico em s. Caso contrário T é uma
árvore k-simples crítica.
50
Intuitivamente, uma árvore k-simples não-crítica possui vertex separation igual a k e não
contém vértice k-crítico. De mesma forma, uma árvore k-simples crítica possui vertex
separation igual a k e seu único vértice k-crítico é sua raiz. Verifica-se ainda que uma árvore
0-simples não-crítica é uma árvore de único vértice e que não existe árvore crítica 0-simples.
Definição 3.6 (SKODINIS, 2003): Seja T uma árvore enraizada em u e s = (k
1
, ..., k
p
) a
seqüência de u. Sejam v
1
, ..., v
p
os vértices correspondentes a seqüência s. As partes de T,
ki
,
1 i p, são definidas por:
i)
k1
: subárvore T[v
1
],
ii)
ki
: subárvore T[u; v
1
, ..., v
i-1
] enraizada em v
i
para 1 < i p.
No processo de sequenciamento descrito na Seção 3.2.2.2, as subárvores iterativamente
removidas e a árvore final corresponem às partes de uma árvore. A árvore da FIG. 3.7 pode
ser dividida em 3 partes, a saber, as subárvores T[C], T’[B] e T’’ da FIG. 3.7. De maneira
análoga, a árvore da FIG. 3.8 também possui 3 partes que correspondem às subárvores T[E],
T’[D] e T’’ da FIG. 3.8.
Pelas Definições 3.2, 3.3 e 3.6 conclui-se de forma imediata que toda árvore pode ser
dividida em suas partes, as quais são árvores simples.
Lema 3.1 (SKODINIS, 2003): Seja T uma árvore enraizada em u e s = (k
1
, k
2
, ..., k
p
) a
seqüência de u. Logo, toda parte
ki
, 1 i p, é k
i
-simples. Todas as partes são críticas exceto
kp
que pode ser crítica ou não-crítica.
Pelo Corolário 3.2 podemos concluir que para toda árvore são únicos: a seqüência da raiz,
os vértices correspondentes à seqüência, e as partes da árvore.
Lema 3.2 (SKODINIS, 2003): Para cada árvore a seqüência de sua raiz, os vértices
correspondentes a seqüência, e suas partes são únicas.
51
3.3.2. LAYOUTS EXTENSÍVEIS À ESQUERDA E À DIREITA, COARSE
LAYOUT
Introduzimos nesta seção o conceito de layouts extensíveis à esquerda, layouts extensíveis
à direita e layouts esparsos. Será mostrado que toda árvore k-simples não-crítica possui
ambos, layout extensível à esquerda e layout extensível à direita. De maneira similar mostra-
se que toda árvore k-simples crítica possui um layout esparso. Finalmente define-se o coarse
layout de uma árvore com uma lista de layouts (extensíveis e esparsos) das partes da árvore.
Intuitivamente, L é um layout extensível à esquerda se o vertex separation de L (a maior
cardinalidade dos conjuntos ativos de L) não é aumentado quando se adiciona uma aresta
entre a raiz u e um novo vértice w à esquerda de L. Da mesma forma L é um layout extensível
à direita se o vertex separation de L (a maior cardinalidade de conjuntos ativos de L) não é
aumentado quando se adiciona uma aresta entre a raiz u e um novo vértice w à direita de L.
A seguir apresentamos a definição formal de layout extensível. Utilizamos o símbolo “&”
para indicar a operação de concatenação de layouts. Por exemplo: sejam L um layout qualquer
de n vértices e w um vértice que não está em L. A operação (w)&L = L’ indica que w estará na
primeira posição de L’, L’(1) = w, e que os vértices de L serão colocados em L’ a partir da
segunda posição, L’(i+1) = L(i), 1
i n.
Dado uma árvore T, seja T
w
uma árvore obtida adicionando-se em T um novo vértice w e
uma nova aresta entre w e a raiz de T.
Definição 3.7 (SKODINIS, 2003): Seja L um layout da árvore T. Se T é uma árvore de
único vértice então L é um layout extensível à esquerda e extensível à direita. Caso contrário,
L é um layout extensível à esquerda se vs
(w)&L
(T
w
) = vs
L
(T), e L é um layout extensível à
direita se vs
L&(w)
(T
w
) = vs
L
(T).
A FIG. 3.10 mostra a diferença entre um layout extensível à esquerda, um layout
extensível à direita e um layout usual (não extensível à esquerda e não extensível à direita).
52
FIG. 3.10 (a) um layout extensível à esquerda que não é extensível à direita, (b) um layout
extensível à direita que não é extensível à esquerda, (c) um layout que não é extensível à
esquerda e nem extensível à direita
Intuitivamente, L é um layout esparso se nenhum vértice à esquerda de u em L é
adjacente a algum vértice à direita de u em L. Formalmente:
Definição 3.8 (SKODINIS, 2003): Seja L um layout da árvore T enraizada em u. L é um
layout esparso se nenhum par de vértices v e w em T verificando L(v) < L(u) < L(w) são
adjacentes na árvore T.
53
A FIG. 3.11 mostra a diferença entre layouts esparsos e não esparsos.
FIG. 3.11 (a) Um layout esparso de T, (b) um layout que não é esparso
A seguir são apresentados resultados mostrando em quais condições pode ser garantida a
existência de layout extensível ou esparso em função da criticidade de uma árvore k-simples.
Antes introduzimos dois lemas preliminares:
Lema 3.3 (SKODINIS, 2003): Seja T uma árvore k-simples não-crítica enraizada em u.
Então no máximo uma subárvore de u em T é k-simples não-crítica e todas as demais
subárvores possuem vertex separation com valor máximo igual a k-1.
Lema 3.4 (SKODINIS, 2003): Seja T uma árvore k-simples crítica enraizada em u. Então
exatamente duas subárvores de u em T são k-simples não-críticas e todas as demais subárvores
possuem vertex separation no máximo igual a k-1.
O próximo lema garante que toda árvore k-simples não-crítica possui um layout ótimo
extensível à esquerda e um layout ótimo extensível à direita.
Lema 3.5 (SKODINIS, 2003): Toda árvore T k-simples não-crítica possui um layout
ótimo extensível à esquerda, esquerdoL (T), e um layout ótimo extensível à direita, direitoL
(T).
54
O Lema 3.5 sugere um esquema de construção de layouts ótimos extensíveis à esquerda e
extensíveis à direita de uma árvore k-simples não-crítica utilizando os layouts ótimos de suas
subárvores. Podemos então enunciar o Lema 3.6:
Lema 3.6 (SKODINIS, 2003): Seja T uma árvore k-simples não-crítica enraizada em u e
u
1
, ..., u
d
os filhos de u.
a) Se u não possui subárvore k-simples não-crítica então
esquerdoL (T) = direitoL (T)= (u) & L
1
& L
2
& ... & L
d
é um layout extensível à esquerda e à direita de T, onde L
1
, ..., L
d
são layouts ótimos das
subárvores T[u
1
], ..., T[u
d
].
b) Se u possui subárvore k-simples não-crítica T[u
1
] então
esquerdoL (T) = (u) & L
2
& ... & L
d
& esquerdoL (T[u
1
])
é um layout extensível à esquerda e
direitoL (T) = direitoL (T[u
1
]) & (u) & L
2
& ... & L
d
é um layout extensível à direita de T, onde esquerdoL (T[u
1
]) e direitoL (T[u
1
]) são layouts
extensíveis à esquerda e à direita de T[u
1
] e L
2
, ..., L
d
são layouts ótimos das subárvores T[u
2
],
..., T[u
d
].
A FIG. 3.12 mostra a utilização do Lema 3.6 em duas árvores 2-simples não-críticas, T e
T’. A primeira árvore T é enraizada no vértice u. Nenhuma das subárvores de u, T[v
1
], T[v
2
] ou
T[v
3
], é 2-simples não-crítica, portanto pela parte (a) do Lema 3.6 temos esquerdoL (T) =
direitoL (T) = (u) & (v
1
, v
4
) & (v
2
, v
5
) & (v
3
, v
6
), ou seja, (u, v
1
, v
4
, v
2
, v
5
, v
3
, v
6
) é um layout
extensível à esquerda e à direita de T. A segunda árvore T’ possui raiz w. O vértice w possui
subárvore 2-simples não-crítica, T’[u]. Logo, pela parte (b) do Lema 3.6 temos esquerdoL (T’)
= (w) & (u, v
1
, v
4
, v
2
, v
5
, v
3
, v
6
) e direitoL (T’) = (u, v
1
, v
4
, v
2
, v
5
, v
3
, v
6
) & (w). Ou seja, (w,u,
u, v
1
, v
4
, v
2
, v
5
, v
3
, v
6
) é um layout extensível à esquerda de T’ e (u, v
1
, v
4
, v
2
, v
5
, v
3
, v
6
, w) é um
layout extensível à direita de T’.
55
FIG. 3.12 Determinação dos layouts extensíveis à esquerda e à direita de duas árvores
utilizando o Lema 3.6
Lema 3.7 (SKODINIS, 2003): Toda árvore T k-simples crítica possui um layout ótimo
esparso, esparsoL(T).
O Lema 3.7 determina um processo de construção para um layout ótimo esparso de uma
árvore k-simples crítica utilizando os layouts ótimos de suas subárvores. Portanto pode-se
concluir o Lema 3.8:
Lema 3.8 (SKODINIS, 2003): Seja T uma árvore k-simples crítica enraizada em u, u
1
, ...,
u
d
filhos de u e T[u
1
] e T[u
d
] subárvores k-simples não-críticas de u. Então:
esparsoL (T) = direitoL (T[u
1
]) & (u) & L
2
& L
3
& ... & L
d-1
& esquerdoL (T[u
d
])
é um layout ótimo esparso de T, onde direitoL (T[u
1
])
é um layout extensível à direita de
T[u
1
], esquerdoL (T[u
d
]) é um layout extensível à esquerda de T[u
d
], e L
2
, ..., L
d-1
são layouts
ótimos das subárvores T[u
2
], ..., T[u
d-1
].
A FIG. 3.13 ilustra o Lema 3.8 numa árvore T enraizada no vértice u. T é 1-simples
crítica com T[v
1
] e T[v
3
] subárvores 1-simples não-críticas do vértice u. Logo pelo Lema 3.8
56
temos esparsoL (T) = (v
1
, v
4
) & (u) & (v
3
) & (v
2
, v
5
) = (v
1
, v
4
, u, v
3
, v
2
, v
5
) é um layout esparso
de T.
FIG. 3.13 Determinação do layout esparso da árvore T utilizando o Lema 3.8
A seguir será apresentada a definição de coarse layout de uma árvore, que consiste de
uma lista de layouts ótimos (extensíveis ou esparsos) das partes da árvore. Será utilizada a
seguinte notação:
Notação 3.3 (SKODINIS, 2003): Seja T uma árvore e
ki
uma parte k
i
-simples de T. Se
ki
é não-crítica então esquerdo (
ki
) denota um layout ótimo extensível à esquerda, e
direito (
ki
) um layout ótimo extensível à direita de
ki .
Se
ki
é crítico então esparso
(
ki
)
denota um layout ótimo esparso de
ki .
Definição 3.9 (SKODINIS, 2003): Seja T uma árvore enraizada em u e s = (k
1
, k
2
, ..., k
p
) a
seqüência de u. O coarse layout de T é definido como:
i) coarse = ( esparso (
k1
), esparso (
k2
),..., esparso (
kp
) ) se k
p
é crítico em s e
ii) coarse = ( esparso (
k1
), esparso (
k2
),..., esparso (
k(p-1)
) , ( esquerdo (
kp
) , direito
(
kp
) ) ) caso contrário.
Calcularemos a seguir o coarse layout da árvore T da FIG. 3.7. A árvore T possui raiz A
com seqüência s = (2,1,0), e {C,B,A} o conjunto dos vértices correspondentes a s. As partes
de T são
2
= T[C],
1
= T’[B] e
0
= T’’. Segundo a Definição 3.9 temos:
coarse = ( esparso (
2
), esparso (
1
), ( esquerdo (
0
) , direito (
0
) ) ) é o coarse
layout da árvore T da FIG. 3.7. Resta então calcular cada componente deste coarse layout.
57
A parte
2
de T é uma árvore simples 2-crítica então pelo Lema 3.8 temos esparso (
2
) =
direitoL (
2
[I])
& (C) & esquerdoL (
2
[J]). Pelo Lema 3.6(a) temos direitoL (
2
[I]) = (I) &
(K,Q) & (L,R) & (M,S) = (I,K,Q,L,R,M,S). Ainda pelo Lema 3.6(a) temos esquerdoL (
2
[J])
= (J) & (N,T) & (O,U) & (P,V) = (J,N,T,O,U,P,V). Logo, esparso (
2
) = (I, K,Q,L,R,M,S) &
(C) & (J, N,T,O,U,P,V) = (I,K,Q,L,R,M,S,C,J,N,T,O,U,P,V).
A parte
1
de T é uma árvore simples 1-crítica então pelo Lema 3.8 temos esparso (
1
) =
direitoL (
1
[D])
& (B) & L (
1
[F]) & esquerdoL (
1
[E]), onde L (
1
[F]) é um layout ótimo de
1
[F]. Pelo Lema 3.6(a) temos direitoL (
1
[D]) = (D) & (G) = (D,G) e esquerdoL (
1
[4]) = (4)
& (7) = (4,7). Logo, esparso
(
1
) = (D,G) & (B) & (F) & (E,H) = (D,G,B,F,E,H).
Portanto coarse = ( (I,K,Q,L,R,M,S,C,J,N,T,O,U,P,V), (D,G,B,F,E,H), (A,A) ) é o coarse
layout da árvore T da FIG. 3.7.
3.3.3. DETERMINAÇÃO DE UM LAYOUT ÓTIMO A PARTIR DO COARSE
LAYOUT
Uma vez calculados os coarses layouts de todos os vértices de uma dada árvore T, pode-
se determinar de forma eficiente o layout ótimo utilizando o coarse layout da raiz de T. Será
mostrado a seguir como realizar este cálculo, uma vez que o coarse layout nada mais é que
uma representação flexível de um layout ótimo. Introduzimos a seguir alguns conceitos novos.
Definição 3.10 (SKODINIS, 2003): O foco de um layout L é um vértice que divide L em
duas sublistas, pre(L) e suf(L). O prefixo de L, pre(L), consiste do foco e dos vértices de L que
estão à esquerda do foco. O sufixo de L, suf(L), consiste dos vértices de L que estão a direita
do foco.
Dado dois layouts L e L’ e seus respectivos focos, o layout resultante da operação L L’
é definido por L L’ = pre(L) & L’ & suf(L), sendo o foco de L L’ igual ao foco de L’.
Deve-se destacar que a operação é associativa mas não comutativa e será aplicada somente
em layouts de árvores simples.
O foco do layout de uma árvore simples é definido como sendo sua raiz.
O próximo lema define a construção de um layout ótimo de uma árvore a partir de seu
coarse layout e da operação . Intuitivamente um layout ótimo é obtido inserindo o segundo
58
layout à esquerda da raiz do primeiro layout, o terceiro layout à direita da raiz do segundo
layout e assim sucessivamente até que o último layout, esparso (
kp
) ou esquerdo (
kp
),
dependendo da criticidade da última parte de T seja inserido à direita da raiz do último e único
layout.
Lema 3.9 (SKODINIS, 2003): Seja T uma árvore enraizada em u e s = (k
1
, k
2
, ..., k
p
) a
seqüência de u.
i) Se k
p
é crítico em s então L = esparso (
k1
) esparso (
k2
) ... esparso (
kp
) é um
layout ótimo de T;
ii) Se k
p
é não-crítico em s então L = esparso (
k1
) ... esparso (
k(p-1)
) esquerdo (
kp
)
é um layout ótimo de T.
Calcularemos agora um layout ótimo da árvore T da FIG. 3.7 a partir do coarse layout de
T. A árvore T possui raiz A com seqüência s = (2,1,0), e {C,B,A} o conjunto dos vértices
correspondentes a s. As partes de T são
2
= T[C],
1
= T’[B] e
0
= T’’. O coarse layout de T
é dado por coarse = ((I,K,Q,L,R,M,S,C,J,N,T,O,U,P,N), (D,G,B,F,E,H), (A,A)). Segundo o
Lema 3.9 um layout ótimo de T é dado por L = esparso (
2
) esparso (
1
) esquerdo
(
0
) = ( (I,K,Q,L,R,M,S,C,J,N,T,O,U,P,N) (D,G,B,F,E,H) (A), cujos focos (vértices
sublinhados) são C, B e A respectivamente. Vamos resolver a primeira operação
(I,K,Q,L,R,M,S,C,J,N,T,O,U,P,N) (D,G,B,F,E,H) = (I,K,Q,L,R,M,S,C) & (D,G,B,F,E,H) &
(J,N,T,O,U,P,N) = (I,K,Q,L,R,M,S,C,D,G,B,F,E,H,J,N,T,O,U,P,N). Agora resolvendo a
segunda operação L = (I,K,Q,L,R,M,S,C,D,G,B,F,E,H,J,N,T,O,U,P,N) (A) =
(I,K,Q,L,R,M,S,C,D,G,B,A,F,E,H,J,N,T,O,U,P,N) temos um layout ótimo da árvore T da FIG.
3.7.
3.3.4. CONSTRUÇÃO DE UM COARSE LAYOUT
Nesta subseção será apresentado um procedimento para calcular um coarse layout de uma
árvore utilizando-se os coarses layouts de suas subárvores. O procedimento é a base do
algoritmo linear para determinação do layout ótimo de árvores em geral que será descrito na
Seção 3.3.5.
59
Lema 3.10 (SKODINIS, 2003): Seja T uma árvore enraizada em u e s = (k
1
, k
2
, ..., k
p
) a
sequência de u e sejam u
1
, ..., u
d
os filhos de u.
i) As partes
k1
, ...,
p-1
de T são exatamente as partes de T[u
1
], ..., T[u
d
] com vertex
separation maiores que k
p
;
ii) Nenhuma subárvore T[u
i
], 1 i d, possui uma parte k
p
-simples crítica.
O lema a seguir mostra como obter os primeiros p-1 componentes do coarse layout de uma
árvore.
Lema 3.11 (SKODINIS, 2003): Seja T uma árvore enraizada em u e s = (k
1
, k
2
, ..., k
p
) a
seqüência de u. Sejam u
1
, ..., u
d
os filhos de u e C
1
, ..., C
d
os coarses layouts das subárvores de
u. Os componentes de C
1
, ..., C
d
com vertex separation maiores que k
p
são os primeiros p-1
componentes de um coarse layout de T.
Para construir corretamente o coarse layout de T, os primeiros p-1 componentes do coarse
layout de T determinado no Lema 3.11, devem estar ordenados pelos seus valores de vertex
separations. Resta apenas mostrar como calcular o último (p) componente do coarse layout de
T, que pode ser um layout esparso (esparso
(
kp
)) ou um layout extensível (esquerdo (
kp
) ou
direito (
kp
)). Optou-se por apresentar a prova do próximo lema por este conter detalhes de
construção do último componente p do coarse layout de T que serão utilizados no Algoritmo
3.2.
Lema 3.12 (SKODINIS, 2003): Sejam T uma árvore enraizada em u, s = (k
1
, k
2
, ..., k
p
) a
seqüência de u e u
1
, ..., u
d
os filhos de u. Para 1 i d, seja C’ a lista obtida removendo do
coarse layout de T[u
i
] todos os componentes com vertex separation maior que k
p
. Se o último
componente k
p
de s, a informação de criticidade de k
p
em s, e as listas C’
1
, ..., C’
d
forem
conhecidas então o último componente de um coarse layout de T pode ser calculado.
Prova:
Pelo Lema 3.9, as listas C’
1
, ..., C’
d
são coarses layouts das subárvores de u em
p
.
Existem dois casos a considerar.
60
caso 1.
kp
é não-crítico.
Pela Definição 3.9, será necessário calcular esquerdo (
kp
) e direito (
kp
). Pelo Lema
3.3,
kp
possui no máximo uma subárvore k
p
-simples não-crítica, dita
kp
[u
1
]. Todas as outras
subárvores possuem vertex separation no máximo igual a k
p-1
. Pelo Lema 3.6, para o cálculo
de esquerdo (
kp
) e direito (
kp
)
necessita-se apenas dos layouts ótimos extensíveis à
esquerda, à direita de
kp
[u
1
] e os layouts ótimos das outras subárvores
kp
[u
i
], 2 i d, caso
existam. Os layouts ótimos extensíveis de
kp
[u
1
] encontram-se no único componente da lista
C’
1
e os layouts ótimos das outras subárvores podem ser construídos a partir das listas C’
i
, 2
i d, utilizando-se o Lema 3.9.
caso 2.
kp
é crítico.
Pela Definição 3.9, será necessário calcular um layout ótimo esparso esparso
(
kp
) de
kp
.Pelo Lema 3.4
kp
possui duas subárvores k
p
-simples não-críticas, ditas
kp
[u
1
] e
kp
[u
d
] e
todas as outras subárvores possuem vertex separation no máximo igual a k
p-1
. Pelo Lema 3.8,
para o cálculo de esparso (
kp
) necessita-se apenas de um layout ótimo extensível à direita de
kp
[u
1
], um layout ótimo extensível à esquerda de
kp
[u
d
] e os layouts ótimos das outras
subárvores
kp
[u
j
], 2 j d-1, caso existam. Os layouts ótimos extensíveis estão nas
componentes de C’
1
e C’
d
. Os layouts ótimos das outras subárvores podem ser calculados a
partir das listas C’
j
, 2 j d-1, utilizando-se o Lema 3.9.
De acordo com os Lemas 3.9, 3.11 e 3.12 pode-se calcular um coarse layout de uma
árvore utilizando-se os coarses layouts das subárvores correspondentes. Resumindo os
resultados obtidos: primeiro deve ser construído um coarse layout de uma árvore T utilizando
os Lemas 3.11 e 3.12, em seguida este coarse layout será utilizado para determinar um layout
ótimo para a árvore T usando o Lema 3.9.
3.3.5. ALGORITMO DE SKODINIS
O algoritmo proposto por (SKODINIS, 2003) determina em tempo linear o layout ótimo
para árvores gerais. A idéia é encontrar os coarses layouts de todas as subárvores até que o
coarse layout da árvore T seja calculado. A partir daí basta efetuar a operação conforme o
Lema 3.9 para obter o layout ótimo de T a partir do seu coarse layout.
61
Para executar o algoritmo deve-se escolher inicialmente um vértice arbitrário u como raiz
da árvore T. O coarse layout de T é calculado recursivamente da seguinte maneira: primeiro
calculam-se os coarses layouts das subárvores enraizadas nos filhos de T[v] e posteriormente
pelos Lemas 3.11 e 3.12 é realizada uma combinação destes coarses layouts a fim de
determinar os componentes do coarse layout de T[v]. O procedimento termina quando é
obtido o coarse layout de T[u], onde u é a raiz de T.
Pela definição, o coarse layout de uma subárvore contendo um único vértice v é formado
por um único componente (o próprio vértice), ou seja, coarse layout de T[v] = (v). O algoritmo
utiliza duas operações, “+” e “&”, explicadas a seguir:
<coarse> = + <layout>: esta operação adiciona um layout a um coarse,
<layout> = <layout
1
> & <layout
2
>: concatenação dos layouts <layout
1
> e <layout
2
>
resultando em um novo layout <layout>.
Seja T uma árvore enraizada em u e s = (k
1
, k
2
, ..., k
p-1
, k
p
) a seqüência de u. Sejam C
1
, ...,
C
d
os coarses layouts das subárvores de u. Sejam L
1
, ..., L
p
os layouts de um coarse layout e
sejam conhecidas as seqüências e os valores de vertex separation de todos os vértices da
árvore T.
Algoritmo 3.2 (SKODINIS, 2003)
função layout_ótimo (T: árvore): layout;
Escolher um vértice u como raiz de T;
layout_ótimo := Efetuar operação
entre todos os componentes de calcula_coarse (T, u);
função calcula_coarse (T: árvore; u: vértice): coarse;
se u é o único vértice da árvore T[u] então
calcula_coarse = ( (u) ); // coarse com único componente
senão início
para todos os filhos de u, v
i
1 i d faça C
i
= calcula_coarse (T, v
i
);
//calcula o coarse layout de u combinando os coarses layouts C
i
de seus d filhos, 1 i d
calcula_coarse = combina_coarses (C
1
, ..., C
d
, u);
fim;
62
função combina_coarses (C
1
,..., C
d
: coarse, u: vértice): coarse;
se seqüência(u) possui mais de 1 componente então
combina_coarses = primeiros_componentes (C
1
,..., C
d
,, u);
combina_coarses = + último_componente (C
1
,..., C
d
,, u);
função primeiros_componentes (C
1
,..., C
d
: coarse, u: vértice): coarse;
para todos os C
i
, 1 i d faça
// todos os layouts de um coarse
para todos os L
j
, 1 j < p faça
se vs(L
j
) > vs(u) então primeiros_componentes = + L
j
;
função último_componente (C
1
,..., C
d
: coarse, u: vértice): layout;
// Seja k
p
o último componente da seqüência de u
se ( k
p
é não-crítico ) então
se
kp
possui única subárvore k
p
-simples não-crítica cuja raiz é u
1
//Sejam L
2
... L
d
: layouts ótimos das subárvores
kp
[u
i
], 2 $ i $ d
então último_componente = ( u) & (L
2
) & ...& (L
d
) & (esquerdoL(
kp
[u
1
]);
senão último_componente = ( u) & (L
1
) & (L
2
) & ...& (L
d
);
senão // k
p
é crítico
//sejam u
1
e u
d
as raízes das duas subárvores k
p
-simples não-críticas de
kp
//Sejam L
2
... L
d-1
: layouts ótimos das subárvores
kp
[u
i
], 2 $ i $ d-1
último_componente = (direitoL (
kp
[u
1
])) & ( u) & (L
2
) & ...& (L
d-1
) & (esquerdoL
(
kp
[u
d
]));
A complexidade do Algoritmo 3.2 é da ordem de O(n) (SKODINIS, 2003). Este algoritmo
foi implementado na linguagem de programação Java
TM
2. Detalhes da implementação serão
apresentados no Apêndice.
A FIG. 3.14 mostra uma árvore T e os coarses layouts das subárvores obtidas pela
execução do Algoritmo 3.2 para raiz u. Os vértices sublinhados indicam os focos respectivos
de cada layout. O coarse layout da raiz de T é dado por (u , v
8
, v
9
, v
12
, v
10
, v
13
, v
11
, v
14
, v
3
,
v
6
, v
1
, v
2
, v
4
, v
5
, v
7
, v
15
, v
19
, v
16
, v
21
, v
18
, v
20
, v
17
) que pela Definição 3.9 corresponde ao
esparso (
1
). Pelo Lema 3.9 um layout ótimo de T é dado por L = esparso (
1
) = (u , v
8
, v
9
, v
12
, v
10
, v
13
, v
11
, v
14
, v
3
, v
6
, v
1
, v
2
, v
4
, v
5
, v
7
, v
15
, v
19
, v
16
, v
21
, v
18
, v
20
, v
17
).
63
=
*
>
?
?
>
*
=
=
>
*
?
>
=
*
?
?
=
>
*
>
=
*
?
@
=
>
*
>
=
*
?
>
=
*
?
=
>
*
>
*
?
@
=
=
>
*
>
=
*
?
@
?
>
*
?
=
>
*
>
=
*
?
@
?
@
?
?
>
*
?
>
*
FIG. 3.14 Árvore T e os coarse layouts de cada subárvore de T.
64
4. EDGE SEARCH NUMBER E PLANO DE BUSCA ÓTIMO PARA ÁRVORES
4.1. INTRODUÇÃO
Neste capítulo será tratado o problema edge search number e a determinação do plano de
busca ótimo para a classe particular das árvores.
A Seção 4.2 trata dos algoritmos de Meggido para calcular o parâmetro edge search
number e o plano de busca ótimo para árvores. A Subseção 4.2.1 mostra alguns conceitos
apresentados por Meggido, úteis para resolver os problemas de edge search number e plano de
busca ótimo de uma árvore. Primeiramente define-se o conceito de avenida de uma árvore T,
usado para pesquisar ou limpar uma árvore com esn(T) guardas. Em seguida apresenta-se o
Lema 4.1 de Parsons (MEGIDDO et all., 1988) e por fim uma classificação de árvore em 4
tipos dependendo da localização de sua raiz. Uma vez discutidos todos estes conceitos
preliminares é apresentado na Subseção 4.2.2 o algoritmo linear para calcular o edge search
number de uma árvore e na Subseção 4.2.3 a versão de Meggido para calcular o plano de
busca ótimo de árvores em tempo O(n log n).
Na Seção 4.3 são formalizados os algoritmos para resolver os problemas de edge search
number e plano de busca ótimo para árvores segundo Ellis. Na Subseção 4.3.1 introduzem-se
inicialmente os conceitos de 2-expansão e layout padrão de um grafo. Também é apresentado
um importante teorema de Ellis que revela que o edge search number de um grafo é igual ao
vertex separation de seu grafo 2-expansão. A Subseção 4.3.2 apresenta então o algoritmo
linear de Ellis que calcula o edge search number de uma árvore a partir do cálculo do vertex
separation de sua árvore 2-expansão. Na Subseção 4.3.3 inclui o algoritmo proposto por Ellis
para determinar um plano de busca ótimo de uma árvore a partir do layout ótimo de sua árvore
2-expansão.
4.2. SOLUÇÃO DE MEGGIDO PARA ÁRVORES
O algoritmo proposto em (MEGIDDO et all., 1988) para resolver o problema do cálculo
do edge search number para o caso particular de árvores é linear e recursivo. Nas próximas
65
subseções serão apresentados os conceitos necessários para descrever os algoritmos que
determinam o edge search number de uma árvore e o plano de busca ótimo propostos em
(MEGIDDO et all., 1988).
4.2.1. CONCEITOS INICIAIS
Definição 4.1 (MEGIDDO et all., 1988): Dada uma árvore T = (V,E) e um vértice v V,
dizemos que uma subárvore T’ de T é um ramo em v, se v possui grau 1 em T’ e T’ é uma
subárvore maximal com esta propriedade.
A FIG. 4.1. apresenta os ramos em A da árvore T .
FIG. 4.1. Ramos de uma árvore T.
O Lema seguinte provado por Parsons em 1976 (MEGIDDO et all., 1988) introduz a
idéia básica para a construção do algoritmo que determina o edge search number de uma
árvore.
Lema 4.1 (MEGIDDO et all., 1988): Para qualquer árvore T e inteiro k A 1, esn(T) A k +
1 se e somente se T possui um vértice v para o qual existam 3 ou mais ramos com edge
search number maior ou igual a k.
Podemos reescrever o lema anterior da seguinte forma:
Lema 4.2 (MEGIDDO et all., 1988): Para qualquer árvore T e inteiro k A 1, esn(T) < k +
1 se e somente se todos os vértices de T possuem, no máximo, 2 ramos com edge search
number maior ou igual a k.
66
O Lema 4.2 conduz ao conceito de avenida de uma árvore. Intuitivamente, a avenida de
uma árvore T é um caminho v
1
, v
2
, ..., v
r
para r 2, tal que exista um plano de busca que
limpe a árvore T utilizando esn(T) guardas da seguinte forma:
1) colocar um guarda em v
1
,
2) limpar os ramos em v
1
utilizando os esn(T) - 1 guardas restantes;
3) movimentar guarda para o próximo vértice da avenida;
4) repetir os passos 2 e 3 até que o último vértice v
r
da avenida seja visitado.
A definição formal do conceito de avenida é dado a seguir.
Definição 4.2 (MEGIDDO et all., 1988): Uma avenida de T é um caminho v
1
, v
2
, ..., v
r
com r 2 se:
v
1
tiver somente um ramo que contem v
2
com edge search number igual a esn(T);
v
r
tiver somente um ramo que contem v
r-1
com edge search number igual a esn(T);
e para cada j com 2 j r – 1;
v
j
tiver somente um ramo que contem v
j-1
com edge search number igual a esn(T);
v
j
tiver somente um ramo que contem v
j+1
com edge search number igual a esn(T).
Observamos então que uma avenida pode ser usada para pesquisar uma árvore T com
esn(T) guardas.
Definição 4.3 (MEGIDDO et all., 1988): Um vértice v de uma árvore T é chamado centro
de T, se todos os ramos em v possuem edge search number menor que esn(T).
Um vértice centro corresponde a uma avenida de tamanho zero, ou seja, a uma avenida
que consiste de um caminho formado por um único vértice.
Lema 4.3 (MEGIDDO et all., 1988): Se esn(T) = s, então:
i) T possui um vértice v tal que todos os ramos em v possuem edge search number menor
que s, ou
ii) T tem uma única avenida.
67
Consideremos que toda árvore possui um vértice denominado raiz. O valor de edge search
number de uma árvore é independente da escolha da raiz.
Pelo Lema 4.3, as árvores enraizadas podem ser classificadas em 4 tipos, dependendo da
localização da raiz.
Definição 4.4 (MEGIDDO et all., 1988): Seja T uma árvore enraizada. A árvore T pode
ser de um dos 4 tipos a seguir:
tipo H: a raiz r coincide com o centro de T (avenida de tamanho zero), FIG. 4.2(a);
tipo E: a raiz r está em um ramo de uma das extremidades v
1
ou v
r
da avenida de T,
neste caso é necessário que v
1
v
r
, o que implica que a avenida tem tamanho diferente
de zero, FIG. 4.2(b);
tipo I: a raiz r é um nó interior v
2
, ..., v
r-1
da avenida de T, FIG. 4.2(c);
tipo M: a raiz r está no meio de um ramo, e não na avenida, de um nó interior da
avenida de T. Tal ramo tem quantidade de guardas menor que esn(T), FIG. 4.2(d).
FIG. 4.2 Árvores genéricas dos tipos H, E, I e M.
Definição 4.5 (MEGIDDO et all., 1988): Para uma árvore de tipo M, denominamos de
árvore-M de T ao ramo no qual encontra-se a raiz.
Notamos que o edge search number da árvore-M de T é menor que o edge search
number de T, esn(árvore-M) < esn(T).
4.2.2. ALGORITMO DE MEGGIDO PARA CALCULAR O EDGE SEARCH
NUMBER
Seja T uma árvore enraizada, cuja raiz foi escolhida arbitrariamente. O Algoritmo 4.1
trabalha recursivamente para preencher a estrutura de dados info associada à árvore T. A
68
estrutura info é formada pelos campos [tipo, sn, M-info]. Os três campos da estrutura são
descritos a seguir:
tipo: o tipo de T, sendo os valores possíveis H, E, I ou M;
sn: o edge search number de T;
M-info: se o tipo da árvore for M então M-info é o registro de informação info (árvore-M
de T), caso contrário (se for tipo H, E ou I) M-info assume valor nulo.
Algoritmo 4.1 (MEGIDDO et all., 1988)
função edge_search_number_Meggido (T: árvore): inteiro;
Escolher uma raiz r arbitrária em T;
calcula_info(T, r);
edge_search_number_Meggido = sn;
função calcula_info(T: árvore, r: raiz): info;
se grau(r) = 1 então
se T é apenas uma aresta então calcula_info = [E,1,nulo];
senão
// Obter T’ mudando a raiz de T do nó r para um nó vizinho r’ qualquer de r;
info(T’) = calcula_info(T’, r’);
calcula_info = enraizar ( info(T’) );
senão //grau(r)
2
// Dividir T em duas árvores T
1
e T
2
: ambas enraizadas em r, sem nenhum outro nó em
// comum e tendo ao menos uma aresta cada uma. As duas árvores podem ser
// escolhidas arbitrariamente, sendo T
1
T
2
= T
info(T
1
) = calcula_info(T
1
, r);
info(T
2
) = calcula_info(T
2
, r);
calcula_info = fusão ( info(T
1
), info(T
2
) );
Inicialmente escolhemos um vértice r como raiz de T. O objetivo do algoritmo é dividir
recursivamente a árvore T em duas subárvores T
1
e T
2
, ambas com raiz r e sem nenhum outro
vértice em comum, tal que T
1
T
2
= T, até chegar numa subárvore de uma única aresta. Neste
69
caso info pode ser determinado pelo algoritmo sem necessidade das rotinas auxiliares enraizar
ou fusão.
Quando a subárvore gerada possuir mais de uma aresta, mas sua raiz r encontrar-se em
uma folha, grau(r) = 1, então não será possível dividi-la em duas subárvores. Neste caso,
desloca-se a raiz r para um vértice vizinho a r, gerando-se assim uma árvore T’ idêntica a
original T, exceto pela localização da raiz, que agora pode ser dividida.
No retorno das chamadas recursivas, aplica-se a rotina enraizar(T’) para determinar o
registro info da árvore que gerou T’ e a rotina fusão(T
1
,T
2
) para determinar o registro info da
árvore que foi dividida para gerar T
1
e T
2
. Este procedimento será repetido determinar o valor
do registro info(T) = [tipo, sn, M-info] da árvore original, onde sn será o valor do edge search
number da árvore T. A escolha de raízes iniciais diferentes para uma mesma árvore T não
altera o valor do edge search number determinado pelo algoritmo.
A rotina enraizar(T’) apenas modifica o tipo de T, pois T e T’ são árvores idênticas, exceto
pela localização da raiz, portanto a quantidade sn de guardas de T é igual a quantidade sn’ de
guardas de T’. Consideremos então info(T) = [tipo, sn, M-info] e info(T’) = [tipo’, sn’, M-
info’] .
função enraizar ( info(T’): info ): info;
M-info = M-info’;
se tipo’ = E ou tipo’ = H então tipo = E;
se tipo’ = I e sn’ = 1 então tipo = E;
senão tipo = M;
M-info = [E,1,nulo];
se tipo’ = M então tipo = M;
M-info = enraizar (M-info’);
enraizar = [tipo’, sn’, M-info];
O Lema 4.4 descreve o funcionamento da rotina enraizar.
Lema 4.4. (MEGIDDO et all., 1988): Para qualquer árvore T que contenha mais de uma
aresta, o algoritmo enraizar computa corretamente o registro info(T) a partir de info(T’), sendo
T a árvore enraizada em uma folha r e T’ obtida a partir de T pela mudança da raiz r para um
vizinho de r.
70
A rotina fusão concatena duas árvores T
1
e T
2
, com registros info(T
1
) = [tipo
1
, sn
1
, M-
info
1
] e info(T
2
) = [tipo
2
, sn
2
, M-info
2
] para determinar info(T) = [tipo, sn, M-info]. Sem perda
de generalidade, podemos assumir que sn
1
sn
2
. Temos então 5 casos possíveis quando sn
1
=
sn
2
e 2 casos possíveis quando sn
1
> sn
2
que são enumerados na função fusão a seguir.
função fusão (info(T
1
): info, info(T
2
):info) : info(T);
se sn
1
= sn
2
então
se (tipo
1
= tipo
2
= H então fusão = [H, sn
1
, nulo]; // caso 1
se (tipo
1
= H e tipo
2
= E) então fusão = [E, sn
1
, nulo]; // caso 2
se (tipo
1
= tipo
2
= E) então fusão = [I, sn
1
, nulo]; // caso 3
se (tipo
1
= I e tipo
2
= H) então fusão = [I, sn
1
, nulo]; // caso 4
se (tipo
1
= M) ou (tipo
2
= M) ou (tipo
1
= tipo
2
= I) ou
(tipo
1
= I e tipo
2
= E) então fusão = [H, sn
1
+ 1, nulo]; // caso 5
senão // sn
1
> sn
2
se (tipo
1
= H ou E ou I) então fusão = [tipo
1
, sn
1
, nulo]; // caso 6
se (tipo
1
= M) então //caso 7
info(T’) = fusão (M-info
1
, info(T
2
));
se sn’ < sn
1
então fusão = [M, sn
1
, info(T’)];
se sn’ = sn
1
então fusão = [H, sn
1
+1, nulo];
O Lema 4.5 descreve o funcionamento da rotina fusão.
Lema 4.5. (MEGIDDO et all., 1988): O algoritmo fusão determina corretamente o
registro info(T) a partir de info(T
1
) e info(T
2
), onde T é uma árvore enraizada em r, e T
1
e T
2
são árvores enraizadas em r, disjuntas com exceção do nó r e cuja união resulta em T.
A seguir é apresentada a análise dos 7 casos descritos na rotina fusão, com os respectivos
exemplos.
caso 1. Ambas as raízes são centro de suas árvores, e a união destas é uma árvore na qual
todos os ramos tem quantidade de guardas menor que sn
1
= sn
2
. Uma vez que a quantidade de
71
guardas não pode diminuir, concluímos que sn = sn
1
é a raiz da nova árvore que também é um
centro, como ilustra a FIG. 4.3.
FIG. 4.3 Caso 1 da rotina fusão.
caso 2. A nova árvore pode ser limpa com sn
1
= sn
2
guardas caminhando ao longo da
avenida de T
2
e descendo pelo ramo que contem a raiz r. T possui uma avenida de tamanho
pelo menos igual a um, com r sendo uma das extremidades, o que indica que seu tipo é E,
como ilustra a FIG. 4.4.
FIG. 4.4 Caso 2 da rotina fusão.
72
caso 3. A avenida de T é o menor caminho que contem as avenidas de T
1
e T
2
, e esta
avenida pode ser usada para limpar T com sn
1
guardas. Já que r é um vértice interior na
avenida, temos que T é do tipo I, como ilustra a FIG. 4.5.
FIG. 4.5 Caso 3 da rotina fusão.
caso 4. A raiz de T
1
é um vértice no interior desta avenida, e após a concatenação com T
2
os ramos fora da avenida para aquela raiz irão todos continuar a possuir uma quantidade de
guardas menor que sn
1
= sn
2
. Portanto, T possui o mesmo registro info(T
1
) = [I, sn
1
,nulo],
como ilustra a FIG. 4.6.
FIG. 4.6 Caso 4 da rotina fusão.
73
caso 5. Seja r’ a raiz de T
1
se tipo
1
= I, ou o vértice mais próximo da raiz de T
1
, na avenida
de T
1
, se tipo
1
= M. É trivial visualizar que r’ é um vértice com três ramos possuindo
quantidade de guardas sn
1
, logo sn
1
+ 1 guardas são necessários para T. Uma vez que sn
1
+ 1
guardas são suficientes e a raiz de T tem apenas ramos com quantidade de guardas menor que
sn
1
+ 1, T é do tipo H e possui quantidade de guardas sn
1
+ 1, como ilustra a FIG. 4.7.
B
0C1
C
D
E
01
B
0E1
DC
E
74
FIG. 4.7 Caso 5 da rotina fusão para: (a) T
1
tipo I e T
2
tipo E, (b) T
1
e T
2
tipo I, (c) T
1
tipo M e
T
2
tipoH.
caso 6. Se tipo
1
= H, então a raiz continua a ter apenas ramos com quantidade de guardas
menor que sn
1
em T, logo T possui quantidade de guardas sn
1
e é do tipo H. Se tipo
1
= E,
então T pode se limpo com sn
1
guardas caminhando ao longo da avenida de T
1
e descer o
ramo que contem r. Portanto T possui uma avenida de tamanho ao menos igual a um, com r
num ramo de um vértice de extremidade (possivelmente seja a própria extremidade), logo T é
do tipo E. Se tipo
1
= I, aplica-se o argumento do Caso 4, logo, T é do tipo I e tem quantidade
de guardas sn
1
, como ilustra a FIG. 4.8.
FIG. 4.8 Caso 6 da rotina fusão
.
75
caso 7. A quantidade de guardas para T depende da quantidade de guardas (T’) da união
da M-tree(T
1
) com T
2
. A quantidade de guardas para T’ não pode se maior que sn
1
, já que M-
tree e T
2
possuem quantidade de guardas menor que s
1
. Se sn’ = esn(T’) < sn
1
, então a avenida
de T é exatamente a mesma que a avenida de T
1
, a mesma quantidade de guardas sn
1
é
suficiente, e T’ é agora a M-tree de T. Se sn’ = sn
1
, então o vértice cabeça do ramo
correspondente a T’ em T possui três ramos com quantidade de guardas sn
1
, logo a quantidade
de guardas para T é pelo menos igual sn
1
+ 1. Além do mais, a raiz r possui apenas ramos com
quantidade de guardas menor que sn
1
+ 1, logo sn
1
+ 1 guardas são suficientes e T é do tipo H,
como ilustra a FIG. 4.9.
FIG. 4.9 Caso 7 da rotina fusão: (a) quando sn’ < sn
1
e (b) quando sn’ = sn
1.
Seguem exemplos da aplicação do algoritmo calcula_info em duas árvores. Na FIG. 4.10
aplica-se o Algoritmo 4.1 na árvore T resultando em info(T) = [E,2,nulo], logo o esn(T) = 2. A
76
FIG. 4.11 apresenta uma outra árvore T com esn(T) = 3, pois o registro info(T) determinado
pelo Algoritmo 4.1 é dado por [H,3,nulo].
FIG. 4.10 Resultado do Algoritmo 4.1 em uma árvore T de esn(T) = 2.
FIG. 4.11 Resultado do Algoritmo 4.1 em uma árvore T de esn(T) = 3.
4.2.3. ALGORITMO DE MEGGIDO PARA DETERMINAR UM PLANO DE
BUSCA ÓTIMO
O algoritmo plano de busca ótimo proposto por (MEGIDDO et all., 1988) determina um
plano de busca em uma árvore T para limpar a árvore utilizando esn(T) guardas. Este
algoritmo trabalha recursivamente invocando uma modificação do Algoritmo 4.1 ao encontrar
um ramo contaminado. O plano de busca de uma árvore pode ser determinado utilizando o
algoritmo proposto por Meggido em tempo O(n log n).
77
Em (MEGIDDO et all., 1988) é proposta uma ligeira modificação no Algoritmo 4.1 a fim
de que este também identifique um caminho em T (que certamente contem uma avenida de T).
A partir deste resultado, o autor apresenta a idéia de como estabelecer um plano de busca
ótimo utilizando o caminho determinado pela alteração no Algoritmo 4.1.
Incluímos em cada registro info o campo path, no qual serão armazenadas as extremidades
do caminho na árvore T. Desta forma o registro info modificado será formado pelos campos
seguintes, info(T) = [tipo, sn, M-info, path], onde path = (a,b) e a, b são vértices de T.
A rotina enraizar do Algoritmo 4.1 não afeta o campo path. Já o procedimento fusão deve
ser modificado. Apresentamos a seguir a função fusão_1, que contempla as atualizações
adequadas do campo path nos 7 casos discutidos na seção anterior. Consideramos path(T) =
(a,b), info(T) = [tipo, sn, M-info, (a,b)], path(T
1
) = (a
1
, b
1
), path(T
2
) = (a
2
, b
2
) e r: raiz de T.
função fusão_1 (info(T
1
): info, info(T
2
):info) : info(T);
se sn
1
= sn
2
então
se (tipo
1
= tipo
2
= H então fusão_1 = [H, sn
1
, nulo, (r, r)]; // caso 1
se (tipo
1
= H e tipo
2
= E) então fusão_1 = [E, sn
1
, nulo, (r, b
2
)]; // caso 2
se (tipo
1
= tipo
2
= E) então fusão_1 = [I, sn
1
, nulo, (a
1
, b
2
)]; // caso 3
se (tipo
1
= I e tipo
2
= H) então fusão_1 = [I, sn
1
, nulo, (a
1
, b
1
)]; // caso 4
se (tipo
1
= M) ou (tipo
2
= M) ou (tipo
1
= tipo
2
= I) ou
(tipo
1
= I e tipo
2
= E) então fusão_1 = [H, sn
1
+ 1, nulo, (r, r)]; // caso 5
senão // sn
1
> sn
2
se (tipo
1
= H ou I) então fusão_1 = [tipo
1
, sn
1
, nulo, (a
1
, b
1
)]; // caso 6
se (tipo
1
= E) então fusão_1 = [tipo
1
, sn
1
, nulo, (a
1
, r)]; // caso 6
se (tipo
1
= M) então //caso 7
info(T’) = fusão_1 (M-info
1
, info(T
2
));
se sn’ < sn
1
então fusão_1 = [M, sn
1
, info(T’), (a
1
, b
1
)];
se sn’ = sn
1
então fusão_1 = [H, sn
1
+1, nulo, (r, r)];
As FIG. 4.12 e FIG. 4.13 ilustram a aplicação do Algoritmo 4.1 utilizando a função
fusão_1 para as árvores das FIG. 4.10 e FIG. 4.11. Nestes dois exemplos são identificados os
caminhos encontrados em cada subárvore.
78
FIG. 4.12 Algoritmo 4.1 com função fusão_1 encontrando path = (B,B).
FIG. 4.13 Algoritmo 4.1 com função fusão_1 encontrando path = (A,A).
Apresentamos agora a idéia geral de como obter um plano de busca ótimo para uma árvore
T utilizando a informação armazenada no campo path(T) previamente calculado pelo
Algoritmo 4.1 utilizando a função fusão_1.
Seja uma árvore T cujo valor path(T) = (a,b). Seja a = u
1
, u
2
, ..., u
p
= b um caminho em T
que une os vértices a e b. As arestas de T que não pertencem ao caminho estão distribuídas
nos ramos T1, T2, ..., Tm, cada qual contendo exatamente um vértice pertencente ao caminho
entre os vértices a e b, e com edge search number no máximo igual a esn(T) – 1 (pois o
caminho contem a avenida de T).
Um plano de busca ótimo de T é obtido colocando um guarda em u
1
e limpando todos os
ramos incidentes em u
1
com os esn(T) – 1 guardas restantes. Em seguida, move-se o guarda
que estava fixo em u
1
para u
2
, e procede-se novamente à limpeza de todos os ramos incidentes
em u
2
usando os esn(T) – 1 guardas restantes; e assim sucessivamente até u
p
.
79
Observamos que o plano de busca ótimo de T pode ser construído pela inclusão de planos
de busca para cada ramo T1, T2, ..., Tm, nos lugares apropriados do plano de busca ótimo de
T.
A TAB. 4.1 mostra um plano de busca ótimo para a árvore da FIG. 4.13 obtido a partir da
aplicação da idéia exposta anteriormente, utilizando um total de 3 guardas.
plano de busca ótimo
guardas
usados
plano de busca ótimo
(cont.)
guardas
usados
colocar 1 guarda em A; 1 mover 1 guarda de G para D;
colocar 1 guarda em C; 2 remover 1 guarda de D; 2
colocar 1 guarda em U; 3 colocar 1 guarda em K; 3
mover 1 guarda de U para R; mover 1 guarda de K para H;
mover 1 guarda de R para C mover 1 guarda de H para D;
remover 1 guarda de C; 2 remover 1 guarda de D; 2
colocar 1 guarda em V; 3 mover 1 guarda de D para B;
mover 1 guarda de V para S; remover 1 guarda de B; 1
mover 1 guarda de S para C; colocar 1 guarda em E; 2
remover 1 guarda de C; 2 colocar 1 guarda em O; 3
colocar 1 guarda em X; 3 mover 1 guarda de O para L;
mover 1 guarda de X para T; mover 1 guarda de L para E;
mover 1 guarda de T para C; remover 1 guarda de E; 2
remover 1 guarda de C; 2 colocar 1 guarda em P; 3
mover 1 guarda de C para A; mover 1 guarda de P para M;
remover 1 guarda de A; 1 mover 1 guarda de M para E;
mover 1 guarda de A para B; remover 1 guarda de E; 2
colocar 1 guarda em D; 2 colocar 1 guarda em Q; 3
80
colocar 1 guarda em I; 3 mover 1 guarda de Q para N;
mover 1 guarda de I para F; mover 1 guarda de N para E;
mover 1 guarda de F para D; remover 1 guarda de E; 2
remover 1 guarda de D; 2 mover 1 guarda de E para B;
colocar 1 guarda em J; 3 remover 1 guarda de B; 1
mover 1 guarda de J para G; remover 1 guarda de B; 0
TAB. 4.1 Plano de busca ótimo para a árvore da FIG. 4.13.
4.3. SOLUÇÃO DE ELLIS PARA ÁRVORES
Foi mostrado na seção anterior como calcular o edge search number de uma árvore
em tempo linear O (n log n) segundo os conceitos e algoritmos de (MEGIDDO et all.,
1988). No entanto apresentaremos nesta seção o procedimento de transformação de um
grafo sugerido por (ELLIS et all., 1994) que possibilita o cálculo do parâmetro edge
search number a partir do vertex separation. No caso particular de árvores, fazendo uma 2-
expansão e usando o Algoritmo 3.1 pode-se obter o valor do edge search number.
4.3.1. TRANSFORMAÇÃO 2-EXPANSÃO, LAYOUT PADRÃO DE UM GRAFO
Introduziremos a seguir alguns conceitos necessários para o desenvolvimento dos
resultados.
Definição 4.6 (ELLIS et all., 1994): Seja o grafo G = (V, E). Denomina-se 2-expansão de
G ao grafo G’ gerado pela substituição de cada aresta e = (x, y)
E por dois novos vértices a
e b, e novas arestas (x,a), (a,b) e (b,y).
Em G’, grafo 2-expansão de um grafo G, existem dois tipos de vértices, os que estão
presentes em G e em G’, denominados vértices originais, e os que foram adicionados para
criar o grafo G’ e portanto existem apenas em G’, denominados vértices adicionados.
81
A FIG. 4.14 mostra um grafo e sua 2-expansão, neste último grafo são diferenciados os
vértices originais dos adicionados.
FIG. 4.14 Árvore 2-expansão de T
Podemos observar que a subdivisão de arestas não altera o edge search number. Portanto
temos o seguinte resultado.
Lema 4.6 (ELLIS et all., 1994): Seja o grafo G’ o grafo 2-expansão de um grafo G
qualquer. Então esn(G) = esn(G’).
Definição 4.7 (ELLIS et all., 1994): Seja G’ a 2-expansão de um grafo G. Um layout Lp é
chamado layout padrão do grafo G’ se, para todas as arestas originais (x, y) e para os vértices
adicionados a e b, Lp(a)
Lp(b) - 1 e, no caso de x e y forem distintos, Lp(a) > Lp(x).
FIG. 4.15 mostra o exemplo de um grafo G com layout padrão e não padrão para sua 2-
expansão G’.
FIG. 4.15 Três layouts padrão para o grafo G e dois layouts não padrão para G.
82
A prova do Lema 4.7 foi incluída neste documento porque mostra como transformar um
layout de um grafo 2-expansão em um layout padrão. Essa transformação é utilizada na
construção do algoritmo para cálculo do plano de busca ótimo que será apresentado no final
desta seção.
Lema 4.7 (ELLIS et all., 1994): Seja G’ o grafo 2-expansão de um grafo G. Se existe um
layout para G’ com vertex separation k então existe um layout padrão para G’ com vertex
separation k.
Prova:
A FIG. 4.16 mostra todas as possíveis posições de a e b com respeito aos vértices
distintos x e y nos quais b precede a, e a precede b, respectivamente. Assume-se que os outros
vértices possam ser posicionados em qualquer lugar.
Das dez possíveis disposições, apenas a oitava e a décima verificam a Definição 4.7. É
imediato constatar que as demais disposições podem ser transformadas na oitava ou na décima
disposições sem aumento do parâmetro vertex separation fazendo um reposicionamento
adequado dos vértices a ou b, da seguinte forma:
#1 pode ser transformado em #7 movimentando b para a posição entre x e y,
#2 pode ser transformado em #8 movimentando b para a posição entre a e y,
#3 pode ser transformado em #8 movimentando b para a posição entre a e y,
#4 pode ser transformado em #3 movimentando a para a posição entre b e y,
#5 pode ser transformado em #10 movimentando b para a posição imediatamente após a,
#6 pode ser transformado em #7 movimentando b para a posição entre x e y,
#7 pode ser transformado em #8 movimentando a para a posição entre x e b,
#9 pode ser transformado em #8 movimentando b para a posição entre a e y.
83
FIG. 4.16 Possíveis posições dos vértices adicionados a e b em relação aos vértices
originais x e y, tal que, de #1 a #5 b precede a, e de #6 a #10 a precede b.
A prova do Teorema 4.1 será incluída a seguir pois apresenta um algoritmo que é
utilizado tanto no final desta seção como no Capítulo 6. A determinação do plano de busca
ótimo para árvores em geral e do plano de busca ótimo para árvores binárias cheias utilizam o
Algoritmo 4.1 para estabelecer a seqüência de movimentos dos guardas na árvore respectiva.
Teorema 4.1 (ELLIS et all., 1994): Seja G um grafo e G’ seu grafo 2-expansão. Então
esn(G) = vs(G’).
Prova:
Seja G’ o grafo 2-expansão de G. Pelo Teorema 2.1, vs(G’) esn(G’). É imediato
verificar que a subdivisão de arestas ocorrida na criação de G’ não altera o valor do edge
search number, sendo assim esn(G) = esn(G’), portanto vs(G’) esn(G).
Para provar que esn(G) vs(G’) mostra-se como construir um plano de busca P’ a partir
de um layout L’ de G’ de tal forma que a quantidade w de guardas utilizados em P’ seja menor
que o vertex separation de L’, ou seja, w vs
L’
(G’). É imediato concluir que esn(G) w e que
vs
L’
(G’) = vs(G’) quando L’ for um layout ótimo de G’. Logo, esn(G) w vs
L’
(G’) = vs(G’),
e portanto tem-se a relação esn(G) vs(G’). O Lema 4.2 garante que existe layout padrão com
vertex separation ótimo, ou seja, existe layout padrão ótimo Lp para G’, logo resta apenas
84
apresentar o Algoritmo 4.2 que determina um plano de busca a partir de um layout ótimo
padrão Lp e provar que este plano utiliza w guardas, tal que w vs
Lp
(G’), ou melhor, w
vs(G’) já que Lp é um layout ótimo do grafo 2-expansão G’.
Algoritmo 4.2 (ELLIS et all., 1994)
procedimento busca2 ( G’, Lp )
para i:=1 até |V| faça
início
x = Lp
-1
(i);
se x é um vértice original
então
se x possui um vizinho colocado à sua esquerda
(1) então mover um guarda de cada um dos vizinhos esquerdos de x até x;
(2) senão colocar um guarda em x
senão {x é um vértice adicionado com dois vizinhos. Um deles é um vértice
adicionado y, e o outro é um vértice original z}
início
Caso 1: {y e z estão à esquerda de x}
(3) mover um guarda de y para x e então de x para z;
Caso 2: {apenas um vizinho (ou y ou z) está à esquerda de x}
se não existe aresta que conecte este vizinho esquerdo de x
a um nó à direita de x
(4) então mover o guarda deste vizinho esquerdo de x para x
(5) senão adicionar um novo guarda ao vizinho esquerdo e movê-lo até x;
Caso 3: {y e z estão à direita de x}
(6) colocar um guarda em x
fim;
Remover os guardas dos vértices que não são ativos em Lp
i
e
Remover os guardas duplicados nos vértices que são ativos em Lp
i
fim;
85
Pode ser mostrado por indução em i, que na i-ésima iteração do laço as seguintes condições
são satisfeitas:
todas as arestas que conectam vértices no domínio do layout parcial Lp
i-1
estão limpas,
existe exatamente um guarda em cada vértice do layout parcial Lp
i-1
e nenhum guarda em
qualquer outro vértice.
O argumento deve mostrar que durante a i-ésima iteração, todas as arestas que conectam
vértices do domínio(Lp
i-1
) com o vértice Lp
-1
(i) estão limpas e não admitem recontaminação.
O caso 3 do Algoritmo 4.2, no qual x é um vértice adicionado e seus dois vizinhos encontram-
se à direita de x implica que trata-se de um loop, caso contrário este layout não poderia ser
padrão.
É fácil constatar que em cada um dos casos, todas as novas arestas estão limpas, no
entanto deve-se verificar que não ocorrerá recontaminação:
linha (1): o movimento dos guardas não permite recontaminação, pois os vizinhos de um
nó original são nós adicionados (de grau 2). Uma vez que o layout é padrão, estes nós
adicionados são adjacentes aos vértices que devem estar à esquerda de x. Pela hipótese de
indução, as arestas que conectam estes nós adicionados aos nós à esquerda de x já estão
limpas;
linha (3): mover um guarda de um vértice adicionado para a esquerda de x não permite
recontaminação, já que o layout é padrão e o vértice adicionado está conectado a outro
vértice à esquerda de x. Pela hipótese de indução, todas as arestas que conectam nós à
esquerda de x foram limpas;
linha (4): uma vez que o vizinho à esquerda de x não está conectado por uma aresta a
nenhum vértice à direita de x, todas as arestas incidentes a este vizinho, exceto a que o
conecta a x, foram limpas. Assim, o guarda pode ser movimentado deste vizinho esquerdo
para x sem permitir o recontaminação;
linha (5): não permite recontaminação, já que um guarda novo é adicionado ao vizinho
esquerdo antes da movimentação.
Pela hipótese de indução, na i-ésima iteração do laço, há exatamente um guarda em cada
um dos vértices ativos de Lp
i-1
. Como vs(G’) corresponde a maior quantidade de vértices
ativos dentre todos os possíveis layouts parciais de G’, em cada iteração (ou seja, em cada
86
layout parcial) nunca são usados mais que vs(G’) guardas. Examinam-se então os movimentos
realizados em cada linha do algoritmo.
As linhas (1), (3), e (4) não introduzem novos guardas, portanto existem no máximo
vs(G’) guardas em G’ durante estas etapas. Somente nas linhas (2), (5) e (6) um novo guarda é
adicionado, o vértice x é um vértice ativo no layout parcial Lp
i
já que no mínimo um vizinho
de x encontra-se à sua direita. Além disso todos os vértices que estavam ativos em Lp
i-1
ainda
são ativos em Lp
i
, pois na linha (2) observa-se que x não possui nenhum vizinho esquerdo, na
linha (5) que o vizinho esquerdo de x está conectado a um vértice à direita de x e na linha (6)
que x é um nó adicionado com ambos os vizinhos à sua direita. Assim o número de vértices
ativos em Lp
i
é 1 a mais do que em Lp
i-1
. Conseqüentemente o número de guardas usados em
todas as etapas do algoritmo não é maior do que o número de vértices ativos em qualquer
layout parcial, ou seja, não é maior do que vs(G’).
A complexidade do Algoritmo 4.2 é da ordem de O(n) (ELLIS et all., 1994). As FIG. 4.15
e FIG. 4.18 apresentam a execução passo a passo do Algoritmo 4.2 iniciado em um layout
padrão qualquer e em um layout padrão ótimo do grafo G, respectivamente.
Dado um layout padrão Lp de um grafo 2-expansão G’, o Algoritmo 4.2 determina um
plano de busca que não necessariamente é ótimo, ou seja, que não necessariamente utiliza a
quantidade ótima de guardas esn(G’). O Algoritmo 4.2 constrói um plano de busca que utiliza
um número de guardas w menor ou igual ao vertex separation deste layout padrão da entrada
Lp, ou seja, w
vs
Lp
(G’). No exemplo da FIG. 4.17, o plano de busca determinado pelo
Algoritmo 4.2 necessita de 3 guardas para limpar o grafo G’, no entanto, o plano de busca
ótimo para o grafo G’ utiliza 2 guardas, esn(G’) = 2. Já no exemplo da FIG. 4.18, vs
Lp
(G’) = 2,
e o vertex separation do grafo G’ é igual a 2 vs(G’) = 2, portanto o plano de busca obtido
neste caso é ótimo.
87
F
)FF
')F )
!
G
'/
G
3,/23
G)
3,/23)
G
</23)
G
'/
G)F
3,''#
//#7&/2
3)F
?G'
3,/233)F''
H/#33/
#.'9#
=G)FF
3,/23)FF
>G
3,/23)FF
*GF
3,''/F
G
3,'#
/F/#7&/2
3F
G
</23
B 3/2 3'/
F
)FF
')F )
F
)FF
')F )
F
)FF
')F )
F
)FF
')F )
F
)FF
')F )
F
)FF
')F )
F
)FF
')F )
H/#/
#.'9#
G
</23
</23F
H/#33/
#.'9#
!,
333
2)3'
FIG. 4.17 Algoritmo 4.2 determina plano de busca que utiliza 3 guardas, no entanto
quantidade ótima é esn(G’) = 2 guardas, portanto plano de busca encontrado não é ótimo.
88
F
)FF
')F )
!
G
'/
G
3,/23
G)
3,/23)
G
</23)
G
'/
G)F
3,''#
//#7&/2
3)F
?G'
3,/233)F''
H/#33/
#.'9#
=G)FF
3,/23)FF
>G
3,/23)FF
*GF
3,''/F
G
3,'#
/F/#7&/2
3F
G
</23
B 3/2 3'/
F
)FF
')F )
F
)FF
')F )
F
)FF
')F )
F
)FF
')F )
F
)FF
')F )
F
)FF
')F )
F
)FF
')F )
H/#/
#.'9#
G
</23
</23F
H/#33/
#.'9#
!,
333
2)3'
FIG. 4.18 Algoritmo 4.2 determina plano de busca que utiliza 2 guardas, portanto plano de
busca encontrado é ótimo pois a quantidade ótima é esn(G’) = 2 guardas.
89
4.3.2. ALGORITMO DE ELLIS PARA CALCULAR O EDGE SEARCH NUMBER
BASEADO NO VERTEX SEPARATION DA 2-EXPANSÃO
Pelo Teorema 4.1, o valor do edge search number de um grafo qualquer G coincide com o
vertex separation da sua 2-expansão. Se T é uma árvore, é claro que T’, a sua 2-expansão
também é uma árvore. Portanto, para o caso particular de árvores, podemos utilizar o Teorema
4.1 para obter o edge search number de T utilizando o Algoritmo 3.1 na árvore T’, 2-expansão
de T. A FIG. 4.19 mostra as fases do cálculo do edge search number de T usando o Algoritmo
3.1.
FIG. 4.19 Esquema para cálculo do edge search number de uma árvore qualquer
A seguir formaliza-se o esquema da FIG. 4.19 no Algoritmo 4.3. Inicialmente o algoritmo
transforma a árvore T de entrada em sua árvore 2-expansão T’ e em seguida executa o
Algoritmo 3.1 (cálculo do vertex separation de uma árvore qualquer) para a árvore T’, vertex
separation(T’). O resultado será o parâmetro edge search number da árvore de entrada T.
Algoritmo 4.3 (Ellis et all., 1994)
função edge_search_number_Ellis (T: árvore): inteiro;
T’ = 2-expansão(T) ;
edge_search_number_Ellis = vertex separation(T’); // Algoritmo 3.1
// esta função transforma a árvore T de entrada em uma árvore T’ 2-expansão
função 2-expansão (T: árvore): árvore;
para cada a aresta (a,b) de T faça
início
remover aresta (a,b) de T;
adicionar novos vértices x, y em T;
adicionar novas arestas (x,a), (a,b) e (b,y) em T;
fim
2-expansão = T;
90
A complexidade de tempo do Algoritmo 4.3 é da ordem de O(n). Foi realizada uma
implementação do Algoritmo 4.3 na linguagem de programação Java
TM
2 que será
apresentada no Apêndice.
A FIG. 4.20 mostra a árvore 2-expansão T’ da árvore da FIG. 4.14 com as seqüências de
cada vértice obtidos a partir da execução do Algoritmo 3.1. Podemos observar que esn(T’) =
2. Logo, pelo Algoritmo 4.3 temos que o edge search number da árvore original T da FIG.
4.14 é igual a 2.
FIG. 4.20 Aplicação do Algoritmo 4.3 na árvore T da FIG. 4.14, onde esn(T) = 2.
4.3.3. ALGORITMO DE ELLIS PARA DETERMINAR UM PLANO DE BUSCA
ÓTIMO BASEADO EM UM LAYOUT ÓTIMO DA 2-EXPANSÃO
Provou-se na Seção 4.2, que dado um layout ótimo padrão Lp de um grafo 2-expansão
G’, o Algoritmo 4.2 calcula um plano de busca P’ que limpa o grafo G’ utilizando w guardas,
tal que w vs(G’). Verificou-se que P’ não é necessariamente um plano de busca ótimo,
portanto esn(G’) w, logo, esn(G’) w vs(G’) ou ainda esn(G’) vs(G’). Pelo Teorema
2.1 apresentado no Capítulo 2, tem-se que vs(G’) esn(G’) para um grafo qualquer G’, logo,
vs(G’) = esn(G’), ou seja, w = vs(G’) = esn(G’). Pode-se então concluir que dado um layout
ótimo padrão Lp de um grafo 2-expansão G’, o plano de busca P’ determinado pelo Algoritmo
4.2 utiliza o número ótimo de guardas esn(G’) para limpar o grafo G’, portanto P’ é um plano
de busca ótimo de G’.
Nesta seção consideraremos o grafo G como uma árvore T.
Portanto resta apenas transformar o plano de busca ótimo P’ para a 2-expansão T’ de uma
árvore T, em um plano de busca ótimo P para a árvore T. Pelo Lema 4.1, tem-se que P’ utiliza
esn(T) guardas, portanto falta somente garantir que P’ limpe também a árvore T com os esn(T)
guardas que utiliza. Sabe-se que a transformação 2-expansão de uma árvore T apenas
91
subdivide as arestas de T, substituindo cada aresta (x,y) de T pelas arestas (x,a), (a,b) e (b,y).
Para converter P’ em P, todas as operações (adiciona, move e remove guardas) de P’ que
envolvam vértices adicionados deverão ser eliminadas da seguinte forma:
A limpeza das arestas (x,a), (a,b) e (b,y) será feita por três operações de P’:
i) move guarda de x para a,;
ii) move guarda de a para b;
iii) move guarda de b para y.
No plano de busca ótimo P, estas movimentações deverão limpar apenas a aresta (x,y),
portanto devem ser substituídas por uma única operação:
i) move guarda de x para y.
Todas as demais operações de P’ que removam ou adicionem guardas em vértices
adicionados de T’ devem ser descartadas de P por serem irrelevantes para a limpeza da árvore
T.
Pode-se finalmente propor um modelo para determinar um plano de busca ótimo para
uma dada árvore T que utilize esn(T) guardas, como mostra a FIG. 4.21.
"!
#"!"#$
"
#!"#$
"
$"! "#$
$"
/I
/"2JK3
'/#.'3'3
J9I
/I
</I
$! "#$
$
FIG. 4.21 Modelo para determinar um plano de busca ótimo para uma árvore qualquer.
Segundo o modelo da FIG. 4.21 o cálculo de um plano de busca ótimo P para a árvore T
pode ser realizado construindo-se primeiramente T’, calculando-se em seguida o layout ótimo
L’ de T’ através do Algoritmo 3.2 do Capítulo 3, e finalmente transformando L’ em P
92
aplicando para isso a transformação de um layout em layout padrão, o Algoritmo 4.2 e a
eliminação das operações que envolvam vértices adicionados em P’. A seguir a formalização
deste modelo no Algoritmo 4.4, que calcula um plano de busca ótimo para uma árvore
qualquer.
Algoritmo 4.4 (ELLIS et all., 1994)
função plano_de_busca_ótimo (T: árvore): plano de busca;
T’ = 2-expansão(T) ;
L’ = layout ótimo (T’); // Algoritmo 3.2
// Seja Lp obtido a partir da transformação de L’ mostrada no Lema 4.1
P’ = busca2 (T’, Lp); // Algoritmo 4.1
plano_de_busca_ótimo = eliminar_operações (P’, T);
// transforma o plano de busca ótimo P’ de uma árvore 2-expansão de T em um plano de busca
ótimo P para a árvore T
função eliminar_operações (T: árvore, P’: plano de busca): plano de busca;
para cada aresta (x, y) de T faça
//Sejam a e b os vértices adicionados de x e y em P’
Substituir cada conjunto de 3 operações de P’ (move guarda de x para a,
move guarda de a para b e move guarda de b para y) por uma única
operação (move guarda de x para y);
Eliminar de P’ todas as operações “adiciona guarda” em vértices adicionados;
Eliminar de P’ todas as operações “remove guarda” de vértices adicionados;
eliminar_operações = P’ ;
Uma vez que os Algoritmos 3.2 e 4.2 são lineares, tem-se que a complexidade de tempo
do Algoritmo 4.4 que calcula um plano de busca ótimo para uma árvore qualquer, é da ordem
de O(n).
A FIG. 4.22 mostra o resultado da execução do Algoritmo 4.4 para a árvore T da FIG.
4.14.
93
plano de busca guardas usados
colocar 1 guarda em A 1
colocar 1 guarda em A 2
mover 1 guarda de A para B
mover 1 guarda de B para E
remover 1 guarda em E 1
adicionar 1 guarda em A 2
mover 1 guarda de A para C
mover 1 guarda de C para F
remover 1 guarda em F 1
mover 1 guarda de A para D
mover 1 guarda de D para G
remover 1 guarda em G 0
FIG. 4.22 Execução do Algoritmo 4.4 para árvore T da FIG. 4.14.
94
5. VERTEX SEPARATION E LAYOUT ÓTIMO PARA ÁRVORES BINÁRIAS
CHEIAS
5.1. INTRODUÇÃO
Neste capítulo será apresentado um estudo do problema vertex separation e determinação
de layout ótimo para um tipo de árvores especial.
A Seção 5.2 descreve os resultados obtidos pelo estudo do cálculo do vertex separation
para as árvores binárias cheias. Na Subseção 5.2.1 o algoritmo proposto é formalizado para
esta classe de árvores. A Subseção 5.2.2 descreve os resultados observados a partir da
implementação em Java do algoritmo específico para as árvores binárias cheias. Finalmente a
Subseção 5.2.3 demonstra um teorema que determina o valor de vertex separation em função
da altura da árvore binária cheia.
A Seção 5.3 trabalha a solução do layout ótimo para as árvores binárias cheias. Na
Subseção 5.3.1 é apresentado o algoritmo construído para determinar o layout ótimo de
árvores binárias cheias.
5.2. VERTEX SEPARATION
Sempre que o termo “árvore binária cheia” for mencionado neste documento deve-se
entender uma árvore binária cheia enraizada em seu único vértice de grau 2. Essa hipótese é
muito importante pois caso outro vértice seja escolhido como raiz, não será possível garantir a
validade dos resultados teóricos obtidos para árvores binárias cheias e nem executar
corretamente os algoritmos apresentados para esta classe.
5.2.1. ALGORITMO PROPOSTO
O Algoritmo 3.1 apresentado no Capítulo 3 calcula o vertex separation de árvores. Foram
realizados vários experimentos de executá-lo para alguns tipos de árvores, em particular para
árvores binárias cheias de diversas alturas h. Observou-se que quando aplicado nesta classe de
95
árvores o Algoritmo 3.1 apresenta características particulares que podem ser aproveitadas para
simplificar sua execução.
FIG. 5.1 Árvores binárias cheias de alturas h = 0, 1, 2 e 3, todas com raiz A e com as
seqüências de cada vértice
Numa árvore binária cheia, para qualquer vértice não folha, as subárvores enraizadas em
seus filhos são idênticas, portanto as seqüências correspondentes a seus filhos são também
idênticas, como observado nas árvores da FIG. 5.1. Seja T
h
uma árvore binária cheia de altura
h 0, para h inteiro. Durante a execução do Algoritmo 3.1 a seqüência s
h
da raiz de T
h
é dada
por:
s
h
= combina_seqüências ( s
h-1
, s
h-1
)
Além disso, todas as seqüências de T
h
serão sempre formados por único número inteiro,
conforme o Lema 5.1, portanto vs(T
h
) é igual ao único valor da seqüência s
h
.
Lema 5.1: Seja T uma árvore binária cheia enraizada no único vértice v de grau dois de T.
Ao final da execução do Algoritmo 3.1 todos os vértices de T, incluindo v, serão raízes de
uma subárvore k-simples de T, para k 0.
Prova:
Empregando o Algoritmo 3.1 numa árvore binária cheia, a rotina combina_seqüências
será unicamente executada para um conjunto de duas seqüências idênticas. Sendo assim, a
variável q, que indica a quantidade de seqüências que contém o elemento k, somente poderá
assumir dois valores:
96
q = 0, quando nenhuma das duas seqüências combinadas contém o elemento k. Nesta
condição, nenhum dos 6 casos será executado, logo nada será feito nesta iteração do laço
da rotina combina_seqüências. Portanto esta condição poderá ser descartada para o caso
de uma árvore binária cheia pois não interfere nos cálculos, aumentando apenas o tempo
de processamento;
q = 2, quando as duas seqüências combinadas contém o elemento k. Nesta condição,
somente os casos 2 ou 3 da rotina combina_seqüências poderão ser executados.
Ambos os casos 2 e 3 determinam seqüências simples s = (k+1’) e s = (k) respectivamente.
Logo, pode-se concluir que todos os vértices de uma árvore binária cheia submetida ao
Algoritmo 3.1 serão raízes de uma subárvore k-simples de T, para algum valor k
0.
No Algoritmo 3.1 a recursividade é utilizada para percorrer a árvore até suas folhas e
retornar à raiz obtendo a seqüência do pai pela combinação das seqüências dos seus filhos.
Numa árvore binária cheia T
h
de altura h esta recursividade pode ser substituída por um laço
de h iterações que combina as seqüências dos filhos iniciando nas folhas em direção à raiz,
pois a estrutura de T
h
é conhecida.
Pelo Lema 5.1, as seqüências correspondentes a todos os vértices de uma árvore binária
cheia são simples e portanto compostas de único número inteiro. Desta forma é imediato
verificar que para cada chamada da função combina_seqüências a variável q atinge o valor 2
apenas na iteração k = p do laço, permitindo assim a execução dos casos 2 ou 3. Nas demais p-
1 iterações (k = 1 ,..., p-1) a variável q será sempre zero, não sendo necessário executar caso
algum. Portanto pode-se substituir o laço da função combina_seqüências juntamente com as
linhas 1 e 2 (que apenas atribuem um valor provisório à seqüência antes da entrada no laço)
por uma execução direta dos casos 2 ou 3 para k = p, sendo p o único elemento das duas
seqüências a serem combinadas.
97
Algoritmo 5.1
função vertex_separation_ÁrvBinCheia (h: altura da árvore binária cheia): inteiro;
vertex_separation_ÁrvBinCheia := único elemento de calcula_seqüência_VS_ÁrvBinCheia
(h);
função calcula _seqüência_VS_ÁrvBinCheia (h: altura): seqüência;
(1) s
1
= s
2
= (0);
para i = 1 até h faça
s
1
= s
2
= combina_seqüências_ÁrvBinCheia (s
1
, s
2
);
calcula_seqüência_VS_ÁrvBinCheia = s
1
;
função combina_seqüências_ÁrvBinCheia (s
1
: seqüência, s
2
: seqüência): seqüência;
//seja k o único elemento das seqüências s
1
e s
2
// seja q a quantidade de seqüências (dentre s
1
e s
2
) que contém o elemento k
(2) caso i: {q = 2 e elemento k é crítico em s
1
e em s
2
} s = (k +1’);
(3) caso ii: {q = 2 e elemento k é não crítico em s
1
e em s
2
} s = (k);
combina_seqüências_ÁrvBinCheia = s;
O resultado obtido com a adaptação para árvores binárias cheias do Algoritmo 3.1 foi uma
redução substancial de tempo de processamento e espaço de memória. A seguir, a versão do
algoritmo para o caso particular das árvores binárias cheias.
A complexidade do pior caso do procedimento vertex_separation_ÁrvBinCheia,
Algoritmo 5.1, foi reduzida para O(log n) onde h
log n é a altura da árvore binária cheia
com 2
h
+1
- 1 vértices. A FIG. 5.2 ilustra sua execução para uma árvore binária cheia de altura
3.
FIG. 5.2 Execução do Algoritmo 5.2 para uma árvore binária cheia T
3
de altura 3
98
A partir do Algoritmo 5.1 pode-se concluir o lema seguinte que será utilizado na
construção do algoritmo que determina o layout ótimo para árvores binárias cheias.
Lema 5.2: Seja T uma árvore binária cheia enraizada em seu único vértice de grau 2. Seja
um vértice u não folha de T, raiz de um subárvore k-simples. Sejam u
1
e u
2
os dois filhos de u.
Ao final da execução do Algoritmo 5.2 para T tem-se que:
i) se u não é crítico, então u
1
e u
2
serão raízes de subárvores (k-1)-simples críticas de T;
ii) se u é k-crítico, então u
1
e u
2
serão raízes de subárvores k-simples não-críticas de T.
Prova:
i) Seja um vértice u não folha de T com seqüência s = (t’). Sejam u
1
e u
2
os dois filhos de
u, com seqüências s
1
= s
2
.
Pela hipótese, t não é crítico em s. No Algoritmo 5.1, apenas a linha 2 (caso i) determina
uma seqüência com elemento não-crítico s = (k+1’), logo t = k+1, onde k é crítico em s
1
e s
2
,
sendo assim s
1
= s
2
= (k). Portanto se k+1 não é crítico em s então u
1
e u
2
são raízes de
subárvores (k)-simples críticas de T, ou ainda, se k não é crítico em s então u
1
e u
2
são raízes
de subárvores (k-1)-simples críticas de T.
ii) Seja um vértice u não folha de T com seqüência s = (t). Sejam u
1
e u
2
os dois filhos de
u, com seqüências s
1
= s
2
. Pela hipótese, t é crítico em s. No Algoritmo 5.1, apenas a linha 3
(caso ii) determina uma seqüência com elemento crítico s = (k), logo t = k, onde k não é crítico
em s
1
e s
2
, sendo assim s
1
= s
2
= (k’). Portanto se k é crítico em s então u
1
e u
2
são raízes de
subárvores (k)-simples não-críticas de T.
5.2.2. DETERMINAÇÃO DO VALOR DO VERTEX SEPARATION EM FUNÇÃO
DA ALTURA DA ÁRVORE BINÁRIA CHEIA
O Algoritmo 3.1 proposto em (ELLIS et all., 1994) que calcula o vertex separation para
árvores em geral foi implementado na linguagem de programação Java
TM
2. De igual maneira
o Algoritmo 5.1, que adapta o Algoritmo 3.1 para o caso particular das árvores binárias
99
cheias, foi também implementado. Detalhes das implementações dos dois algoritmos são
apresentados no Apêndice 1.
Executamos então o Algoritmo 5.1 para árvores binárias cheias de diversas alturas h,
desde h = 1 até h = 50.000. Verificamos que os valores obtidos de vertex separation possuíam
relação direta com a altura h da árvore. A seguir provamos o resultado observado, Teorema
5.1, que determina de forma imediata o valor do vertex separation de uma árvore binária cheia
a partir de sua altura h.
Teorema 5.1: Seja T
h
uma árvore binária cheia de altura h 0. Então vs(T
h
) = (h+1)/2.
Prova:
A prova será feita por indução em h, a altura da árvore binária cheia T
h
, sendo h 0 um
número inteiro. Para h = 0 o teorema é válido pois vs(T
0
) = 0 = (0+1)/2, conforme FIG. 5.1
(a). Para h = 1 o teorema também é válido pois vs(T
1
) = 1 = (1+1)/2, segundo FIG. 5.1 (b).
Sejam h > j 2 números inteiros. Supor que vs(T
j
) = (j+1)/2 é válido para toda árvore
binária cheia de altura j < h. Será provado que o teorema vale para as árvores binárias cheias
de altura h.
Seja h 2 um número ímpar, então existe um número inteiro k > 1, tal que h = 2k + 1 ou k
= (h-1)/2.
Seja h´ = h – 2 = (2k+1) – 2 = 2k – 1. Como h´ < h então vale a hipótese indutiva. Logo
vs(T
h´
) = (h´+1)/2 = (2k-1+1)/2 = 2k/2 = k. Seja u raiz de T
h
e sejam v
1
e v
2
os dois
filhos de u. As árvores T[v
1
] e T[v
2
] são árvores binárias cheias de altura h-1. Os vértices v
1
e
v
2
são k-críticos pois cada um deles possui como subárvores duas árvores binárias cheias de
altura h´ = h – 2 para as quais tem-se, pela hipótese indutiva, que o valor de vertex separation
das mesmas é igual a k. Logo pelo caso (2) do Corolário 3.3 temos que vs(T[u]) = k + 1.
Portanto vs(T
h
) = k + 1 = (h –1)/2 +1 = (h –1+2)/2 = (h+1)/2 = (h+1)/2.
A FIG. 5.3 (a), (b) mostra as árvores T
h´
e T
h
para h impar, onde os vértices v
1
e v
2
são k-
críticos.
Seja h 2 um número par, então existe um inteiro k > 1, tal que h = 2k ou k = h/2.
Seja h´ = h – 2 = 2k– 2. Como h´ < h então vale a hipótese indutiva. Logo vs(T
h´
) =
(h´+1)/2 = (2k-2+1)/2 = (2k-1)/2 . Seja u raiz de T
h
e sejam v
1
e v
2
os dois filhos de u.
As árvores T[v
1
] e T[v
2
] são árvores binárias cheias de altura h-1. Os vértices v
1
e v
2
são (2k-
100
1)/2-críticos, pois cada um deles possui como subárvores duas árvores binárias cheias de
altura h´ = h – 2 para as quais tem-se, pela hipótese indutiva, que o valor de vertex separation
é igual a (2k-1)/2 . Logo, pelo caso (2) do Corolário 3.3, conclui-se que vs(T[u]) = (2k-1)/
2 + 1. Portanto, vs(T
h
) = (2k-1)/ 2 + 1 = {2(h/2)-1}/2 + 1 = (h-1)/2 + 1 = (h-
1+2)/2 = (h+1)/2 .
A FIG. 5.3 (a), (c) mostra as árvores T
h´
e T
h
, para h par, onde os vértices v
1
e v
2
são (2k-1)/
2 - críticos.
Logo o teorema vale para toda árvore binária cheia de altura h.
FIG. 5.3 Árvores binárias cheias de alturas h e h’= h-2.
5.3. LAYOUT ÓTIMO
O Algoritmo 3.2 apresentado no Capítulo 3 para determinar um layout ótimo de uma
árvore qualquer foi alterado a fim de resolver o problema para o caso específico das árvores
binárias cheias. Primeiramente será necessário introduzir alguns resultados que serão
empregados na formalização do teorema que fundamenta o algoritmo para árvores binárias
cheias.
101
5.3.1. CONCEITOS INICIAIS
O objetivo desta série de resultados é construir o layout ótimo de uma árvore binária
cheia a partir da raiz u e dos layouts ótimos das duas subárvores correspondentes aos filhos de
u. Para tal fim será necessário analisar a criticidade da raiz das árvores em questão para o caso
particular de árvores binárias cheias e a seguir utilizar os resultados obtidos por (SKODINIS,
2003), já apresentados no Capítulo 3.
Segue um exemplo da execução do Algoritmo 3.2 que determina um layout ótimo para
uma árvore qualquer, aplicado na árvore binária cheia de altura 3 da FIG. 5.1(d). A FIG. 5.4
complementa a informação da execução.
calcula_coarse (T, D) = (D, H, I)
calcula_coarse (T, H) = ( (H) )
calcula_coarse (T, I) = ( (I) )
combina_coarses ( (H) , (I) , D )
último_componente ( (H) , (I) , D ) = (D) & (H) & (I)
calcula_coarse (T, E) = (E, J, K)
calcula_coarse (T, J) = ( (J) )
calcula_coarse (T, K) = ( (K) )
combina_coarses ( (J) , (K) , E )
último_componente ( (J) , (K) , E ) = (E) & (J) & (K)
calcula_coarse (T, F) = (F, L, M)
calcula_coarse (T, L) = ( (L) )
calcula_coarse (T, M) = ( (M) )
combina_coarses ( (L) , (M) , F )
último_componente ( (L) , (M) , F ) = (F) & (L) & (M)
calcula_coarse (T, G) = (G, N, O)
calcula_coarse (T, N) = ( (N) )
calcula_coarse (T, O) = ( (O) )
combina_coarses ( (N) , (O) , G )
102
último_componente ( (N) , (O) , G ) = (G) & (N) & (O)
calcula_coarse (T, B) = (D, H, I, B, E, J, K)
calcula_coarse (T, D) = (D, H, I)
calcula_coarse (T, E) = (E, J, K)
combina_coarses ( (D, H, I) , (E, J, K) , B )
último_componente ( (D, H, I) , (E, J, K) , B ) = direito(D, H, I) & (B) &
esquerdo(E, J, K)
calcula_coarse (T, C) = (F, L, M, C, G, N, O)
calcula_coarse (T, F) = (F, L, M)
calcula_coarse (T, G) = (G, N, O)
combina_coarses ( (F, L, M) , (G, N, O) , C )
último_componente ( (F, L, M) , (G, N, O) , C ) = direito(F, L, M) & (C) &
esquerdo(G, N, O)
calcula_coarse (T, A) = (A, D, H, I, B, E, J, K, F, L, M, C, G, N, O)
calcula_coarse (T, B) = (D, H, I, B, E, J, K)
calcula_coarse (T, C) = (F, L, M, C, G, N, O)
combina_coarses ( (D, H, I, B, E, J, K) , (F, L, M, C, G, N, O) , A )
último_componente ( (D, H, I, B, E, J, K) , (F, L, M, C, G, N, O) , A ) =
(A) & (D, H, I, B, E, J, K) & (F, L, M, C, G, N, O)
FIG. 5.4 Esquema da execução do Algoritmo 3.2 para a árvore da FIG. 5.1(d).
103
Lema 5.3: Seja T uma árvore binária cheia de altura h > 0, para h inteiro, enraizada em
seu único vértice de grau 2. Aplicando-se o Algoritmo 5.1 em T, para k inteiro, tem-se que:
caso h seja um número par então T será uma árvore k-simples crítica;
caso h seja ímpar então T será uma árvore k-simples não-crítica.
Prova:
A prova será feita por indução em h, a altura da árvore binária cheia T
h
, sendo h > 0 um
número inteiro.
Para h = 1 o teorema é válido pois h é ímpar e aplicando-se o Algoritmo 5.1 tem-se que a
seqüência da raiz de T
1
é s
1
= (1’), o que implica que T
1
é árvore 1-simples não-crítica,
conforme FIG. 5.1 (b).
Para h = 2 o teorema é válido pois h é par e aplicando-se o Algoritmo 5.1 tem-se que a
seqüência da raiz de T
2
é s
2
= (1), o que implica que T
2
é árvore 1-simples crítica, conforme
FIG. 5.1 (c).
Para h = 3 o teorema é válido pois h é ímpar e aplicando-se o Algoritmo 5.1 tem-se que a
seqüência da raiz de T
3
é s
3
= (2’), o que implica que T
3
é árvore 2-simples não-crítica,
conforme FIG. 5.1 (d).
Sejam h > h’ 4 números inteiros. Supor que o lema é válido para toda árvore binária
cheia de altura h’ < h. Será provado que o teorema vale para árvores binárias cheias de altura
h.
caso 1: h 4 é par.
Seja h’ = h – 2 ou h = h’ + 2, logo h’ também é um número par. Como h’ < h então vale a
hipótese indutiva para h’, ou seja, T
h
’
é árvore k-simples crítica. A estratégia é transformar T
h
’
em T
h
e observar a criticidade da árvore final. Inicialmente converte-se T
h
’
em T
h
’+1
efetuando
os seguintes passos, conforme mostra a FIG. 5.5(b):
tomam-se duas árvores T
h
’
de raízes u
1
e u
2
;
adiciona-se novo vértice u;
acrescentam-se duas novas arestas (u, u
1
) e (u, u
2
).
Já que T
h
’
é k-simples crítica então utilizando o Lema 5.2 (i) conclui-se que T
h
’+1
é uma
árvore (k+1)-simples não-crítica.
104
Finalmente transforma-se de maneira análoga T
h
’+1
em T
h
’+2
= T
h
, conforme a FIG. 5.5(c):
tomam-se duas árvores T
h
’+1
de raízes v
1
e v
2
;
adiciona-se novo vértice v;
acrescentam-se duas novas arestas (v, v
1
) e (v, v
2
).
Uma vez que T
h
’+1
é (k+1)-simples não-crítica então utiliza-se o Lema 5.2 (ii) para concluir
que T
h
’+2
= T
h
é uma árvore (k+1)-simples crítica.
caso 2: h 4 é ímpar.
Seja h’ = h – 2 ou h = h’ + 2, logo h’ também é um número ímpar. Como h’ < h então
vale a hipótese indutiva para h’, ou seja, T
h
’
é árvore k-simples não-crítica. A estratégia é
transformar T
h
’
em T
h
e observar a criticidade da árvore final. Inicialmente converte-se T
h
’
em
T
h
’+1
da seguinte forma, conforme mostra a FIG. 5.5 (b):
tomam-se duas árvores T
h
’
de raízes u
1
e u
2
;
adiciona-se novo vértice u;
acrescentam-se duas novas arestas (u, u
1
) e (u, u
2
).
Já que T
h
’
é k-simples não-crítica então utiliza-se o Lema 5.2 (ii) para concluir que T
h
’+1
é
uma árvore k-simples crítica.
Finalmente transforma-se de maneira análoga T
h
’+1
em T
h
’+2
= T
h
, conforme a FIG. 5.5 (c):
tomam-se duas árvores T
h
’+1
de raízes v
1
e v
2
;
adiciona-se novo vértice v;
acrescentam-se duas novas arestas (v, v
1
) e (v, v
2
).
Uma vez que T
h
’+1
é k-simples crítica então utiliza-se o Lema 5.2 (i) para concluir que T
h
’+2
= T
h
é uma árvore (k+1)-simples não-crítica.
Logo o teorema vale para toda árvore binária cheia de altura h.
105
FIG. 5.5 Transformação de T
h
’
em T
h
Pode-se então definir o teorema seguinte que será a base para o algoritmo que determina
um layout ótimo para uma árvore binária cheia.
Teorema 5.2: Seja T uma árvore binária cheia enraizada em u, onde s = (k
p
) é a seqüência
da raiz de T. Sejam u
1
e u
2
os dois filhos de u. Um layout ótimo de T pode ser determinado em
função dos layouts ótimos L
1
e L
2
dos dois filhos de u, onde h 0 número inteiro é a altura da
árvore T:
i) se h for par, então L = L
1
& (u) & L
2
é um layout ótimo de T;
ii) se h for ímpar, então L = (u) & L
1
& L
2
é um layout ótimo de T.
Prova:
Sejam os dois filhos de u, raízes das subárvores T[u
1
] e T[u
2
], com seqüências s
1
= (k
p1
) e
s
2
= (k
p2
).
i) Uma vez que s possui único número inteiro k
p
e pela hipótese k
p
é crítico em s, pode-se
utilizar o Lema 3.9(i) para obter um layout ótimo de T dado por L = es
kp
.
Já que T é uma árvore k
p
-simples crítica, pelo Lema 5.2 tem-se que T[u
1
] e T[u
2
] são
subárvores k
p
-simples não-críticas de u, logo, k
p1
= k
p2
= k
p
. Desta forma, pode-se utilizar o
Lema 3.8 para substituir es
kp
por dir
kp1
& (u) & esq
kp2
, onde dir
kp1
é um layout
extensível à direita de T[u
1
], e esq
kp2
é um layout extensível à esquerda de T[u
2
]. Portanto
tem-se que L = dir
kp1
& (u) & esq
kp2
.
106
Já que u é raiz de uma subárvore k
p
-simples crítica, sabe-se pelo Lema 5.2 que u
1
é raiz de
uma subárvore k
p
-simples não-crítica e seus filhos u
11
e u
12
, são raízes de subárvores simples
críticas. Sendo assim, pelo Lema 3.6 (a) tem-se que esq
kp1
= dir
kp1
, portanto tem-se que L
= esq
kp1
& (u) & esq
kp2
.
Como k
p1
e k
p2
são não-críticos em s
1
e s
2
respectivamente, tem-se pelo Lema 3.9 (ii) que
esq
kp1
= L
1
e esq
kp2
= L
2
. Logo, tem-se que: se k
p
é crítico em s então L = L
1
& (u) & L
2
é
um layout ótimo de T. Finalmente, pelo Lema 5.3 tem-se que:
se h for par, então L = L
1
& (u) & L
2
é um layout ótimo de T.
ii) Uma vez que s possui único número inteiro k
p
e pela hipótese k
p
é não-crítico em s,
pode-se utilizar o Lema 3.9 (ii) para obter um layout ótimo de T dado por L = = esq
kp
.
Já que T é uma árvore k
p
-simples não-crítica, pelo Lema 5.2 tem-se que T[u
1
] e T[u
2
] são
subárvores simples críticas de u, logo, pode-se utilizar o Lema 3.6 (a) para substituir esq
kp
por (u) & L
1
& L
2
. Logo, tem-se que: se k
p
é não-crítico em s então L = (u) & L
1
& L
2
é um
layout ótimo de T. Finalmente, pelo Lema 5.3 tem-se que:
se h for ímpar, então L = (u) & L
1
& L
2
é um layout ótimo de T.
Logo o teorema vale para toda árvore binária cheia de altura h.
5.3.2. ALGORITMO PROPOSTO
Apresenta-se agora a estruturação do algoritmo para determinação de um layout ótimo
para árvores binárias cheias que utiliza o Teorema 5.2 como base para sua construção. A
operação “&” utilizada no algoritmo representa a concatenação de layouts.
107
Algoritmo 5.2
função layout_ótimo_ÁrvBinCheia (T: árvore binária cheia, h: altura de T): layout;
// escolher único vértice u de grau 2 como raiz de T
layout_ótimo_ÁrvBinCheia = calcula_layout (T, h, u);
função calcula_ layout (T: árvore binária cheia, h: altura, u: raiz): layout;
// sejam u
1
, u
2
os dois filhos de u
se (h = 0) então
calcula_layout = (u);
senão
L
1
= calcula_layout (T[u
1
], h -1, u
1
);
L
2
= calcula_layout (T[u
2
], h -1, u
2
);
se (h é número par) então
calcula_layout = L
1
& (u) & L
2
;
senão
calcula_layout = (u) & L
1
& L
2
;
O algoritmo é recursivo e a partir da raiz percorre as subárvores de T em direção às folhas,
em seguida retorna à raiz aplicando o Teorema 5.2, determinando o layout ótimo de T.
Pela Definição 3.21, observa-se que a quantidade de componentes do coarse layout de
uma árvore T é igual a quantidade p de inteiros da seqüência da raiz de T. Sabe-se pelo Lema
5.1 que numa árvore binária cheia p = 1 para todo vértice u de T, portanto os coarses layouts
de todas as subárvores T[u] terão sempre único componente. Em virtude disso, a construção
do Algoritmo 5.2 não utiliza o conceito de coarse layout, manipulando-se diretamente o único
layout de cada coarse layout.
A complexidade do Algoritmo 5.2 é O(n). Este algoritmo foi implementado na linguagem
de programação Java
TM
2 e os detalhes de implementação são apresentados no Apêndice 1.
Seguem os cálculos intermediários da execução do Algoritmo 5.2 para a árvore binária
cheia de altura 3 da FIG. 5.1 (d). O layout ótimo resultante é mostrado na FIG. 5.6.
108
layout_ótimo_ÁrvBinCheia = (A, D, H, I, B, E, J, K, F, L, M, C, G, N, O)
calcula_layout (T[A], 3, A) = (A) & (D, H, I, B, E, J, K) & (F, L, M, C, G, N, O)
calcula_layout (T[B], 2, B) = (D, H, I) & (B) & (E, J, K)
calcula_layout (T[D], 1, D) = (D) & (H) & (I)
calcula_layout (T[H], 0, H) = (H)
calcula_layout (T[I], 0, I) = (I)
calcula_layout (T[E], 1, E) = (E & (J) & (K)
calcula_layout (T[J], 0, J) = (J)
calcula_layout (T[K], 0, K) = (K)
calcula_layout (T[C], 2, C ) = (F, L, M) & (C) & (G, N, O)
calcula_layout (T[F], 1, F) = (F) & (L) & (M)
calcula_layout (T[L], 0, L) = (L)
calcula_layout (T[M], 0, M) = (M)
calcula_layout (T[G], 1, G) = (G) & (N) & (O)
calcula_layout (T[N], 0, N) = (N)
calcula_layout (T[O], 0, O) = (O)
FIG. 5.6 Layout ótimo para a árvore T
3
da FIG. 5.2 (d)
109
6. EDGE SEARCH NUMBER E PLANO DE BUSCA ÓTIMO PARA ÁRVORES
BINÁRIAS CHEIAS
6.1. INTRODUÇÃO
Neste capítulo será apresentado um estudo do problema edge search number e
determinação do plano de busca ótimo para um tipo de árvores especial.
A Seção 6.2 é dedicada a solução do problema do edge search number para árvores
binárias cheias. A Subseção 6.2.1 aborda como calcular o edge search number de uma árvore
binária cheia utilizando o mesmo procedimento apresentado na Seção 4.3, ou seja, obtendo o
valor do edge search number a partir do cálculo do vertex separation. A Subseção 6.2.2
apresenta um resultado especificando o valor do edge search number de uma árvore binária
cheia em função de seu valor de vertex separation.
A Seção 6.3 descreve o algoritmo proposto que determina um plano de busca ótimo para
as árvores binárias cheias.
6.2. EDGE SEARCH NUMBER
6.2.1. ALGORITMO PROPOSTO
No Capítulo 4 foi apresentado o procedimento para determinar o edge search number de
um grafo a partir do cálculo do vertex separation do mesmo utilizado o conceito de 2-
expansão. O modelo da FIG. 4.17 mostra como determinar o edge search number de uma
árvore a partir do cálculo do vertex separation. Este procedimento baseia-se no Algoritmo 3.1
para calcular o vertex separation de uma árvore e no Teorema 4.1 que relaciona os valores de
vertex separation e edge search number de um grafo. O mesmo procedimento pode ser usado
para construir o Algoritmo 6.1 para resolver o edge search number para a classe particular de
árvores binárias cheias.
Seja T
h
uma árvore binária cheia de altura h 0, para h inteiro e 2-T
h
sua 2-expansão.
Podemos observar que 2-T
h
é também uma árvore pois a transformação 2-expansão apenas
subdivide todas as arestas de T
h
.
110
Apesar do modelo da FIG. 4.17 realizar a transformação de T
h
em 2-T
h
, o Algoritmo 6.1
não necessita dos parâmetros de entrada T
h
e 2-T
h
, pois a estrutura de ambas as árvores são
conhecidas.
De maneira análoga às árvores binárias cheias (Subseção 5.2.1) a árvore 2-expansão de
uma árvore binária cheia também possui características que podem ser aproveitadas para
simplificar o Algoritmo 3.1.
Qualquer vértice original não folha de 2-T
h
é raiz de duas subárvores idênticas. Cada uma
dessas subárvores é formada por 2 vértices adicionados (cada um contendo apenas único
filho) seguido por 1 vértice original. Além disso, se os vértices x, y estiverem no mesmo nível
em 2-T
h
então as seqüências de x e y serão iguais, como mostra o exemplo da FIG. 6.1.
Como realizado no Algoritmo 5.1, substituiremos a recursividade do Algoritmo 3.1 por
um laço de h iterações que combina as seqüências dos vértices de 2-T
h
iniciando nas folhas
em direção à raiz, pois são conhecidas as estruturas de T
h
e de 2-T
h
.
Algoritmo 6.1
função edge search number_ÁrvBinCheia (h: altura da árvore binária cheia): inteiro;
edge search number_ÁrvBinCheia = maior elemento de
calcula_seqüência_ESN_ÁrvBinCheia (h);
função calcula _seqüência_ESN_ÁrvBinCheia (h: altura): seqüência;
s = (0);
para i = 1 até h faça
// calcula seqüência dos vértices adicionados nas subárvores enraizadas
// em vértices originais
s = combina_seqüências (s); // rotina do Algoritmo 3.1
s = combina_seqüências (s); // rotina do Algoritmo 3.1
// calcula a seqüência de um vértice original na árvore 2-expansão
s = combina_seqüências (s, s); // rotina do Algoritmo 3.1
calcula_seqüência_ESN_ÁrvBinCheia = s;
O parâmetro de entrada do Algoritmo 6.1 é a altura h de uma árvore binária cheia T
h
, no
entanto, o algoritmo é aplicado na árvore 2-expansão de T
h
. A execução inicia das folhas e
111
segue em direção à raiz de T
h
. Ao final de cada iteração i, 1 i h, do laço da função
calcula_seqüência_ESN_ÁrvBinCheia obtém-se a seqüência da raiz de uma árvore 2-
expansão de uma árvore binária cheia T
i
de altura i, como mostra a FIG. 6.1. No término da h-
ésima iteração, a função calcula_seqüência_ESN_ÁrvBinCheia identificará a seqüência da
árvore 2-expansão de T
h
. A saída do Algoritmo 6.1 será o parâmetro edge search number da
árvore binária cheia T
h
.
O Algoritmo 6.1 possui complexidade do pior caso da ordem de O(n). Este algoritmo foi
implementado na linguagem de programção Java
TM
2. Detalhes da implementação encontram-
se no Apêndice 1.
%
& '
(
) *
+
*
*
*
%
%
*
%
$,
-
.
*
/
0
1
#
*
*
*
#.' #.''
FIG. 6.1 Execução do Algoritmo 6.1 para uma árvore 2-expansão 2-T
2
de uma árvore binária
cheia T
2
de altura 2
112
6.2.2. DETERMINAÇÃO DO EDGE SEARCH NUMBER EM FUNÇÃO DO
VERTEX SEPARATION
O Teorema 2.1 do Capítulo 2, apresenta uma relação dada por Ellis entre os parâmetros
edge search number e vertex separation de um grafo G, onde vs(G) esn(G) vs(G) + 2.
A implementação do Algoritmo 6.1 permitiu testar o valor do parâmetro edge search
number para árvores binárias cheias de diversas alturas. Executou-se o procedimento para
árvores binárias cheias com altura variando desde 1 até 5.000. Em todos os casos identificou-
se uma relação entre o edge search number de uma árvore binária cheia e a sua altura.
O Teorema 6.1 mostra a relação entre edge search number e vertex separation para uma
árvore binária cheia de altura h, refinando o Teorema 2.1.
Teorema 6.1: Seja T
h
uma árvore binária cheia de altura h 0, para h inteiro. Se h 1
então esn(T
h
) = vs(T
h
). Se h > 1 então esn(T
h
) = vs(T
h
) + 1.
Prova:
se h
1
Para h = 0 o teorema é válido pois vs(T
0
) = esn(T
0
) = 0. Para h = 1 o teorema também é
válido pois vs(T
1
) = esn(T
1
) = 1.
se h > 1
Primeiramente vamos mostrar que esn(T
h
) vs(T
h
) + 1.
A prova será feita por indução em h, a altura da árvore binária cheia T
h
, sendo h > 1 um
número inteiro.
Para h = 2 e 3 sabemos pelo Teorema 5.1 que vs(T
2
) = 1 e vs(T
3
) = 2. Aplicando o
Algoritmo 6.1 obtemos que esn(T
2
) = 2 e esn(T
3
) = 3. Portanto o teorema é válido para h = 2 e
3 pois esn(T
2
) = vs(T
2
) + 1 e esn(T
3
) = vs(T
3
) + 1.
Para h 4 vamos supor que o resultado vale para h-1 e h-2. Provaremos então que o
teorema é válido para toda árvore binária cheia de altura h.
Sejam u raiz de T
h
e u
1
um dos filhos de u. O grau de u é igual a 3 portanto existem 3
subárvores T1, T2 e T3 que são ramos em u
1
, como mostra a FIG. 6.2.
113
O ramo T1 pode ser construído tomando-se uma árvore binária cheia T
h
-2
e adicionando-se
um novo vértice u
1
e uma nova aresta e incidente a u
1
e a raiz de T
h
-2
, como mostra a FIG.
6.2(a). Pela hipótese indutiva o teorema vale para T
h
-2
, logo esn(T
h
-2
) = vs(T
h
-2
) + 1. A adição
de e em T
h
-2
não altera o valor do edge search number da árvore resultante T1 pois pode-se
construir um plano de busca ótimo para T1 que utilize esn(T
h
-2
) guardas. Primeiramente
limpa-se a subárvore à direita da raiz de T
h
-2
, em seguida limpa-se a aresta e, e finalmente
efetua-se a limpeza da subárvore à esquerda da raiz de T
h
-2
. Portanto esn(T1) = vs(T
h
-2
) + 1.
Para o ramo T2 temos de maneira análoga que esn(T2) = vs(T
h
-2
) + 1.
O ramo T3 pode ser construído tomando-se uma árvore binária cheia T
h
-1
com raiz u
2
e
adicionando-se dois novos vértices u e u
1
, e duas novas arestas e1 = (u
2
, u) e e2 = (u, u
1
) como
mostra a FIG. 6.2(c). Pela hipótese indutiva o teorema vale para T
h
-1
, logo esn(T
h
-1
) = vs(T
h
-1
)
+ 1. A adição de e1 e e2 em T
h
-1
não altera o valor do edge search number da árvore resultante
T3 pois pode-se construir um plano de busca ótimo para T3 que utilize esn(T
h
-1
) guardas da
seguinte forma: primeiramente limpamos a subárvore à direita de u
2
, em seguida limpamos as
arestas e1 e e2, e finalmente efetuamos a limpeza da subárvore à esquerda de u
2
. Portanto
esn(T3) = vs(T
h
-1
) + 1.
Observamos que esn(T1) = esn(T2) esn(T3) pois pelo Teorema 5.1 sabemos que vs(T
h
-2
)
vs(T
h
-1
). Logo podemos afirmar que a árvore T
h
possui um vértice u
1
para o qual existem 3
ramos T1, T2 e T3, todos com edge search number maior ou igual a vs(T
h
-2
) + 1. Pelo Teorema
5.1 sabemos que vs(T
h
) = vs(T
h
-2
) + 1, ou vs(T
h
-2
) = vs(T
h
) – 1. Logo, os ramos T1, T2 e T3
possuem edge search number maior ou igual a vs(T
h
). Portanto pelo Lema 4.1 provamos que
esn(T
h
) vs(T
h
) + 1.
Agora vamos mostrar que esn(T
h
) < vs(T
h
) + 2.
O Lema 4.1 apresentado no Capítulo 4 determina que esn(T
h
) k + 1 se e somente se
existe um vértice v de T
h
que produza 3 ou mais ramos R
i
, para i 3, tal que esn (R
i
) k, ou
seja, todos os ramos possuem edge search number limitados inferiormente por k. A negação
deste resultado determina que se não existir um vértice v de T
h
que produza 3 ou mais ramos
R
i
, para i 3, tal que esn (R
i
) k, então esn(T
h
) < k + 1.
Os vértices u
1
e u
2
, filhos da raiz da árvore binária cheia T
h
, produzem 3 ramos T1, T2 e T3
todos com edge search number menor ou igual a vs(T
h
). É imediato verificar que vs(T
h
) é o
maior valor possível de k para a árvore T
h
. Ou seja, não existe outro vértice v na árvore binária
cheia T
h
, diferente de u
1
e u
2
, que produza 3 ramos R
i
com esn (R
i
) k’ tal que k’ > vs(T
h
).
114
Portanto, pela negação do Lema 4.1, esn(T
h
) < k’ + 1. Seja k’ = vs(T
h
) + 1, logo esn(T
h
) <
vs(T
h
) + 2.
Finalmente podemos concluir que se esn(T
h
) vs(T
h
) + 1 e esn(T
h
) < vs(T
h
) + 2 então
esn(T
h
) = vs(T
h
) + 1, para h > 1. Portanto o teorema é válido para toda árvore binária cheia T
h
de altura h 0.
FIG. 6.2 Ramos em u
1
, filho da raiz de T
h
.
6.3. PLANO DE BUSCA ÓTIMO
Nesta seção será proposto um algoritmo linear para cálculo de um plano de busca ótimo
para o caso das árvores binárias cheias.
6.3.1. ALGORITMO PROPOSTO
Seja uma árvore binária cheia T
h
de altura h 0.
Pelo Teorema 6.1 sabemos que esn(T
h
) = vs(T
h
) para h 1. Não há sentido em determinar
um plano de busca ótimo para T
0
pois esta árvore contém único vértice. Já para a árvore T
1
,
um plano de busca ótimo pode ser determinado iniciando-se a limpeza da árvore por qualquer
uma das folhas de T
1
.
Ainda pelo Teorema 6.1, sabemos que esn(T
h
) = vs(T
h
) + 1 para h > 1. Para este caso
apresentamos a seguir o Algoritmo 6.2, que determina um plano de busca ótimo para T
h
que
utiliza vs(T
h
) + 1 guardas.
O Algoritmo 6.2 foi construído a partir da adaptação do Algoritmo 2.1 apresentado no
Capítulo 2. O layout de entrada L, deverá ser um layout ótimo de T
h
gerado pelo Algoritmo
5.2. Os parâmetros da rotina remover_guardas (u, j) possuem o seguinte significado:
115
u: vértice de L cujos guardas devem ser removidos;
j: número inteiro tal que:
se j > 0 então remover j guardas de u;
se j = 0 então remover todos os guardas existentes em u;
se j < 0 então manter |j| guardas em u e remover os guardas restantes de u.
Algoritmo 6.2
procedimento plano_de_busca_ÁrvBinCheia (T
h
: árvore, L: layout ótimo de T
h
)
(1) para (i := 1 to |V|) faça
início
x := L
-1
(i);
(2) para (cada aresta (x,y), com y à esquerda de x, onde
y possui 1 única aresta contaminada) faça
mover_guarda(y,x);
(3) se (x possui ao menos 1 guarda)
se (x é ativo)
remover_guardas(x,-1);
senão // neste caso x é folha
remover_guardas(x,0);
senão se (x é ativo)
colocar_guarda(x);
(4) para (cada aresta (x,y), com y à esquerda de x) faça
início
(5) colocar_guarda(y);
mover_guarda(y,x);
(6) remover_guardas(x,1);
fim;
remover_guardas(vértices não ativos em L
i
, 0);
fim;
116
Teorema 6.2: O Algoritmo 6.2 determina um plano de busca ótimo para uma árvore
binária cheia T
h
usando no máximo vs(T
h
) + 1 guardas.
Prova:
A idéia é inicialmente mostrar como um layout qualquer L de uma árvore binária cheia T
h
de altura h pode derivar um plano de busca P que utilize w guardas, tal que w vs
L
(T
h
) + 1.
No Algoritmo 2.1, apresentado na Seção 2.5 do Capítulo 2, a linha 2 adiciona 1 guarda no
vértice x = L
-1
(i) do grafo G no início de cada iteração i, o que eleva o limite superior de w
para w vs
L
(G) + 1. No Algoritmo 6.2 essa ação é substituída pelos blocos de comandos (2) e
(3) que adicionam 1 guarda em x somente se este for ativo no layout parcial L
i
.
De maneira análoga ao Algoritmo 2.1, pode-se mostrar, por indução em i, que no início da
i-ésima iteração do laço para mais externo (linha 1) do Algoritmo 6.2, as duas condições
seguintes são satisfeitas:
iii) todas as arestas conectando vértices no domínio do layout parcial L
i
-1
estão limpas, e
iv) há exatamente um guarda em cada vértice ativo do layout parcial L
i
-1
, e nenhum
guarda em qualquer outro vértice.
Pela condição i) anterior concluímos que ao final da última iteração da linha 1 o algoritmo
terá limpado todas as arestas de T
h
.
Já pela condição ii) obtemos que w = |A
L
(i-1)|. Pela definição vs
L
(T
h
) é a maior quantidade
de vértices ativos dentre todos os layouts parciais de L, vs
L
(T
h
) = max
1
i
|V|
{ |A
L
(i)| : L
(T
h
)}. Portanto no início de cada iteração da linha 1, w vs
L
(T
h
). Resta analisar a variação
de w durante a execução da i-ésima iteração do laço da linha 1.
Bloco de comandos da linha 2
Seja y o vértice à esquerda de x que era ativo ao final da iteração anterior i-1, e que
portanto inicia a iteração i com um guarda, e que possui única aresta contaminada (x, y).
Este bloco limpa todas as arestas (x, y) que tornam y não-ativo em L
i
, a fim de que o
guarda que estava em y seja removido. Dessa forma, permanecerão com guardas apenas os
vértices à esquerda de x que ainda continuarão ativos na iteração i. Portanto após a
execução deste bloco de comandos o limite superior de w permanecerá w vs
L
(T
h
).
117
Bloco de comandos da linha 3
i. adiciona (ou deixa) um guarda em x caso este seja ativo em L
i
(possua alguma aresta
incidente à um vértice a sua direita); ou
ii. retira todos os guardas de x (se existirem guardas em x) caso este seja não ativo em L
i
(não possua nenhuma aresta incidente a um vértice à sua direita).
Portanto após a execução deste bloco de comandos o algoritmo terá adicionado 1 guarda
em x somente se x for ativo em L
i
, portanto ainda teremos w vs
L
(T
h
).
Bloco de comandos da linha 4
De maneira análoga ao laço da linha 3 do Algoritmo 2.1, este bloco apenas limpa as
demais arestas incidentes a x e a algum vértice à esquerda de x. Um guarda é adicionado
dentro de um laço na linha 5, tornando w vs
L
(T
h
) + 1. No entanto, antes que a linha 5
volte a ser executada, a linha 6 remove este guarda extra impedindo que o limite superior
de w atinja vs
L
(G) + 2. Desta forma, após as execuções necessárias do laço da linha 4, w
vs
L
(G) + 1.
Portanto provamos que dado um layout qualquer L de uma árvore T
h
o Algoritmo 6.2
constrói um plano de busca para T
h
que utiliza w guardas de tal forma que w vs
L
(T
h
) + 1.
Se L é um layout ótimo de T
h
, vs
L
(T
h
) = vs(T
h
). Portanto tem-se que w vs(T
h
) + 1.
É imediato verificar que o plano de busca P não é necessariamente um plano de busca
ótimo para T
h
, logo P pode utilizar quantidade w de guardas maior que o número ótimo de
guardas esn(T
h
), ou seja, esn(T
h
) w ou esn(T
h
) vs(T
h
) + 1. Portanto provamos que, dado um
layout ótimo L de T
h
, o Algoritmo 6.2 determina um plano de busca ótimo para T
h
que utiliza
então vs(T
h
) + 1 guardas para limpar totalmente a árvore T
h
.
O Algoritmo 6.2 possui complexidade de tempo de O(n). Este algoritmo foi
implementado em Java
TM
2 e será apresentado em detalhes no Apêndice 1. A FIG. 6.3 mostra
a execução do Algoritmo 6.2 para a árvore binária cheia T
2
de altura 2 da FIG. 5.1(c). O
resultado é um plano de busca ótimo P que utiliza esn(T
2
) = 2 guardas para limpar toda a
árvore T
2
. A tabela TAB. 6.1 apresenta a quantidade de guardas ao final de cada operação de
P, verificando que 2 guardas são suficientes para limpeza total da árvore T
2
.
118
FIG. 6.3 Plano de busca com 2 guardas gerado pelo Algoritmo 6.2
119
plano de busca ótimo guardas utilizados
colocar 1 guarda em B 1
colocar 1 guarda em B 2
mover 1 guarda de B para D 2
remover 1 guarda de D 1
colocar 1 guarda em B 2
mover 1 guarda de B para E 2
remover 1 guarda de E 1
mover 1 guarda de B para A 1
mover 1 guarda de A para C 1
colocar 1 guarda em C 2
mover 1 guarda de C para F 2
remover 1 guarda de F 1
mover 1 guarda de C para G 1
remover 1 guarda de G 0
TAB. 6.1 Quantidade de guardas utilizados no plano de busca ótimo da FIG. 6.3.
120
7. CONCLUSÃO
No início do trabalho de dissertação realizamos uma pesquisa bibliográfica sobre os
problemas vertex separation e edge search number e analisando o material obtido detectamos
algumas soluções algorítmicas para a classe das árvores. Estudamos cada um dos algoritmos e
implementamos alguns na linguagem de programação Java, como mostra a TAB. 7.1. Os
detalhes das implementações encontram-se na Seção 1 do Apêndice.
Problema Solução para árvores Complexidade
Implementado
em Java?
vertex separation
Algoritmo 3.1 (ELLIS et all., 1994) O(n) Sim
layout ótimo
Algoritmo 3.2 (SKODINIS, 2003) O(n) Sim
Algoritmo 4.3 (ELLIS et all., 1994) O(n) Sim
edge search
number
Algoritmo 4.1 (MEGIDDO et all.,
1988)
O(n) Não
Algoritmo 4.1 com função fusão_1
(MEGIDDO et all., 1988)
O(n log n) Não
plano de busca
ótimo
Algoritmo 4.4 (ELLIS et all., 1994) O(n) Não
TAB. 7.1 Soluções encontradas na literatura para árvores.
Foram executados os algoritmos implementados (TAB. 7.1) para árvores binárias cheias
com diversas alturas e observamos que, em geral, os procedimentos não concluíam para
alturas superiores a 15. Por tal motivo foram construídos algoritmos específicos para o caso
das árvores binárias cheias.
A partir do estudo das características das soluções da TAB. 7.1, para cada um dos
problemas, adotamos um algoritmo como base na construção dos procedimentos específicos
para as árvores binárias cheias. A tabela TAB. 7.2 mostra os algoritmos existentes na
121
literatura para árvores em geral que foram adaptados para árvores binárias cheias. Os detalhes
das implementações dos algoritmos da TAB. 7.2 são apresentados nas Seções 2 e 3 do
Apêndice.
Problema
Solução para árvore
utilizada na adaptação
Árvores binárias
cheias
Implementado
em Java?
vertex separation
Algoritmo 3.1
(ELLIS et all., 1994)
Algoritmo 5.1 Sim
layout ótimo
Algoritmo 3.2
(SKODINIS, 2003)
Algoritmo 5.2 Sim
edge search
number
Algoritmo 4.3
(ELLIS et all., 1994)
Algoritmo 6.1 Sim
plano de busca
ótimo
- Algoritmo 6.2 Sim
TAB. 7.2 Soluções construídas para as árvores binárias cheias.
Utilizando os programas desenvolvidos (baseados nos Algoritmos 5.1 e 6.1) calculamos os
parâmetros vertex separation e edge search number para árvores binárias cheias de alturas
desde 1 até 50 mil. Observando os resultados obtidos percebemos que cada valor mantém uma
relação direta com a altura da respectiva árvore binária cheia. Provamos então dois teoremas
que determinam de forma imediata o valor do vertex separation e do edge search number em
função da altura da árvore binária cheia.
Teorema 5.1: Seja T
h
uma árvore binária cheia de altura h 0. Então vs(T
h
) = (h+1)/2.
Teorema 6.1: Seja T
h
uma árvore binária cheia de altura h 0, para h inteiro. Se h 1
então esn(T
h
) = vs(T
h
). Se h > 1 então esn(T
h
) = vs(T
h
) + 1.
Utilizando a relação existente entre o vertex separation e outros parâmetros de grafos
mostrada na TAB. 2.1 do Capítulo 2, podemos concluir que valor dos mesmos para as árvores
binárias cheias podem ser determinados em função da altura h da árvore, como mostra a TAB.
7.3.
122
TAB. 7.3 Relação do vertex separation com outros problemas para árvores binárias cheias
7.1. TRABALHOS FUTUROS
Foi mencionado no Capítulo 2 que o problema de vertex separation de um grafo tem
relação com o problema de pathwidth, (KINNERSLEY, 1992).
Utilizando os resultados obtidos para árvores binárias cheias propomos como trabalhos
futuros:
a investigação do comportamento dos problemas de pathwidth e decomposição em
caminhos (DAMAS, 2003) para classes particulares de árvores;
o estudo dos problemas de vertex separation e edge search number para as árvores
binárias completas.
T
h
- árvore binária cheia de altura h
Parâmetro relação com vertex separation
edge search number (h+1)/2 esn (Th) (h+1)/2 + 2
node search number ns (Th) = (h+1)/2 + 1
path width pw (Th) = (h+1)/2
interval thickness
(Th) = (h+1)/2 + 1
gate matrix layout gml (Th) = (h+1)/2 + 1
123
8. REFERÊNCIAS BIBLIOGRÁFICAS
ALSPACH, Brian. Searching and Sweeping Graphs: A Brief Survey. Department of
Mathematics and Statistics, University of Regina, Canada, 2004.
CHUNG, M. J., MAKEDON, F., SUDBOROUGH, I. H., TURNER, J. Polynomial algorithms
for the min-cut linear arrangement problem on degree restricted trees. SIAM J. Compt.,
v. 14, n. 1, p. 158-177, 1985.
DAMAS, Maximiliano Pinto. Sobre a solução eficiente de problemas em grafos utilizando
Treewidth e Tree-Decomposition. Dissertação de Mestrado, Instituto Militar de
Engenharia, 2003.
DÍAZ, J., PETIT, J., SERNA, M. A Survey on Graph Layout Problems. ACM Computing
Surveys, v. 34, n. 3, p. 313-356, 2002.
DINNEEN, M. J. VLSI Layouts and DNA Physical Mappings. Los Alamos National
Laboratory. Combinatorics report LACES, [05C-95-20], 1995.
DYER, Daniel. Sweeping graphs and digraphs. Thesis from Simon Fraser University,
Department of Mathematics, 2004.
ELLIS, John.A., SUDBOROUGH, I.H., TURNER, J.S. The vertex separation and edge search
number of a graph. Information and Computation, n. 113, p. 50-79, 1994.
ELLIS, John.A., MARKOV Minko. Computing the vertex separation of unicyclic graphs.
Information and Computation, n. 192, p. 123-161, 2004.
GAREY, M. R., JOHNSON, D. S. Computers and Intractability: A Guide to the Theory of
NP-Completeness. Freeman, problem [ND17], San Francisco, 1999.
124
GUIBAS, L. J., LATOMBE, J. C., LAVALLE, S. M., LIN, D., MOTWANI, R. A Visibility-
Based Pursuit-Evasion Problem. International Journal of Computational Geometry
and Applications, v. 9, n. 5, p. 471-194, 1999.
JUSTEL, Claudia Marcela, MARKENZON, Lilian. Crown Graphs. Congressus
Numerantium, n. 137, p. 169-176, 1999.
KINNERSLEY, N. G. The vertex separation number of a graph equals its path-width.
Inform. Process. Lett., n. 42, p. 345-350, 1992.
KIROUSIS, L. M., PAPADIMITRIOU, C. H. Interval graphs and searching. Discrete Math.,
n. 55, p. 181-184, 1985.
KIROUSIS, L. M., PAPADIMITRIOU, C. H. Searching and pebbling. Theoretical
Computer Sciense, n. 47, p. 205-216, 1986.
LIPTON, R. J., TARJAN, R. E. Applications of a planar separator theorem. SIAM J.
Comput., v. 9, n. 3, p. 615-627,1980.
MAKEDON, F. S., PAPADIMITRIOU, C. H., SUDBOROUGH, I. H. Topological
bandwidth. SIAM J. Algebraic Discrete Meth., n. 6, p. 418-444, 1985.
MEGIDDO, N., HAKIMI, S.L., GAREY, M.R., JOHNSON, D.S., PAPADIMITRIOU, C.H.
The complexity of searching a graph (preliminary version). In Proceedings of the 22nd
Annual Symposium on Foundations of Computer Science, IEEE, p. 376-385, 1981.
MEGIDDO, N., HAKIMI, S.L., GAREY, M.R., JOHNSON, D.S., PAPADIMITRIOU, C.H.
The complexity of searching a Graph. Journal of the Association for Computing
Machinery, v. 35, n. 1, p. 18-44, 1988.
125
PENG, Sheng-Lung, HO, Chin-Wen, HSU, Tsan-sheng, KO, Ming-Tat, TANG, Chuan Yi.
Edge and node searching problems on trees. Theoretical Computer Science n. 240, p.
429-446, 2000.
ROBERTSON, N., SEYMOUR, P. Graph minors I. Excluding a forest. J.Combin. Theory
Ser., B 35, p. 39-61, 1983.
ROBERTSON, N., SEYMOUR, P. Disjoint paths – A survey. SIAM J. Algebra Discrete
Methods, n. 6, p. 300-305, 1985.
SKODINIS, K. Construction of linear tree-layouts which are optimal with respect to vertex
separation in linear time. Journal of Algorithms, n. 47, p. 40-59, 2003.
SZWARCFITER, J. L. Grafos e Algoritmos Computacionais, 2
a
Edição. Editora Campus,
1988.
YANNAKAKIS, M. A polynomial algorithm for the min-cut linear arrangement of trees. J.
Assoc. Comput. Mach., v. 32, n. 4, p. 950-988, 1995.
126
9. APÊNDICES
127
9.1. APÊNDICE 1: IMPLEMENTAÇÕES DE ALGORITMOS ESTUDADOS PARA
ÁRVORES EM GERAL E ÁRVORES BINÁRIAS CHEIAS
9.1.1. INTRODUÇÃO
Neste apêndice são apresentados os programas desenvolvidos durante a dissertação.
Todos os algoritmos foram implementados na linguagem de programação Java
TM
2 utilizando
o ambiente Eclipse 2.1, ambos disponibilizados gratuitamente pela Sun Microsystems e
Eclipse Foundation respectivamente. Uma interface gráfica simples, com classes do pacote
Swing, foi elaborada para facilitar a utilização do programa.
Na Seção 9.2 é abordada a implementação de um programa único para árvores em geral,
onde o usuário pode optar por calcular o vertex separation, determinar o layout ótimo e
calcular o edge search number de uma árvore. Este programa é baseado nos Algoritmos 3.1,
3.2 e 4.3. Nesta seção descrevemos a forma de manuseio deste programa, especificando seus
dados de entrada e saída. Também é mostrado um algoritmo de verificação do layout ótimo
determinado pelo programa, útil para comprovar o resultado para árvores com número
expressivo de vértices. No final da seção são descritas brevemente todas as classes construídas
no programa.
A Seção 9.3 contem informações específicas dos dois programas desenvolvidos para
atender a classe particular das árvores binárias cheias. Na Subseção 9.3.1 é apresentado o
primeiro programa, baseado nos Algoritmos 5.1 e 6.1, que resolve os problemas de vertex
separation e edge search number. A tela de entrada e saída de dados e as classes
implementadas por este programa são especificadas nesta subseção. Finalmente na Subseção
9.3.2 o segundo programa, baseado nos Algoritmos 5.2 e 6.2, é abordado e determina o layout
ótimo e o plano de busca ótimo. Novamente a forma de utilização do programa e suas classes
implementadas em Java são detalhadas.
128
9.1.2. IMPLEMENTAÇÕES EM ÁRVORES: VERTEX SEPARATION, LAYOUT
ÓTIMO, EDGE SEARCH NUMBER
Esta seção apresenta a implementação dos três principais algoritmos para árvores em
geral discutidos nos capítulos anteriores, conforme mostra a tabela seguinte.
Algoritmo Implementado Finalidade Complexidade
Algoritmo 3.1 (ELLIS et all., 1994)
calcular o parâmetro vertex
separation
O(n)
Algoritmo 3.2 (SKODINIS, 2003) determinar um layout ótimo O(n)
Algoritmo 4.3 (ELLIS et all., 2004)
calcular o valor do edge search
number
O(n)
TAB. 9.1 Algoritmos implementados para árvores.
O cálculo do vertex separation é pré-requisito para a determinação do layout ótimo e do
edge search number. Sendo assim, para evitar a repetição de código optamos por implementar
uma única interface de entrada para a execução dos 3 algoritmos. Portanto apresentaremos
nesta seção um único programa onde o usuário poderá escolher qual dos três cálculos deseja.
9.1.2.1.DADOS DE ENTRADA E SAÍDA
A tela inicial do programa apresenta os seguintes dados de entrada e saída, conforme FIG.
9.1 e FIG. 9.2.
Árvore de Entrada: neste campo deve ser informado o nome do arquivo texto que
contem a estrutura da árvore de entrada, com vértices e arestas.
Escolha RAIZ: neste campo deve ser digitado o vértice da árvore de entrada que será a
raiz inicial para a execução dos algoritmos.
129
Botões do tipo radio: possibilitam a escolha de execução, ou seja, ou o programa
calcula o vertex separation, ou o layout ótimo ou o edge search number da árvore de
entrada.
Validar Layout Ótimo?: este campo possui a finalidade de indicar se o usuário deseja
verificar se o layout ótimo determinado pelo programa é de fato ótimo. Essa
verificação é detalhada na seção 1.2 deste apêndice. Portanto este campo somente será
considerado pelo programa se o usuário solicitar o cálculo do layout ótimo.
Executar: este botão de comando inicia o processamento de acordo com os dados
informados.
Resultado: neste espaço localizado no centro da tela inicial são apresentados os
resultados obtidos pela execução do programa.
130
FIG. 9.1 Cálculo de um layout ótimo (com verificação) para a árvore da FIG. 3.9(c).
131
FIG. 9.2 Cálculo do vertex separation para a árvore da FIG. 3.9(c).
9.1.2.2.VERIFICAÇÃO DO LAYOUT ÓTIMO
Através da tela inicial, o usuário pode optar pela validação do layout ótimo L determinado
pelo programa para a árvore de entrada T. Para realizar a verificação o algoritmo calcula a
cardinalidade de todos os conjuntos ativos de L, o maior destes valores é o vertex separation
de L, vs
L
(T). Segundo a definição, para que L seja um layout ótimo de T, vs
L
(T) deve ser igual
ao vertex separation de T, vs(T), parâmetro calculado previamente na determinação do layout
ótimo.
Essa validação foi construída quando da implementação do cálculo do layout ótimo para
árvores, pois a validação manual era exaustiva, demandando muito tempo e incorrendo a erros
freqüentes quando a árvore trabalhada possuía muitas arestas.
132
9.1.2.3.CLASSES IMPLEMENTADAS
A TAB. 9.3 descreve as classes construídas no desenvolvimento do programa que
determina vertex separation, layout ótimo e edge search number em árvores.
Principal
Chamada para iniciar o software, implementa a classe JFrame e
no seu método construtor é criada a interface gráfica que
disponibiliza as funções do sistema.
InOut
Armazena os dados de entrada e os resultados, para facilitar o
momento de impressão da saída.
Contem primeiro método a ser executado, inicio(), onde as
opções de entrada são verificadas e os métodos adequados são
invocados para obtenção do resultado desejado.
Arvore
Armazena a estrutura da árvore de entrada (arestas e vértices).
Aresta
Armazena uma aresta da árvore de entrada.
ManipulaArquivo
Realiza a leitura do arquivo texto de entrada, o qual contem a
estrutura da árvore de trabalho.
ArmazenaArvore
Preenche a classe Arvore com as informações lidas no arquivo de
entrada.
Vertices
Armazena as informações que todo vértice da árvore possui:
sequência (utilizada no cálculo do vertex separation), coarse
layout (utilizado na determinação do layout ótimo) e algumas
informações adicionais e de controle.
Layout
Armazena um layout (sequência de inteiros) e contem todos os
métodos utilizados para a determinação do layout ótimo.
ValidarLayout
Possui os métodos de verificação do layout ótimo determinado
pelo programa. Essa verificação é realizada calculando-se a
cardinalidade de todos os conjuntos ativos deste layout. O valor
da maior cardinalidade deve ser igual ao vertex separation da
árvore de entrada.
Auxiliar
Estrutura auxiliar que guarda informações de controle dos
vértices da árvore.
133
VertexSeparation
Possui todos os métodos utilizados no cálculo do vertex
separation da árvore de entrada.
Esn
Guarda o valor encontrada para o edge search number da árvore
de entrada.
TAB. 9.2 Resumo das classes implementadas.
9.1.3. IMPLEMENTAÇÕES EM ÁRVORES BINÁRIAS CHEIAS
Esta seção apresenta a implementação dos quatro algoritmos adaptados para árvores
binárias cheias discutidos nos capítulos anteriores, conforme mostra a TAB. 9.3.
Algoritmo
Implementado
Finalidade Complexidade
Algoritmo 5.1
calcular o parâmetro vertex
separation
O(n)
Algoritmo 5.2 determinar o layout ótimo O(n)
Algoritmo 6.1
calcular o valor do edge search
number
O(n)
Algoritmo 6.2 determinar o plano de busca ótimo O(n)
TAB. 9.3 Algoritmos implementados para árvores binárias cheias.
9.1.3.1.VERTEX SEPARATION E EDGE SEARCH NUMBER
Um único programa foi construído para o cálculo do vertex separation e do edge search
number. Em ambas as opções o programa é executado para um intervalo de alturas de árvore
binária cheia.
134
9.1.3.1.1. DADOS DE ENTRADA E SAÍDA
A tela inicial do programa apresenta os seguintes dados de entrada e saída, conforme FIG.
9.3 e FIG. 9.4.
Altura Inicial: neste campo deve ser informada a altura inicial da árvore binária cheia.
Altura Final: neste campo deve ser informada a altura final da árvore binária cheia.
Botões do tipo radio: possibilitam a escolha de execução, ou seja, ou o programa calcula o
vertex separation, ou o edge search number para as árvores binárias cheias
correspondentes às alturas informadas.
Executar: Este botão de comando inicia o processamento de acordo com os dados
informados.
Resultado: Neste espaço localizado no centro da tela inicial são apresentados os resultados
obtidos pela execução do programa.
FIG. 9.3 Cálculo do vertex separation para árvores binárias cheias desde altura 11 até 29.
135
FIG. 9.4 Cálculo do edge search number para árvores binárias cheias desde altura 1 até 19.
9.1.3.1.2. CLASSES IMPLEMENTADAS
A TAB. 9.4 descreve as classes construídas no desenvolvimento do programa que
determina o vertex separation e o edge search number de árvores binárias cheias.
Principal
Chamada para iniciar o software, implementa a classe JFrame e
no seu método construtor é criada a interface gráfica que
disponibiliza as funções do sistema.
Rótulos
Armazena os dados de entrada e as sequências das raízes de cada
altura de árvore binária cheia.
ManipulaRotulos
Armazena a Seqüência Base informada na tela inicial quando
altura inicial for diferente de 1.
VertexSeparation
Possui todos os métodos utilizados no cálculo do vertex
separation de todas as alturas de árvore binária cheia.
Esn
Possui todos os métodos utilizados no cálculo do edge search
number para todas as alturas de árvore binária cheia.
TAB. 9.4 Resumo das classes implementadas.
136
9.1.3.2.LAYOUT ÓTIMO E PLANO DE BUSCA ÓTIMO
Um único programa foi construído para o cálculo do layout ótimo e do plano de busca
ótimo para as árvores binárias cheias.
9.1.3.2.1. DADOS DE ENTRADA E SAÍDA
A tela inicial do programa apresenta os seguintes dados de entrada e saída, conforme FIG.
9.5 e FIG. 9.6.
Altura da Árvore Binária: neste campo deve ser informada a altura da árvore binária
cheia.
Botões do tipo radio: possibilitam a escolha de execução, ou seja, ou o programa calcula o
layout ótimo ou o plano de busca ótimo para a árvore binária cheia correspondente a altura
informada.
Validar Layout?: indica se o usuário deseja que o layout ótimo determinado pelo programa
é realmente ótimo. Essa verificação utiliza o mesmo algoritmo descrito na seção 1.2
anterior.
Executar: este botão de comando inicia o processamento de acordo com os dados
informados.
Resultado: neste espaço localizado no centro da tela são apresentados os resultados
obtidos pela execução do programa.
137
FIG. 9.5 Determinação de um plano de busca ótimo para a árvore da FIG. 5.1(c).
FIG. 9.6 Determinação de um layout ótimo (com verificação) para a árvore da FIG. 5.1(c).
138
9.1.3.2.2. CLASSES IMPLEMENTADAS
A TAB. 9.5 descreve as classes construídas no desenvolvimento do programa que
determina o layout ótimo e o plano de busca ótimo para árvores binárias cheias.
Principal
Chamada para iniciar o software, implementa a classe JFrame e
no seu método construtor é criada a interface gráfica que
disponibiliza as funções do sistema.
Layout
Possui todos os métodos utilizados na determinação do layout
ótimo da árvore binária cheia solicitada.
Verificar
Possui todos os métodos utilizados na verificação do layout
ótimo determinado pelo programa.
PlanoBusca
Possui todos os métodos utilizados na determinação do plano de
busca ótimo da árvore binária cheia solicitada.
TAB. 9.5 Resumo das classes implementadas.
Livros Grátis
( http://www.livrosgratis.com.br )
Milhares de Livros para Download:
Baixar livros de Administração
Baixar livros de Agronomia
Baixar livros de Arquitetura
Baixar livros de Artes
Baixar livros de Astronomia
Baixar livros de Biologia Geral
Baixar livros de Ciência da Computação
Baixar livros de Ciência da Informação
Baixar livros de Ciência Política
Baixar livros de Ciências da Saúde
Baixar livros de Comunicação
Baixar livros do Conselho Nacional de Educação - CNE
Baixar livros de Defesa civil
Baixar livros de Direito
Baixar livros de Direitos humanos
Baixar livros de Economia
Baixar livros de Economia Doméstica
Baixar livros de Educação
Baixar livros de Educação - Trânsito
Baixar livros de Educação Física
Baixar livros de Engenharia Aeroespacial
Baixar livros de Farmácia
Baixar livros de Filosofia
Baixar livros de Física
Baixar livros de Geociências
Baixar livros de Geografia
Baixar livros de História
Baixar livros de Línguas
Baixar livros de Literatura
Baixar livros de Literatura de Cordel
Baixar livros de Literatura Infantil
Baixar livros de Matemática
Baixar livros de Medicina
Baixar livros de Medicina Veterinária
Baixar livros de Meio Ambiente
Baixar livros de Meteorologia
Baixar Monografias e TCC
Baixar livros Multidisciplinar
Baixar livros de Música
Baixar livros de Psicologia
Baixar livros de Química
Baixar livros de Saúde Coletiva
Baixar livros de Serviço Social
Baixar livros de Sociologia
Baixar livros de Teologia
Baixar livros de Trabalho
Baixar livros de Turismo
