Exercícios sobre Fluxo em Grafos, algoritmo Ford-Folkerson, Topólogica

Prévia do material em texto

Universidade Federal Rural de Pernambuco 
Departamento de Estatística e Informática 
Bacharelado em Ciência da Computação 
Projeto e Análise de Algoritmos 
Lista de Exercícios _ Estudo dirigido – VA2 
Prof. Jeane Melo 
 
1. Considere o grafo e respectivas capacidades de arestas a seguir: 
 
 
a) Utilize o algoritmo de Ford-Fulkerson para descobrir o fluxo máximo nesta rede 
partindo do vértice X e chegando no vértice Y. Desenhe as redes ( e respectivas redes 
residuais) obtidas a cada etapa. 
b) Utilize o algoritmo de Edmonds-Karp para obter o fluxo máximo, considerando esse 
grafo inicial. Desenhe as redes ( e respectivas redes residuais) obtidas a cada etapa. 
c) Qual a diferença para a obtenção das redes considerando os dois algoritmos? 
 
 
2. Utilize um Heap Máximo para implementar as seguintes operações em uma Fila de 
Prioridades S, dada como entrada (utilize a linguagem de programação de sua preferência): 
a) Encontrar um elemento máximo de S 
b) Extrair um elemento máximo de S 
c) Inserir um novo número em S 
d) Aumentar o valor de um elemento de S 
e) Exiba a saída de seu programa considerando a seguinte Fila de prioridades S: 
S= {a-17, b-8, c-0, d-11, e-14, f-4, g-20, h-3, i-7, j-10}; Após a extração do máximo de S, 
aumente o valor do elemento “c” para 18. 
 
3. Dê quatro ordenações topológicas diferentes do dígrafo cujos arcos são: a-c a-d b-c b-d c-e 
d-e. 
 
4. Escreva uma função que verifique se uma dada enumeração dos vértices de um digrafo é 
uma ordenação topológica. 
 
5. Construa um grafo direcionado G da seguinte forma 
a) Para cada pessoa P(i) crie dois vértices: B(i) – data de nascimento e D(i), data de morte 
b) Para todo i, crie uma arco de B(i) para D(i) 
c) Se nos dados coletados, P(i) morre antes de P(j) nascer crie um arco de D(i) para B(j) 
d) Se nos dados coletados, a vida de P(i) tem interseção com a vida de P(j), crie um arco de P(i) 
para B(j) e um arco de B(i) para P(j) 
 
Se G tem uma ordenação topológica os dados são consistentes, caso contrário não. 
 
6. a) Imagine que uma empresa deseja transportar a maior quantidade possível de produtos de 
uma cidade para outra, através da rede rodoviária. A restrição do transporte é que cada 
estrada da rede suporta 10 um número finito de caminhões. Então como determinar o fluxo 
máximo permitido na rodovia? 
b) Faça o grafo do problema proposto em (a) usando a tabela a seguir: 
 
 
 
c) Calcule o fluxo máximo do grafo montado em (b). 
 
7. Um algoritmo de fluxo máximo tem necessariamente que examinar toda aresta da rede. 
Verdadeiro ou Falso? Por que? 
 
8. Considere a rede D=(V,E) com V={s, v_1, v_2, v_3, v_4, t} e as seguinte capacidades: 
 
c(s, v_1) = 4 , c(s, v_2) = 4 , c(s, v_3) = 3 , c(v_1, v_3) = 5, c(v_3, v_2) = 2, c(v_2, v_3) = 3, c(v_4, 
v_1) = 4, c(v_3, v_4) = 4, c(v_2, t) = 3, c(v_4, t) = 6. 
 
Determine um fluxo maximal, mas, não máximo em D. Determine um fluxo máximo em D. 
Determine um corte mínimo em D.