Número:
Enunciado: Sobre o método de Ford-Fulkerson e suas implementações podemos afirmar:
I) Em uma rede de fluxo, um corte (S,T) é definido como um corte em que a origem "s" e o sorvedor "t" encontram-se em conjuntos diferentes.
II) Em uma rede de fluxo, o fluxo máximo com origem "s" e sorvedor "t" é igual a capacidade do corte máximo (S,T)
III) O algoritmo de Edmonds-Karp tem complexidade O(VE²), pois utiliza a busca em largura O(VE) para calcular caminhos aumentantes.
IV) Em uma rede de fluxo G com origem "s" e sorvedor "t", se existe um caminho de "s" até "t" sobre a rede residual Gf então o fluxo em G não é máximo.
a) I, III e IV são verdadeiras
b) II e III são verdadeiras
c) III e IV são verdadeiras
d) I e IV são verdadeiras
e) NDA
Ideia original de: Lucas Oliveira Batista
Nenhum comentário:
Postar um comentário