097-2005

MO640 - Questão para a prova oral
Número: 097
Enunciado:
Baseado no texto "On the consecutive ones property" de Meidanis et al., assinale a alternativa FALSA:

1. Três tipos de transformações de equivalência são permitidas em árvores PQR: permutações de filhos de um nó P, reversão de um nó Q e permutações de filhos de um nó R.
2. Duas árvores PQR são equivalentes quando uma pode ser transformada na outra aplicando zero ou mais transformações de equivalência.
3. Seja C um conjunto de restrições a serem respeitadas em um problema de C1P. Para encontrar a "completion" de C, três operações aplicadas repetidamente são suficientes: interseção, união não disjunta e diferença não contida.
4. Nos casos em que uma árvore PQ, estudada anteriormente, não puder ser construída a partir das restrições estabelecidas, uma árvore PQR poderá ser construída e conterá no mínimo um nó R.
5. NDA

Autor: César Morais Palomo