Rede de fluxo

Exercícios de Fluxo em Redes

Exercício 5
Falso. Considere o contra-exemplo abaixo
1
s

1
1

1
1

4
1

t

Exercício 7
Construa uma rede de fluxo da seguinte forma:
• Crie um nó para cada cliente, um nó para cada estação, um nó fonte s e um nó terminal t.
• Se um cliente u está a distância menor ou igual a r de uma base v, conecte u a v com uma aresta de capacidade 1.
• Conecte s a cada cliente com arestas de capacidade 1 e cada base a t com arestas de capacidade L
Se a rede tiver fluxo máximo igual a n então é possível ligar cada cliente a uma base atendendo os requisitos

Exercício 10
Seja G* a nova rede obtida aterando a capacidade de e*.
Caso 1. f não satura e* em G. Então f é máximo para G*.
Caso 2. f satura e*. Os passos a seguir são executados
1. Obtemos um fluxo f* viável para G* da seguinte forma.
Seja P um caminho de s a t em G que contém a aresta e* e só utiliza arestas em que o fluxo f é positivo. Seja um fluxo f* tal que f*e= fe -1 se a aresta e pertence a P e f*e= fe caso contrário. Note que é possível encontrar P em O(m+n) e, portanto, construir tal fluxo.
2. Execute o algoritmo de Ford-Fulkerson utilizando f* como fluxo inicial. Como o valor do fluxo máximo em G* difere do valor do fluxo máximo em G por no máximo uma unidade, o algoritmo executa em O(m+n).

Exercício 12
Encontre o corte mínimo em G e remova k arestas deste corte

Exercício 15
b) Devemos considerar a rede de fluxo utilizada para resolver o problema de emparelhamento que foi discutida em sala de aula. Esta rede tem tamanho O(n2).
A solução encontrada pela Alanis, descartando pi,pj,dk e dl corresponde a um fluxo f de valor n-2 nesta rede. Utilizando f como fluxo inicial para o algoritmo de Ford-Fulkerson necessitamos executar no máximo 2 iterações, cada uma delas com complexidade O(n2), para decidir a existência de uma solução viável para o problema de escalonamento de jantares.

Exercício 18
a)
•
•
•
•
•