sexta-feira, 6 de abril de 2012

Questão dia 06/04


MO405 - Questão para a prova oral

Número:

Enunciado: Dentre as alternativas abaixo, assinale a incorreta:

a) O menor grafo com um matching maximal que não é um matching máximo é P4.
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

Um comentário:

  1. 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.

    Descarto.

    ResponderExcluir