ali

MO417 - Questão para a prova oral

Número:

Enunciado: Marque a alternativa que contém as arestas que fazem parte do menor corte (S,T) "minimum cut (S,T)" do grafo de fluxo abaixo. Lembrando que pelo teorema de Max-flow Min-Cut (Ford-Fulkerson, 1956), em qualquer grafo o valor do fluxo máximo é igual a capacidade do menor corte.

a) SA, AB, AT
b) SA, SB, SC
c) AB, BD, CD
d) AT, DT, BT
e) NDA

Ideia original de: Alisson Linhares de Carvalho