MO405 - Questão para a prova oral

Número:

Enunciado:
Seja G=(X,Y) um K_n,n ponderado positivo e M sua matriz de pesos, onde as linhas de M correspondem à X e as colunas à Y. Podemos afirmar que:

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

b) Uma transversal de M corresponde a um emparelhamento maximal de G.

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

d) 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.

e) NDA