1. Considere o Algoritmo de Dijksta para encontrar o Caminho-mais-curto (c.m.c.) entre o vértice s e os outros vértices de um grafo G=(V,E), orientado onde as distâncias dos arcos e Î E é dada por w_e.
   • Construa um grafo com alguns arcos e com w_e < 0, mas sem ciclos de comprimento negativo, onde o algoritmo de Dijkstra funciona corretamente.
   • Construa um grafo com alguns arcos e com w_e < 0, mas sem ciclos de comprimento negativo, onde o algoritmo de Dijkstra falha em encontrar o c.m.c de s aos outros vértices.
2. Prove que é verdade ou que é falso (nesse caso apresentando um contra-exemplo).
   • Se todas as distâncias dos arcos são diferentes, então a árvore de c.m.c. (de s aos outros vértices do grafo) é única.
   • Considere a distância dos c.m.c. de s aos outros vértices do grafo. Se a distância de cada arco é aumentada de k unidades, a distâncias dos c.m.c. aumentam de um múltiplo de k.
   • Se forem retiradas a orientações dos arcos de um grafo orientado G (i.e. passa ser possível passar nos dois sentidos), as distâncias dos c.m.c.'s permanecem as mesmas.
   • Entre todos os c.m.c.'s existentes entre dois vértices em um grafo, o algoritmo de Dijkstra sempre acha o c.m.c. que possui o menos número de arestas.
3. Considere o c.m.c. entre um par de vértices em um grafo orientado G=(V,E), s e t por exemplo. Um arco vital com respeito a esse c.m.c. é um arco que, se retirado do grafo, a distância do c.m.c. de s a t aumenta. O arco mais vital é aquele cuja retirada causa o maior aumento.
   • Proponha um algoritmo para encontrar o arco mais vital dados G=(V,E), s e t.
   • Analise a complexidade do seu algoritmo.
4. Seja G=(V,E) um grafo orientado e acíclico, e s um vértice a partir do qual existe caminho para todos os demais vértices do grafo. Proponha um aalgoritmo com complexidade O(m), m=|E|, para encontrar os c.m.c.'s de s aos outros vértices do grafo. (Dica: use ordenação topológica.)
5. (5.16) Suponha que foram obtidos os c.m.c.'s de s aos outros vértices de G e a árvore de c.m.c. é conhecida. Suponha agora que as distâncias de todos os arcos deve ser aumentada de k unidades. Proponha um algoritmo O(m) para obter os novos c.m.c.'s.
6. Seja o grafo G=(V,E) onde V={ 1, 2, 3, 4, 5, 6 } e E={ (1,2,3), (1,3,3), (1,4,2), (2,5,4), (3,4,1), (3,6,2), (4,2,1), (4,6,2), (5,4,1), (5,6,1) }, onde os trios (u,v,c) indicam os vértice de partida, de chegada e a capacidade do arco. Deseja-se encontrar o fluxo máximo de 1 para 6.
   • Aplique o algoritmo de Ford e Fulkerson (utilizando busca em profundidade lexicográfica, i.e. vá primeiro para o vértice de menor índice, para buscar caminho aumentante na rede residual) no grafo acima. Conte o número de operações de modificação de fluxo em cada arco.
   • Aplique o algoritmo de Edmonds e Karp (utilizando busca em largura para buscar caminho aumentante na rede residual) no grafo acima. Conte o número de operações de modificação de fluxo em cada arco.
   • Aplique o algoritmo Pre-Flow Push (escolhendo primeiro sempre os vértices de menor índice, seja como nó ativo, seja com arco a tentar fazer passar fluxo) no grafo acima. Conte o número de operações de modificação de fluxo em cada arco. Nesse caso, conte quantas destas modificações saturaram a capacidade do arco. Conte também quantas vezes os rótulos de distância ("altura") se modificaram.
   • Aplique o algoritmo de scaling de capacidade. Conte o número de operações de modificação de fluxo em cada arco.
7. Seja o grafo G=(V,E) onde V={ 1, 2, ..., n } e E={ (1,2,n-1), (2,3,n-2), (3,4,n-3), ..., (n-1,n,1) }, onde os trios (u,v,c) indicam os vértice de partida, de chegada e a capacidade do arco. Deseja-se encontrar o fluxo máximo de 1 para n. (os cálculos abaixo devem ser em função de n).
   • Aplique o algoritmo de Ford e Fulkerson (utilizando busca em profundidade lexicográfica, i.e. vá primeiro para o vértice de menor índice, para buscar caminho aumentante na rede residual) no grafo acima. Conte o número de operações de modificação de fluxo em cada arco.
   • Aplique o algoritmo Pre-Flow Push (escolhendo primeiro sempre os vértices de menor índice, seja como nó ativo, seja com arco a tentar fazer passar fluxo) no grafo acima. Conte o número de operações de modificação de fluxo em cada arco. Nesse caso, conte quantas destas modificações saturaram a capacidade do arco. Conte também quantas vezes os rótulos de distância ("altura") se modificaram.
8. Considere um mapa rodoviário e um motorista que tem que ir do vértice s ao t. O mapa é representado pelo grafo G=(V,E), não-orientado onde os valores associados às arestas e Î E, h_e, correspondem às altitudes das estradas correspondentes aos trechos. O motorista não gosta de altitude e quer fazer o caminho que minimiza a menos altitude que ele vai passar. Utilize um algoritmo de árvore geradora mínima para encontrar esse caminho. Qual a complexidade.
9. Uma floresta é um grafo sem ciclos. Seja um grafo G=(V,E), não-orientado onde os pesos das arestas e Î E são dados por d_e. Proponha um algoritmo para encontrar uma floresta com k arestas, k £ n - 1, de peso total mínimo. Sua complexidade tem que ser O(n²) ou inferior.
10. Uma 1-árvore geradora mínima pode ser obtida adicionando-se à árvore geradora mínima a menor aresta que não pertence à mesma. Suponha agora que essa aresta adicional precise estar conectada á um dado vértice v. Proponha uma algoritmo para encontrar uma 1-árvore geradora mínima com esta restrição.
11. Considere que a árvore geradora de peso mínimo (AGM) de G=(V,E), não-orientado onde os pesos das arestas e Î E são dados por d_e, é conhecida. Considere agora que um novo vértice foi acrescentado à G com arestas para todos os vértices em V. Proponha um algoritmo para encontrar a nova AGM. Seu algoritmo deve excutar em O(n    log    n) ou menos. Tente encontrar um algoritmo O(n), existe.
    
    
12. Um algoritmo executa 3 operações diferentes. A primeira e a segunda são executadas O(nm) e O(n²) vezes, respectivamente. O número de execuções da terceira deve ser determinado. Considere um função potencial F . Cada execução da primeira operação aumenta F no máximo de n unidades. Cada execução da segunda operação aumenta F de uma unidade. Sabe-se que cada execução da terceira operação diminui F no mínimo de uma unidade. Suponha que 0 £ F £ n² e obtenha um limite superior para o número de vezes que a terceira operação é executada.

This document was translated from L^AT_EX by H^EV^EA.