sexta-feira, 30 de março de 2012
MO 405 - Questão para prova oral (5° semana)
Número:
Enunciado: Considerando um grafo bipartido é incorreto dizer:
a) O índice de estabilidade (independence number) nem sempre é igual ao tamanho de uma das partições.
b) O máximo tamanho de emparelhamento sempre é igual ao mínimo tamanho de cobertura de vértice.
c) O máximo tamanho de conjunto independente sempre é igual ao mínimo tamanho de cobertura de aresta.
d) Seja k > 0. Todo grafo bipartido k-regular possui um emparelhamento perfeito.
e) nda
Assinar:
Postar comentários (Atom)
Vou descartar, por não estar muito clara. A alternativa A fala sobre tamanho de uma das particões, mas a maneira de particionar um grafo bipartido pode não ser única, se ele for desconexo.
ResponderExcluir