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 menor número de arestas.
   
   
3. 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 algoritmo com complexidade O(m), m=|E|, para encontrar os c.m.c.'s de s aos outros vértices do grafo. Para isso, percorra os vértices seguindo uma ordenação topológica.
   • Uma ordenação topológica em um grafo orientado acíclido G=(V,E) é uma ordenação dos vértices do grafo onde se um vértice v vem antes de um vértice w então não existe caminho de w para v.
   • Para se obter uma ordenação topológica observe que um grafo acíclico tem sempre pelo menos um vértice com grau de entrada igual a ZERO. (Por que ?) Portanto é possível se obter uma ordenação topológica retirando sucessivamente vértices de grau zero, que aparecem na ordenação antes dos que permanecem no grafo.
   O seu algoritmo deve encontrar uma ordenação topológica e o c.m.c de s aos demais vértices do grafo em O(m). Explique com detalhes este algoritmo.
   
   
4. (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.
5. 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 (algoritmo do caminho aumentante 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 de scaling de capacidade. Conte o número de operações de modificação de fluxo em cada arco.
   
   
6. Considere um grafo bipartido G=(U,V,E) onde os arcos de E têm um extremo em U e o outro em V. Um emparelhamento M é um conjunto de arestas (M Í E) tal que no máximo uma aresta de M incide (é adjacente) sobre os vértices de G. Adicione um vértice s com arcos ligados aos vértices de U e t com os vértices de V ligados a ele. Utilize os algoritmos de caminho aumentante para encontrar o emparelhamento máximo (com mais arestas) em G encontrando o fluxo máximo de s para t. Analise a complexidade deste algoritmo.
   
   
7. 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 maior altitude que ele vai passar. Utilize um algoritmo de árvore geradora mínima para encontrar esse caminho. Qual a complexidade?
   
   
8. 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.
   
   
9. Seja o grafo G=(V,E), não-orientado onde os pesos das arestas e Î E são dados por d_e. Seja também T(e) a árvore geradora mínima que inclui a aresta e. Proponha um algoritmo que encontra as árvores geradoras T(e) para e Î E (i.e. são m=|E| árvores geradoras mínimas) (todas) em O(n²) (n=|V|).
   
   
10. 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.
    
    
11. Seja o algoritmo de Dijkstra abaixo.
    • Analise sua complexidade explicando as estruturas de dados utilizadas para que a complexidade seja O(n²).
    • Analise sua complexidade explicando as estruturas de dados utilizadas para que a complexidade seja O(m    log    n).
    • Explique que alterações devem ser feitas para que este algoritmo encontre uma árvore geradora mínima de G (algoritmo de Prim).
    
    Algoritmo Dijkstra (s - fonte)
    • Passo 0: Inicialização
      
      Seja S o conjunto de vértices com o caminho mais curto a partir de s já determinado, e S seu complemento (S = V - S).
      
      S ¬ Ø
      
      d(i) ¬ +¥ " i Î V;
      
      d(s) ¬ 0; pred(s) ¬ 0;
      
      
    • Passo 1: Iteração
      • Enquanto S Ì V faça
        
        
        • 1.1 Encontre v Î S t.q. d(v) = min_{w Î S} d(w)
          
          
        • 1.2 S ¬ S È { v }; S ¬ S \ { v };
          
          
        • 1.3 Para todo w Î G⁺ (v)
          
          Se d(v) + l_vw < d(w)
          
          então d(w) ¬ d(v) + l_vw; pred(w) ¬ v;

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