Questão para a prova oral 171

Enunciado:

Quanto ao artifício para se encontrar a emparelhamento bipartido máximo em um grafo G=(V,E), através do cálculo do fluxo máximo em sua rede de fluxo correspondente G'=(V',E'), é correto afirmar que:

A) Um grafo residual produzido a partir de G' sempre possuirá três vezes o número de arestas que não fazem parte da emparelhamento bipartido máximo em G.

B) A cardinalidade da emparelhamento máximo em G é igual a capacidade de um corte mínimo de G'.

C) |E'| sempre é igual a 3*|E|.

D) A cardinalidade da emparelhamento máximo em G pode ser igual a |E'|.

E) NDA

Autor(a): André Santanchè
RA: 022287