46

Exercícios resolvidos: Algoritmos - Teoria e Prática - 3ª Ed. 2012

Thomas Cormen IBSN: 9788535236996

Elaborado por professores e especialistas

Passo 1 de 5keyboard_arrow_downkeyboard_arrow_up

Para começar, vamos simplificar o que o enunciado pede para melhor entendimento do problema. Só conhecemos algoritmos de fluxo em grafos com limitação de capacidade nas arestas, mas o “problema do escape” exige, também, limitação de capacidade nos vértices. O exercício afirma que esse problema pode ser reduzido para um problema com capacidade somente nas arestas e pede para mostrar tal afirmação. Então vamos lá...

Passo 2 de 5keyboard_arrow_downkeyboard_arrow_up

Para começar, o “problema do escape” pode ser modelado como um grafo não direcionado, o que já é um problema. Precisamos, então, a princípio transformá-lo num grafo direcionado, o que pode ser feito simplesmente transformando cada uma das arestas do grafo original em duas arestas antiparalelas de capacidade 1. Uma otimização que pode ser feita é a retirada das arestas incidentes em vértices de partida, já que esses já devem ser origem de fluxo, e retirada de arestas originadas em vértices de bordas, já que não faz sentido esse sentido de fluxo. O próximo passo, já que temos arestas direcionadas para todos os lados, é como considerar a origem e o destino do fluxo.

Passo 3 de 5keyboard_arrow_downkeyboard_arrow_up

Para considerarmos que a origem do fluxo são os vértices de partida e o destino são as bordas, basta-nos adicionar um “vértice origem”, ligado a todos os vértices de partida por arestas de capacidade 1, e um “vértice destino”, ao qual todos os vértices de das bordas são ligados por arestas novamente de capacidade 1. O próximo e último passo a ser considerado é o objetivo principal desse problema: como considerar as capacidades dos vértices?

Passo 4 de 5keyboard_arrow_downkeyboard_arrow_up

Para considerarmos que cada vértice também tem capacidade máxima de fluxo, basta representá-lo como uma aresta (que sabemos tratar) e, para isso, a ideia mais simples é duplicar a camada do “problema do escape”, ou seja, teremos agora dois planos de vértices, sendo que cada vértice do plano 1 tem uma aresta com origem nele e destino no seu vértice equivalente no plano 2, de forma que quaisquer arestas que antes chegavam a um vértice chegam agora apenas à sua cópia do plano 1 e que quaisquer arestas que antes saiam de um vértice saem agora apenas da sua cópia do plano 2, fazendo com que, para cada vértice original, agora temos algo parecido com um vértice alongado cuja capacidade máxima de fluxo também é 1, assim como para as arestas. Fazendo tudo como explicado, o fluxo máximo entre os vértices de origem e de destino é o número de caminhos disjuntos entre os pontos de partida e as bordas.

Passo 5 de 5keyboard_arrow_downkeyboard_arrow_up

Resumindo, para transformar o “problema do escape” em um problema de fluxo máximo comum, basta-nos transformar o grafo não direcionado em um grafo direcionado com arestas de capacidade 1, adicionarmos os vértices de origem de fluxo, ligados aos pontos de partida por arestas de capacidade 1, e de destino de fluxo, ligados aos pontos das bordas por arestas de capacidade 1, e duplicarmos a camada de pontos de forma a transformar cada ponto em um conjunto ponto-aresta-ponto com capacidade 1. A seguir basta executar o algoritmo de fluxo máximo entre os vértices de origem e de destino para termos como resposta o número de caminhos disjuntos dos pontos de partida até as bordas.

Navegar por capítulo

Aprenda agora com os exercícios mais difíceis

R$29,90/mês

Cancele quando quiser, sem multa

Aproveite também

  • check Todos os materiais compartilhados
  • check Biblioteca com mais de 5.000 livros
  • check Videoaulas exclusivas
  • check Resumos por tópicos