MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: No grafo abaixo, execute o algoritmo básico de Ford-Fulkerson para resolver o problema do fluxo máximo, onde o nó S é a origem e o nó T é o solvedor.

Supondo que na primeira iteração do algoritmo foi selecionado o caminho aumentante S → V3 → V2 → T e na segunda iteração foi selecionado o caminho aumentante S → V2 → V1 → T, marque a alternativa correta contendo apenas capacidades de fluxo de arestas do grafo residual após a execução das duas primeiras iterações do algoritmo.

1.  c_f(S,V2) = 2,  c_f(V2,S) = 5, c_f(V1,T) = 5, c_f(T,V1) = 10;
2.  c_f(S,V2) = 5,  c_f(V2,S) = 2, c_f(V1,T) = 5, c_f(T,V1) = 10;
3. c_f(V2,T) = 2,  c_f(T,V2) = 8, c_f(V1,T) = 10, c_f(T,V1) = 5;
4. c_f(V2,T) = 8,  c_f(T,V2) = 2, c_f(V1,T) = 5, c_f(T,V1) = 10;
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto

MO417 - QUESTÃO PARA PROVA ORAL

Número:

Enunciado: Um grupo de pesquisadores desenvolveram um módulo de navegação para robôs, usando o algoritmo de Djikstra, que soluciona o problema do caminho mais curto de única origem. Dois robôs-protótipos, construídos com as mesmas configurações de hardware, foram posicionados em salas diferentes, marcadas com as letras 'A' e 'B', de um labirinto projetado conforme o grafo abaixo. Os robôs se deslocam entre as salas do labirinto, seguindo a direção das arestas do grafo, e percorrendo uma distância equivalente ao peso dessas arestas. 

Sabendo que o robô campeão é quem chega primeiro à sala 'G' e que apenas um robô pode ser campeão, marque a alternativa correta com o percurso do robô campeão, e as respectivas estimativas de caminhos mais curtos de cada sala percorrida.

1. Robô A: A(0) → E(2) → C(4) → D(8) → G(9)
2. Robô A: A(0) → E(2) → C(6) → D(8) → G(9)
3. Robô B: B(0) → F(1) → E(2) → C(4) → D(8) → G(9)
4. Robô B: B(0) → F(1) → D(8) → G(9)
5. NDA.

Ideia original de: Laurindo de Sousa Britto Neto