003 - Construção de árvores PQR em tempo quase linear

Sobre árvores PQR e o algoritmo para sua contrução em tempo quase linear proposto por Telles e Meidanis (2005), escolha a alternativa correta:

1. Considere o conjunto das fronteiras das árvores equivalentes a uma dada árvore PQR. Tal conjunto sempre conterá permutações que obedecem, ao mesmo tempo, a todas as restrições utilizadas na construção da árvore.


2. O algoritmo atribui a cor cinza a um nó da árvore se este nó é ortogonal à restrição sendo aplicada na iteração correspondente.


3. A fronteira da subárvore cuja raiz é o LCA não é ortogonal à restrição.


4. Seja S um conjunto com uma restrição sendo adicionada à árvore pelo algoritmo. O algoritmo atrubui a cor cinza a um nó v. Logo, FRONTEIRA(v)\S ≠ Ø   e   S\FRONTEIRA(v) ≠ Ø.



5. NDA