MO405 - Questão para a prova oral
Número:
Enunciado: Dentre as alternativas abaixo, assinale a incorreta:
b) Um matching perfeito pode ser representado por uma matriz que só possui um 1 em cada coluna, bem como em cada linha.
c) O tamanho de um matching é calculado através do número de vértices do grafo.
d) Dado um grafo G e M um matching de G. Caso consigamos adicionar uma aresta a a M de forma que M+a' continue sendo um matching de G, então concluímos que M não era um matching maximal.
e) N.D.A
Ideia original de: Leandro Teófilo
Questçao interessante, mas ahcei meio fácil. Na (b), era bom colocar que o grafo é bipartido e a matriz considerada é a de adjacências.
ResponderExcluirDescarto.