Número: 031
Enunciado:
Seja a seqüência a seguir a fronteira de uma árvore PQ: DEFABCGHJIK
Qual das seqüências abaixo não é uma fronteira possível para esta árvore, após a redução com base no conjunto EFGHI?
- ABCDFGEJHIK
- ABIHGFECJDK
- DHFEGIACBJK
- EHGFICDJKAB
- NDA
Redução é uma operação sobre as árvores PQ (p. 342). A única, aliás. Ela parte da árvore original e, a cada iteração, gera uma nova árvore PQ.
ResponderExcluirAo final do processo as folhas se organizam de maneira consecutiva e ainda respeitando as restrições definidas no subconjunto S. Ler as folhas da esquerda para a direita leva à fronteira da árvore, que nada mais é do que uma permutação do conjunto U (p. 340).
Todos os elementos do conjunto universal estão sempre nas folhas (p. 339). No enunciado da questão a fronteira da árvore PQ, designada aqui por T, é
FRONTIER(T) = DEFABCGHJIK,
o que nos leva ao Conjunto Universo
U = {A,B,C,D,E,F,G,H,I,J,K}.
O subconjunto S apresenta apenas uma restrição:
S = {E,F,G,H,I}.
Portanto, para identificar uma árvore que passou pela Redução sobre S, basta verificar se na sua fronteira os elementos de S aparecem consecutivamente.
Como S possui apenas um conjunto com cinco elementos, há 5.4.3.2.1 = 120 combinações possíveis.
Na alternativa 4 encontramos uma delas, destacada pelos parênteses:
(EHGFI)CDJKAB.
O mesmo acontece nas alternativas 3 e 2, respectivamente:
D(HFEGI)ACBJK e AB(IHGFE)CJDK.
Já na alternativa 1 há um problema. O “J” aparece entre o “E” e o “H”, violando a restrição de S:
ABCD(FGE"J"HI)K.
Logo, a alternativa que responde essa questão é a 1.
As páginas citadas ao longo da resolução do comentário anterior fazem referência ao artigo
ResponderExcluirBooth, K.S. & Lueker, G.S., Testing for the Consecutive Ones Property, Interval Graphs, and Graph Planarity usingPQ-Tree Algorithms. J. Comput. Systems Sci., 1976, Vol. 13(3), pp. 335-379.
Caro Adriano,
ResponderExcluirBom comentário, que resolve a questão corretamente, mas há algumas coisas que eu gostaria de corrigir.
Não creio que redução seja a única operação em árvores PQ. Existem as transformações de equivalência, por exemplo. E, para efetuar uma redução, temos que usar outras operações como: criar e destruir nós, mover nós, juntar nós, etc. Sem falar na operação de extrair a fronteira, que não é usada na redução mas a meu ver seria útil para alguém implementando árvores PQ.
Sua frase: "Ao final do processo as folhas se organizam de maneira consecutiva e ainda respeitando as restrições definidas no subconjunto S" não está muito boa. Eu preferiria que você disesse mais claramente: "Na árvore T resultante de uma redução por S, as folhas que correspondem ao conjunto S aparecem consecutivamente na fronteira de T, e também nas fronteiras de todas as árvores equivalentes a T".