26.2-1) Na figura 26.1(b), qual é o fluxo pelo corte ({s, v2, v4}, {v1, v3, t})? Qual a capacidade desse corte?
|
|
|
|
|
Solução:
- O valor do fluxo para esse corte é: f(s, v1) + f(v1, v2) + f(v2, v1) + f(v3, v2) + f(v4, v3) + f(v4, t) = 11 + (-0) + 1 + (-4) + 7 + 4 = 19
- O valor da capacidade para esse corte é: c(s, v1) + c(v2, v1) + c(v4, v3) + c(v4, t) = 16 + 4 + 7 + 4 = 31
Discussão:
Esse exercício gerou uma discussão sobre o que é fluxo líquido e fluxo máximo. O professor explicou a diferença entre os fluxos da seguinte forma:
Existe uma rede e existe o fluxo. O fluxo sendo máximo ou não, em qualquer corte, o valor do fluxo líquido vai ser igual ao valor do fluxo naquele corte. Agora, a capacidade do corte varia dependendo do corte. Se o corte for mínimo o fluxo vai ser máximo.
No exercício, se for possível achar um corte mínimo com valor 19, pode-se garantir que o fluxo é máximo, mas um fluxo com valor 19 e um corte com valor 31, não se pode afirmar nada.
O corte mínimo encontrado em sala foi de ({s, v1, v2, v4}, {v3, t}) sendo seu valor c(v1, v3) + c(v4, v3) + c(v4, t) = 12 + 7 + 4 = 23
26.2-3) No exemplo da figura 26.5, qual é o corte mínimo correspondente ao fluxo máximo mostrado? Dos caminhos aumentantes que aparecem no exemplo, quais são os dois que cancelam fluxo?
| (a) | 
|
|
| (b) | 
|
|
| (c) | 
|
|
| (d) | 
|
|
| (e) | 
|
| Figura 26.5, página 522 |
Solução:
- No exemplo da figura 26.5,
qual é o corte mínimo correspondente ao fluxo máximo
mostrado?
O corte mínimo correspondente ao fluxo máximo mostrado na figura acima é ({s, v1, v2, v4}, {v3, t}) e seu valor é c(v1, v3) + c(v4, v3) + c(v4, t) = 12 + 7 + 4 = 23
Dica para a resolução do exercício dada pelo professor:
Para achar o corte mínimo verificar, usando a letra (e), quais são os vértices alcançáveis a partir de s.
- Dos caminhos aumentantes que aparecem no exemplo,
quais são os dois que cancelam fluxo?
Após discutir qual seria a interpretação correta para o exercício, cujo resultado foi a alteração no enuciado deste item (verificar a sessão 2: Correções feitas), chegou-se a conclusão que os dois caminhos aumentantes que cancelam fluxo são (olhando-se o lado esquerdo da figura):- Caminho das figuras a e d: Na figura a aparece um fluxo de 4 (aresta (v3, v2)) e na figura d ele não aparece.
- Caminho das figuras b e c: Na figura b aparece um fluxo de 7 (aresta (v1, v2)) e na figura c ele não aparece.
26.2-8) Mostre que um fluxo máximo em uma rede G=(V, E) sempre pode ser encontrado por uma seqüência de no máximo |E| caminhos aumentantes. (Sugestão: Determine os caminhos depois de encontrar o fluxo máximo).
Esse exercício foi enviado para a lista da turma uma vez que não foi encontrada sua solução em sala de aula.
Solução:
Dado um fluxo máximo em uma rede G=(V,E). Este fluxo pode ser representado por um conjunto de caminhos CJ selecionados da seguinte forma:
a) Inicialmente define-se um grafo G' que é igual a G.
b) Esolhe-se aleatoriamente um caminho simples c entre s e t de G'.
c) Determina-se que o fluxo f(c) deste caminho é igual ao menor fluxo entre todas as suas arestas.
d) Adiciona-se c ao conjunto de caminhos CJ.
e) Para cada aresta (i, j) do grafo G' que pertence a c, subtrai-se f(c) do fluxo da aresta. Se o fluxo da aresta se torna 0 ela é removida do grafo G'.
f) Retorna-se ao passo da letra (b) até que não existam mais caminhos.
Vamos associar cada caminho de CJ a uma das arestas removidas quando ele foi adicionado a CJ. Podemos afirmar o seguinte:
A associacao caminho c -> aresta removida (i,j) é INJETIVA, ou seja, não há dois caminhos associados à mesma aresta.
Vamos provar isto:
Tomemos um caminho c escolhido para ser adicionado a CJ, e considere sua aresta associada (i,j). Os caminhos adicionados antes de c não foram associados a (i,j), pois ela estava ainda no grafo quando c foi adicionado. Os caminhos adicionados depois de c também não podem estar associados a (i,j), pois ela não estava mais no grafo depois que c foi adicionado.
Considerando cada cada um dos caminhos c de CJ é um caminho aumentante, e como a associação é injetiva, então temos no máximo |E| caminhos aumentantes.
Exercício 26.2-3
O enunciado original deste exercício referencia a figura 26.6, o correto é referenciar a figura 26.5.
Outro problema encontrado foi na tradução do segundo item do exercício. No enunciado original a pergunta é: "... cancelam O fluxo?". Após discussão em sala, chegou-se a conclusão que o enunciado correto seria: "... cancelam fluxo?"
Os dois primeiros exercícios foram resolvidos com êxito.
Durante a resolução do primeiro exercício surgiu uma dúvida sobre fluxo máximo que foi prontamente esclarecida pelo professor.
Na resolução do segundo exercício houve dúvidas quanto à interpretação do enunciado do mesmo e após discutir as possíveis interpretações optou-se por alterar o enunciado da questão conforme descrito na sessão 2 - Correções feitas.
Após várias tentativas de resolução, o terceiro exercício ficou pendente. Depois de alguns dias foi enviada uma solução para a lista da turma e esta solução foi reproduzida aqui após ser verificada pelo professor.