Algoritmos em Grafos
Euler tour em Árvores (1)

Vários problemas em árvores e grafos
incluem subproblemas básicos, por
exemplo:




Determinar o pai de cada vértice.
Calcular a numeração em pré e pós ordem.
Determinar o nível de cada vértice.
Determinar o número de descendentes de
cada vértice.
Euler tour em Árvores (2)


Estes problemas tem soluções
seqüenciais de tempo linear que usam
basicamente busca em profundidade.
A técnica Euler tour é uma aplicação de
list ranking que pode ser utilizada para
a construção de algoritmos paralelos
eficientes para esses problemas.
Euler tour em Árvores (3)



Seja T=(V,E) uma árvore com V={1, ..., n}
e vi V designado como raiz.
Seja T’=(V,E’) um grafo dirigido obtido de T
onde cada aresta (u,v)  E é substituída
por dois arcos <u,v> e <v,u>.
Como os graus de entrada e saída de cada
vértice de T’ são iguais, T’ é um grafo
euleriano.
Euler tour em Árvores (4)


Um grafo é euleriano se possui um
caminho fechado (circuito) {v0, v1, ...,
vn, v0} que percorre cada aresta uma
única vez.
Esse circuito é denominado Euler tour
de T’.
Estrutura de dados (1)



A árvore T está representada pelas
listas de suas arestas.
Cada aresta (v,w) aparece duas vezes
na estrutura.
Cada aresta (v,w) possui um ponteiro
para a próxima aresta da lista v e um
ponteiro para sua cópia na lista w.
Estrutura de dados (2)



No grafo dirigido T’, a aresta eR=<w,v>
é denominada reversa da aresta
e=<v,w>.
O vetor ListaAdj tem n entradas.
ListaAdj[v] é um ponteiro para a
primeira aresta da lista de arestas
incidentes com v.
Estrutura de dados (3)


Esta estrutura pode ser armazenada em
um vetor EDGE de tal forma que as k
arestas que se originam no vértice 1
ocupem as k primeiras posições,
seguidas das arestas originárias no
vértice 2, e assim sucessivamente.
Isto pode ser construído através de
ordenações no conjunto de arestas.
1
2
8
9
2
1
3
4
3
2
4
2
5
6
5
4
6
4
7
4
8
1
9
1
7
Algoritmo Euler tour de uma
árvore
1.
2.
3.
A árvore T’ e sua lista de adjacência
são calculadas através da duplicação
de todas as arestas de T e ordenandoas.
Todas as listas são tornadas circulares
aplicando-se list ranking.
Para cada aresta (i,j) em T’, prox(i,j) é
o sucessor de (i,j) na sua lista.
Algoritmo Euler tour de uma
árvore
1.
2.
3.
Obtemos T’ e sua lista de adjacências
duplicando todas as arestas de T e
aplicando uma ordenação.
As listas de adjacências para cada vértice
são tornadas circulares aplicando-se list
ranking.
Para cada aresta (i,j) de T’ seja prox(i,j) o
sucessor desta entrada na respectiva lista
de adjacência.
4.
5.
Aplicamos o método de Tarjan e
Vishkin para ordenar as arestas de T’
atribuindo a cada aresta (i,j), a aresta
prox(j,i), como sucessor no Euler tour.
Aplicamos list ranking para determinar
a posição de cada vértice no Euler
tour.

1.
Saída. Um vetor com 2n-2 entradas
representando um Euler tour de T’ como
uma lista ligada. ETourLink[e] é o índice da
aresta sucessora de e no tour.
para k=1 até r faça
1.
se BEDGE[BEDGE[e].reverso].próximonil então
1.
2.
ETourLink[e] BEDGE[BEDGE[e].reverso].próximo
caso contrário ETourLink[e] ListaAdj[e.y]
Tempo

Teorema
O Euler tour de uma árvore T com n
vértices pode ser computado no modelo
CGM com p processadores e O(n/p)
memória local por processador usando
O(log p) rodadas de comunicação e com
O(n/p) computação local por rodada.
Árvore com raiz

Ao tomarmos a primeira aresta do tour
saindo da raiz, então o tour percorre a
árvore enraizada na ordem de uma
busca em profundidade.
Saídas


Em algumas aplicações a posição de
cada aresta no Euler tour deve estar
disponível.
Neste caso, o algoritmo de list ranking é
aplicado à saída do algoritmo.