Exercícios Fluxo Redes

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

*
*
*
Exercícios de Fluxo em Redes
*
*
*
Exercício 5
Falso. Considere o contra-exemplo abaixo
s
t
4
1
1
1
1
1
1
*
*
*
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
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.
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)
Construimos uma rede de fluxo com os nós do conjunto X, do conjunto Y e os nós s e t. 
s é conectado aos nós de X, os nós de X são ligados aos nós de Y e os nós de Y – Y  M são conectados a t. 
Todas as arestas tem capacidade 1. 
Além disso, s tem suprimento |M|+k, todo nó de Y M tem demanda 1 e t tem demanda k. 
O problema considerado tem solução viável se e somente se a rede construída tem circulação viável
*
*
*
Exercício 18
a) É possível mostrar que o fluxo máximo obtido ao aplicar o algoritmo de Ford-Fulkerson, utilizando M como fluxo inicial, satura todos os vértices de Y
*
*
*
Exercício 22
a) Seja uma matriz 3x3 onde somente as entradas (3,1), (3,2), (1,3) e (2,3) são iguais a 1. Qualquer que seja a permutação das linhas e das colunas os elementos inicialmente em (3,1) e (3,2) ficarão na mesma linha, cobrindo no máximo uma diagonal. Por outro lado, os elementos inicialmente em (1,3) e (2,3) ficarão na mesma coluna, cobrindo no máximo uma diagonal. Portanto, as 3 diagonais não serão cobertas
*
*
*
Exercício 22
b) Lema. Uma matriz é reamurrável se e somente se é possível escolher exatamente uma entrada com valor 1 de cada linha de modo que toda coluna seja escolhida ao menos uma vez.
=> Se for possível basta permutar as colunas 	
<= Se a matriz tem 1’s na diagonal principal então é possível fazer a escolha.
	Seja uma matriz M que não possui a propriedade desejada. Seja M’ a matriz obtida ao trocar 2 linhas de M. Claramente, M’ não possui a propriedade. O mesmo vale para matriz obtida trocando duas colunas. Portanto, não é possível rearrumar M a partir de trocas
*
*
*
Exercício 22
Seja G uma rede de fluxo com três camadas, além dos nós s e t
A camada 1 tem um nó para cada linha
A camada 2 tem um nó para cada entrada de M com vaor 1
A camada 3 tem um nó para cada coluna
*
*
*
Exercício 22
O nó correspondente a linha i na camada i é ligado a todo nó correspondente a linha i na camada 2
Todo nó correspondente a coluna i na camada 2 é ligado ao nó correspondente a coluna i na camada 3.
S e ligado a todo nó da camada 1 e todo nó da camada 3 e ligado a t
Todas capacidades são 1
A Matriz é rearrumável se e somente se o fluxo máximo em G é igual a dimensão da matriz
*
*
*
Exercício 29
Construímos uma rede de fluxo com os nós {1,…,n} correspondendo as aplicações e um nó adicional t. 
Utilize duas arestas anti-paralelas,cada uma delas com capacidade xij, para ligar o nó i ao nó j. 
Ligue cada nó u do conjunto {2,…,n} a t utilizando uma aresta de capacidade bu. 
Calcule o corte mínimo que separa 1 de t na rede. Os nós da partição associada a t constituem a solução ótima. 
*
*
*
Exercício 42
Para encontrar o menor fluxo de valor inteiro …
A) Um limite superior para a solução ótima pode ser obtido transformando o problema de encontrar uma circulação viável na rede G em um problema de fluxo máximo conforme apresentado na sala de aula. Seja U este limite superior. Note que U depende apenas dos lower bounds. 
	Construimos uma rede G’ igual a rede original G, exceto pelo fato que um novo nó s’ é conectado a s com capacidade c. Fazemos então uma busca binária para descobrir o menor valor de c para o qual o problema de circulação em G’ apresenta solução viável. A complexidade deste algoritmo é log U vezes a complexidade do problema de fluxo máximo.