fel

MO417 - QUESTÃO PARA A PROVA ORAL

Número:

Enunciado: Seja G = (V,E) a rede de fluxo abaixo, onde uma aresta (u,v) representa a capacidade entre u e v. Deseja-se descobrir o maior fluxo possível entre 1 e 6. Para isso, utiliza-se o método Ford-Fulkerson, com duas maneiras diferentes de se escolher a ordem dos caminhos a serem considerados: a maneira "Longest Path" escolhe sempre o caminho com maior número de arestas na rede residual G' enquanto que a maneira "Shortest Path" escolhe sempre o caminho com menor número de arestas em G'.

Para quaisquer x, y, z naturais positivos tal que x > y > z e y múltiplo de z, qual o número de vezes em que a rede residual G' é atualizada pelo algoritmo Ford-Fulkerson utilizando a maneira  "Longest Path"? E utilizando a maneira "Shortest Path"?

A) Longest Path: 2y / z. Shortest Path: 2;
B) Longest Path: 2x / z. Shortest Path: 2;
C) Longest Path: 1 + (y / z). Shortest Path: 1;
D) Longest Path: 2y / z. Shortest Path: 1;
E) NDA

Ideia original de: Félix Carvalho Rodrigues