MO405 - Questão para a prova oral
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