MO640 - Questão para a prova oral

Número: 069

Enunciado:
Considerando a definição de árvore PQ própria de Booth e Lueker, onde os vértices P têm no mínimo dois filhos, e os vértices Q têm no mínimo três filhos, analise as afirmações abaixo:

I - O número máximo de vértices de uma árvore PQ própria com fronteira de comprimento n é 2n - 1.
II - Uma árvore PQ própria que representa n! permutações tem necessariamente n + 1 vértices.
III - Com uma árvore PQ própria é possível representar uma fronteira de comprimento um.

1. São corretas as alternativas I e II.
2. São corretas as alternativas I e III.
3. São corretas as alternativas II e III
4. São corretas as alternativas I, II e III.
5. NDA

Autor(a): Douglas José Soares Rodrigues