domingo, 8 de abril de 2012

MO405 - Questão para a prova oral

Número: 041

Enunciado: Considere o seguinte procedimento iterativo tendo como entrada uma árvore T. Inicialmente formamos um conjunto M vazio. Na i-ésima iteração, recebemos a árvore da iteração anterior (ou T quando i=1) e removemos dela todos os seus vértices folha. Além disso, se i for ímpar, acrescentamos a M as arestas removidas da árvore durante esta iteração. Este processo termina quando a árvore recebida não possuir vértices. No final deste procedimento, podemos afirmar que:

A. M é um emparelhamento perfeito, se T possuir tal emparelhamento.

B. M é um emparelhamento máximo, se T possuir uma quantidade impar de arestas.

C. M é sempre um emparelhamento.

D. M é sempre uma cobertura por arestas.

E. NDA

Ideia original de: Lucas de Oliveira

Nenhum comentário:

Postar um comentário