MO405 - Questão para a prova oral

Número: 044

Enunciado: Seja G um grafo bipartido ponderado, com bipartição (X,Y), onde |X| = |Y|, e seja M sua matriz de pesos não negativos, onde as linhas de M correspondem a X e as colunas a Y. Podemos afirmar que:

a) Existe uma transversal máxima de M que contém uma das arestas de maior peso em G.

b) Dada uma cobertura ponderada (u,v) de G, se uma transversal de M não possui o mesmo valor de (u,v), então a transversal não é máxima.

c) Um emparelhamento de G corresponde a uma transversal de M.

d) Uma transversal de M corresponde a um emparelhamento maximal (ou seja, não contido propriamente em nenhum outro emparelhamento) de G.

e) NDA