MO417 - Questão para a prova oral

Número: 101

Enunciado:
Seja G = (V,E) uma rede de fluxo com origem s e sorvedor t, e seja f o fluxo em G apresentados na figura abaixo, com cada aresta rotulada na forma "fluxo/capacidade" ou apenas "capacidade" quando não houver fluxo por ela. Na figura temos também a rede residual Gf. Considere as afirmações a seguir:

  • Existe um caminho com capacidade residual positiva em Gf
  • Existe apenas um corte com capacidade |f| em G
  • Existem em G arestas com capacidade 0
    1. Apenas as afirmações I e II estão corretas.
    2. Apenas as afirmações I e III estão corretas.
    3. Apenas as afirmações II e III estão corretas.
    4. Todas afirmações estão corretas.
    5. NDA

    Autor: Fabian van 't Hooft