Algoritmos em Grafos 2014-1 (CK111-A)

Avisos

• A disciplina está terminada. A todos aqueles que contribuíram para que essa disciplina fosse um espaço para o aprendizado e a discussão sincera de ideias interessantes, o meu muito obrigado!

• Após o fechamento da turma virtual desta disciplina no SIGAA, a comunicação professor-aluno passa a se dar apenas por meio desta página e por e-mail.

• Aqui estão todas as notas da disciplina. Se você ainda não pegou alguma das suas provas, então por favor passe no meu gabinete para pegá-las. A universidade requer que as Avaliações Finais fiquem com o professor, mas você pode dar uma olhada na sua prova, se desejar.

• Se você reprovou esta disciplina, então as suas avaliações sugerem que, de forma geral, você ainda não atingiu o nível de compreensão esperado do assunto. Nesse caso, a minha sugestão é que você aproveite um pouco destas férias para estudar as partes e aspectos da disciplina nos quais você teve mais dificuldade. Lembre que as disciplinas com que temos mais dificuldades são aquelas que mais precisamos estudar; por isso, a minha sugestão é que você procure sanar as maiores dificuldades assim que possível, para que, da próxima vez, você passe na disciplina, e não apenas no limite da nota, mas sim com folga, para deixar claro que as dificuldades terão sido superadas. Bom trabalho!

• Aos alunos aprovados, parabéns!, e bom proveito do conteúdo aprendido. A disciplina Construção e Análise de Algoritmos (CAnA) fornece uma muito boa continuidade do assunto visto em Algoritmos em Grafos: embora não trate apenas de outros algoritmos sobre grafos, ela desenvolve técnicas de construção de algoritmos que nós aplicamos algumas vezes (como a técnica "gulosa", de escolha de ótimos locais), além de apresentar outras técnicas e aprofundar também o estudo da complexidade de algoritmos.

  Caso você deseje sugestões de tópicos adicionais para estudo (agora, por exemplo, que chegaram as férias), aqui vão as minhas:

  • Para começar, o capítulo "Análise Amortizada" (número 17 da 2ª edição) do Cormen, que apresenta uma técnica muito interessante (e que não costuma ser apresentada em CAnA!) de análise de complexidade.

  • Em seguida, se ainda houver tempo, eu sugiro o estudo do capítulo sobre "montes (heaps) de Fibonacci" (antes, é necessário ler o capítulo anterior, sobre "montes binomiais", pelo menos na 2ª edição do livro): esta estrutura é utilizada para se diminuir a complexidade assintótica de alguns dos algoritmos que vimos (embora, como eu falei em sala, ela não costume ter bom desempenho na prática).

  • Outra estrutura geral e útil é a estrutura de dados de florestas disjuntas para a representação de "conjuntos disjuntos". Como mencionado na disciplina, ela pode ser utilizada para tornar parte do algoritmo de Kruskal mais rápido. Além disso, diferentemente dos montes de Fibonacci, essa estrutura é eficiente na prática, e além disso ela é bastante simples de implementar – embora muito difícil de analisar formalmente!

  • Por fim, se ainda sobrar tempo (e interesse!), eu sugiro o estudo dos algoritmos "push-relabel" para a obtenção de fluxos máximos.

• Esta página está em contínua construção. Por favor, entre em contato comigo caso você precise de alguma informação adicional, ou caso acredite ter encontrado um erro nesta página. Obrigado!

Datas importantes

• 2014-04-16 (quarta-feira): AP1.

• 2014-06-02 (segunda-feira): aula extra.

• 2014-06-06 (sexta-feira): AP2.

• 2014-06-07 (sábado): aula extra.

• 2014-06-14 (sábado): AP3.

• 2014-06-30 (segunda-feira): AF.

Regras

• Segunda chamada: conforme disposto no manual do aluno, o aluno tem direito a fazer uma segunda chamada caso falte a alguma prova. Entretanto, somente serão realizadas segunda-chamadas para alunos que atenderem a todas as seguintes exigências:

  Solicitar a segunda chamada por escrito na secretaria do Departamento de Computação em até 3 dias úteis após a realização da 1a chamada, anexando à solicitação um atestado médico ou comprovação inequívoca da impossibilidade de comparecer à prova.

  Solicitações que não atendam às exigências acima não serão aceitas. Em particular, não ter estudado o suficiente para a primeira chamada não é motivo aceitável para requerer uma segunda-chamada. Além disso, os solicitantes devem estar cientes de que as provas de segunda-chamada são intencionalmente mais difíceis, dado que o aluno tem, em princípio, mais tempo para estudar para elas.

Bibliografia

O livro sugerido para a disciplina é este (eu, entretanto, possuo a segunda edição e me guiarei por ela):

• Introduction to Algorithms (third edition). Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein. MIT Press. 2009.

Eu recomendo todo aluno da Computação a ter uma cópia desse livro, que é útil para várias disciplinas do curso e é uma excelente referência durante e depois delas.

Caso você queira saber de outro livro, o Rudini sugeriu este:

• Algorithms. Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. McGraw-Hill. 2007.

Para ambos os livros há tradução para o português, mas, se você entende inglês sem dificuldade, eu sugiro o original.

Outras referências são citadas abaixo (em aulas), como complemento ao conteúdo apresentado em cada aula.

Aulas

Alguns exercícios passados para sala ou para casa podem não estar listados abaixo:

• 2014-02-12: sem aula (professor sendo empossado no cargo). Há, entretanto, tarefa para casa. Os problemas e algoritmos estudados nesta disciplina têm amplas aplicações na prática. Eu proponho, a você que já cursou Estruturas de Dados, o seguinte problema:

  Escreva um algoritmo conforme especificado a seguir. A entrada do algoritmo é (1) a especificação das amizades do Facebook, e (2) um usuário "U" qualquer do Facebook. A saída do algoritmo deve ser a impressão de todos os amigos de "U", seguidos pelos amigos dos amigos de "U", seguidos pelos amigos dos amigos dos amigos, etc. Cada pessoa deve ser listada juntamente com a sua "distância" ao usuário "U".

  A título de exemplo, suponha que, no Facebook, as seguintes são as únicas amizades de um grupo de cientistas:

  • Dijkstra é amigo de Hoare e Gries;
  • Gries é também amigo de Lamport e Owicki;
  • Lamport é também amigo de Owicki e Knuth;
  • Knuth é também amigo de Floyd;
  • Hoare é também amigo de Floyd.

  Nesse caso, se o algoritmo desta questão recebe como entrada (1) TODAS as amizades do Facebook e (2) o usuário Dijkstra, uma saída possível é:

  • 1 - Hoare.
  • 1 - Gries.
  • 2 - Lamport.
  • 2 - Owicki.
  • 2 - Floyd.
  • 3 - Knuth.

  Pontos importantes da solução:

  1. Existem muitas amizades no Facebook. Como seria interessante armazená-las?
  2. A forma de armazenamento escolhida permite um rápido acesso aos amigos de um usuário? O uso de memória é eficiente?
  3. Qual é o custo assintótico do seu algoritmo? É possível argumentar que esse custo é o melhor possível?

  A aula seguinte tomará esse exercício como ponto de partida.

• Aula 1 (2014-02-14): apresentação da disciplina, conceitos de teoria dos grafos (grafo não-direcionado, grafo direcionado, caminho, ciclo, caminho direcionado, circuito, distância entre vértices, etc), modelagem do exercício anterior em termos de grafos.

• Aula 2 (2014-02-19): representações de grafos como estruturas de dados: listas de adjacências, matriz de adjacências; comparações entre elas; representações alternativas (listas ao invés de vetor de vértices, incidência ao invés de adjacência, etc).

• Aula 3 (2014-02-21): algoritmo de percurso em grafos não-direcionados por ordem de distância a partir de um dado vértice; implementações alternativas; complexidade do algoritmo.

• Aula 4 (2014-02-26): ferramentas para provas de correção de algoritmos iterativos: variantes e invariantes de laços; enunciado de invariantes para o algoritmo de percurso em grafos da aula anterior.

  Observações:

  1. Provar a correção de algoritmos é como demonstrar um teorema. O primeiro passo é tornar o objeto em questão um objeto matematicamente tratável; para isso, existem as semânticas de linguagens de programação.
     Um trabalho pioneiro na área de verificação foi o de Robert W. Floyd. Eu recomendo a leitura desse artigo se você tiver um tempo livre; "a intuição está toda lá".
     Muita coisa ocorreu de Floyd (e mesmo de antes: Turing, von Neumann, etc) até aqui; um excelente resumo moderno é o capítulo 1 deste trabalho.
     Para o caso de você querer entender do que se trata tudo isso na prática, existem ferramentas para a demonstração formal da correção de programas reais, por exemplo aqueles escritos em C.
     Na minha opinião, essa é uma bela área de pesquisa, que combina lógica e algoritmos; ela é, porém, um pouco especializada.
     Há vários trabalhos na área atualmente, os quais giram em torno da iniciativa do software verificado.

  Exercícios:

  1. Demonstre que as afirmações enunciadas sobre o algoritmo de percurso em grafos são mesmo invariantes do laço principal do algoritmo.

  2. Dispondo dos invariantes apresentados em sala, prove a correção do algoritmo de percurso em grafos em questão.

  3. Se você fizer tudo isso e ainda tiver tempo livre, experimente começar a ler o artigo de Floyd citado acima.

• Aula 5 (2014-02-28): prova do primeiro invariante do algoritmo de percurso em grafos por ordem distância a um dado vértice de origem.

  Exercício: prove os demais invariantes do laço principal do algoritmo.

• 2014-03-05: sem aula (recesso escolar: quarta-feira de cinzas).

• Aula 6 (2014-03-07): demonstração da correção parcial (se o algoritmo termina, então a resposta retornada é correta) e da correção total (o algoritmo termina e retorna uma resposta correta) do algoritmo de percurso em grafos por ordem de distância (não-ponderada).

  Material complementar: aqui está uma demonstração dos invariantes do algoritmo de percurso em grafos discutido em sala. (A minha demonstração inicial continha alguns erros, principalmente um na demonstração do invariante "f", no qual eu supunha, sem demonstrar, o que agora se tornou o invariante "k"; a correção consistiu principalmente em demonstrar esse novo invariante.)

  Exercícios: (sugestão: siga a ordem abaixo)

  1. Escreva um algoritmo que recebe como entrada um grafo não-direcionado "G", possivelmente desconexo, e que responde se "G" possui ou não um ciclo. Qual é a complexidade assintótica do tempo de execução do seu algoritmo, e qual representação do grafo de entrada é suposta?

  2. Análogo ao exercício anterior, exceto que o grafo de entrada agora é direcionado, e que o algoritmo deve informar sobre a existência de circuitos.

• Aula 7 (2014-03-12): discussão e escrita de algoritmo para detecção de ciclos em grafos não-direcionados; discussão sobre detecção de circuitos em grafos direcionados.

  Exercícios:

  1. Utilizando as ideias discutidas em sala, escreva um algoritmo para detecção de circuitos em grafos direcionados.

• Aula 8 (2014-03-14): algoritmo para detecção de circuitos em grafos direcionados (via busca em profundidade, em contraposição ao algoritmo do caso não-direcionado, que é uma aplicação da busca em largura).

  Exercícios:

  1. Escreva uma versão não-recursiva do algoritmo escrito em sala.

  2. Prove a correção do algoritmo discutido em sala.

  3. Obtenha a complexidade assintótica do tempo de execução do algoritmo obtido em sala.

  4. Obtenha a complexidade assintótica do tempo de execução do algoritmo obtido em sala para a detecção de ciclos em grafos não-direcionados.

• 2014-03-19: sem aula (Feriado Estadual: Dia de São José).

• Aula 9 (2014-03-21): prova de terminação do algoritmo de detecção de circuitos; discussão sobre a correção do algoritmo; prova de que, se o algoritmo acusa circuito, então a resposta é correta; "teorema dos parênteses".

  No livro: seção 22.3 (busca em profundidade), até teorema 22.7.

  Exercícios:

  1. Com base nos resultados apresentados em sala, tente demonstrar a volta da implicação demonstrada em sala ("se há um circuito, então o algoritmo o acusa").

  2. Calcule o tempo de execução do algoritmo, e o compare com o tempo de execução do algoritmo para o caso não-direcionado. E os usos de memória dos algoritmos, como se comparam?

  3. O algoritmo em questão serve também para detectar ciclos em grafos não-direcionados? Alguma modificação é necessária?

• Aula 10 (2014-03-26): "teorema do caminho branco"; término da prova da correção do algoritmo de detecção de circuitos ("a resposta é verdadeiro sse existe circuito no grafo"); complexidade do tempo de execução do algoritmo.

  No livro: seção 22.3 (busca em profundidade), até teorema 22.9, e (sem a classificação nomeada das arestas) lema 22.11 da seção 22.4.

  Exercícios:

  1. Uma ordenação topológica de um grafo direcionado G = (V,E) é uma ordenação v_0, v_1, ..., v_n dos vértices de G tal que não há em E um par (v_i,v_j) tal que i > j. Prove que um grafo direcionado qualquer possui uma ordenação topológica sse ele não possui circuitos.

  2. Escreva um algoritmo que recebe como entrada um grafo direcionado e que ou detecta um ciclo no grafo ou retorna uma ordenação topológica do grafo.

  3. Escreva uma variação do algoritmo para a detecção de circuitos em grafos direcionados; ela deve receber como entrada um grafo NÃO-DIRECIONADO, e então responder se o grafo possui ou não ciclos. Mostre que o seu algoritmo executa em tempo O(n).

  4. Foi demonstrado na aula de hoje que O(n+m) é um limite superior para o tempo de execução do algoritmo de detecção de circuitos discutido em sala. Nós poderíamos dizer que O(n) é também um limite superior? Prove que esse é o caso, ou então apresente uma demonstração de que há execuções do algoritmo que levam tempo superlinear para executar. Dica: considere o custo dos vértices pretos para o algoritmo.

• Aula 11 (2014-03-28): prova de que a detecção de ciclos via busca em profundidade leva tempo Teta(n); prova de que, para certas instâncias, a detecção de circuitos via busca em profundidade leva tempo Teta(n^2).

  Material complementar: aqui está uma versão escrita da prova da complexidade O(n) da detecção de ciclos em grafos não-direcionados.

  No livro: a aula incluiu resolver o exercício 22.4-3, sobre detecção de ciclos.

  Exercícios: os mesmos da aula anterior sobre ordenação topológica.

• Aula 12 (2014-04-02): prova de que todo grafo direcionado sem circuitos e com n ≥ 1 vértices possui um vértice no qual não chegam arestas; prova de que todo grafo direcionado possui uma ordenação topológica sse ele não possui circuitos; concepção, em alto nível, de um algoritmo para obter uma ordenação topológica de um grafo direcionado (ou informar que ele possui circuitos).

  Material complementar: aqui estão versões escritas das demonstrações dos lemas provados na aula de hoje.

  Exercícios:

  1. Escreva de forma precisa o algoritmo para obtenção de ordenação topológica (ou detecção de circuitos) que foi discutido em sala.

  2. Na aula de hoje nós percebemos que ordenações topológicas e circuitos estão fortemente relacionados. Assim, dado que nós já tínhamos um algoritmo de detecção de circuitos (via busca em profundidade), modifique-o para produzir uma ordenação topológica do grafo.

  3. Os algoritmos das questões anteriores possuem boas complexidades? Se não, modifique-os de forma que passem a ter.

  4. Prove que os algoritmos obtidos nos exercícios anteriores são corretos. Procure fazer demonstrações não muito extensas, e ao mesmo tempo expressar a essência do argumento. (Talvez seja uma boa ideia conceber toda a demonstração mentalmente em primeiro lugar, e só então escrever os argumentos.)

  5. Num grafo não-direcionado, uma componente conexa é um conjunto maximal de vértices {v_1,...,v_k} tal que, para todos v_i e v_j no conjunto, existe um caminho entre v_i e v_j.

     Num grafo direcionado G = (V,E), é possível existir um caminho de "u" a "v" mas não o contrário. Assim, define-se componente fortemente conexa como um conjunto maximal de vértices {v_1, ..., v_k} tal que, para todos v_i e v_j no conjunto, existe um caminho orientado de v_i a v_j e outro de v_j a v_i. Além disso, uma decomposição de um grafo direcionado G em componentes fortemente conexas é um conjunto cujos elementos são componentes fortemente conexas de G, e tal que todo vértice do grafo pertence a exatamente uma das componentes conexas do conjunto.

     Prove então que todo grafo direcionado possui exatamente uma decomposição em componentes fortemente conexas (em outras palavras, que não existem duas decomposições diferentes de um mesmo grafo em componentes fortemente conexas).

  6. Conceba um algoritmo para obter as componentes fortemente conexas de um grafo direcionado qualquer.

• Aula 13 (2014-04-04): escrita de um algoritmo iterativo para a obtenção de ordenação topológica (ou detecção da existência de circuitos) em um grafo direcionado qualquer; apresentação e discussão de invariantes para o laço principal do algoritmo; obtenção de variação da busca em profundidade para solucionar o mesmo problema; introdução ao problema da decomposição de um grafo em componentes fortemente conexas (CFC's).

  Exercícios: os mesmos da aula anterior sobre CFC's.

• Aula 14 (2014-04-09): discussão sobre componentes conexas de grafos não-direcionados e sobre como e por que obtê-las; discussão sobre como obter componentes fortemente conexas ("CFC's") de grafos direcionados; o grafo que representa as componentes fortemente conexas e conexões entre elas; proposta de algoritmo para resolver o problema por meio de apenas duas buscas em profundidade no grafo.

  Exercícios:

  1. Em sala, o seguinte algoritmo foi proposto para resolver o problema de computar as componentes fortemente conexas de um grafo direcionado qualquer:

     Algoritmo: Comp_Fort_Conexas
     Entrada:   um grafo direcionado G = (V,E)
     Saída:     um conjunto de subconjuntos de V
     -------------------------------------------
     01. execute em G uma busca em profundidade
     02. seja P a ordenação de V na qual ocorre 1o
           quem foi pintado de preto 1o na busca anterior
     03. pinte todos os vértices de G de branco
     04. CFC := conjunto vazio
     05. para cada vértice v de G, NA ORDEM P
     06. | se v está branco
     07. | | C := {v}
     08. | | realize uma busca em profundidade a partir de v,
         | |   inserindo em C todos os vértices descobertos nessa busca
     09. | CFC := CFC união {C}
     10. retorne CFC
     

     O algoritmo acima está correto? Argumente que sim, ou então apresente um contraexemplo, e, neste último caso, apresente uma correção do algoritmo.

  2. Qual é a complexidade assintótica do tempo de execução do algoritmo para o cálculo da decomposição de um grafo em CFC's?

  3. Até agora, na disciplina, nós vimos duas estratégias básicas de percurso em grafo: a busca em largura e a busca em profundidade. Até agora, porém, essas buscas estiveram incorporadas em algoritmos que realizavam tarefas particulares: detectar ciclos ou circuitos, percorrer em ordem de distância, obter ordenação topológica, etc. Tente escrever algoritmos para essas buscas que sejam independentes de aplicação.

• Aula 15 (2014-04-11): desenvolvimento de algoritmo para a decomposição de um grafo direcionado em componentes fortemente conexas.

  Material complementar: aqui está uma versão escrita do algoritmo que obtivemos e da prova de que ele funciona.

  Exercícios:

  1. Demonstrar por conta própria os resultados argumentados em sala.

• 2014-04-16: Prova 1.

• 2014-04-18: sem aula (feriado nacional).

• Aula 16 (2014-04-23): discussão sobre o problema da obtenção de caminhos mínimos, a partir de um dado vértice até todos os demais vértices do grafo, em grafos não-direcionados e ponderados; ideia de solução realizando-se uma busca em largura em grafo subdividido; ideia de solução por expansão criteriosa da fronteira de vértices "visitados".

  Exercícios:

  1. Complete o algoritmo cuja ideia foi combinada em sala, e cuja escrita foi também iniciada em sala.

  2. Argumente a correção do algoritmo; quais são as principais ideias?

  3. Qual é a complexidade do tempo de execução do algoritmo?

  4. Se o problema fosse encontrar um caminho mínimo entre dois dados vértices, o algoritmo obtido teria uma melhor complexidade de tempo de execução no pior caso?

  5. Prove ou refute: o algoritmo obtido serve também caso o grafo possua arestas de peso negativo mas não possua ciclos de peso negativo? Se não, tente obter um algoritmo que sirva nesse caso.

• Aula 17 (2014-04-25): término da escrita do algoritmo de Dijkstra para caminhos mínimos em grafos ponderados com números não-negativos (ver observação abaixo); cálculo da complexidade do tempo de execução do algoritmo com implementação via vetores e com implementação via montes ("heaps") binários; no caso da implementação via montes, observação de particularidades de implementação implicadas pelo uso da operação de aumento de prioridade de um elemento.

  Observação: o algoritmo escrito foi este abaixo.

  algoritmo: cam_mín
  entrada:   grafo não-direcionado G=(V,E),
             função w: E -> R_+,
             vértice o de G
  saída:     informação pai[v] e d[v] para cada v \in V
  01. para cada vértice v de G
  02. | cor[v] := branco
  03. | pai[v] := nulo
  04. | d[v] := infinito
  05. cor[o] := preto
  06. d[o] := 0
  07. para cada vizinho v de o
  08. | d[v] := w(o,v)
  09. | pai[v] := o
  10. enquanto houver vértice v tal que cor[v] = branco e d[v] != infinito
  11. | u := um vértice branco de menor distância
  12. | cor[u] := preto
  13. | para cada vizinho v de u
  14. | | se d[v] > d[u] + w(u,v)
  15. | | | d[v] := d[u] + w(u,v)
  16. | | | pai[v] := u
  17. retorne "pai" e "d".
  

  Como explicado em sala, o código que seria escrito originalmente incluiria preceder a linha 14 acima pelo teste se cor[v] = branco, o qual, entretanto, foi verificado não ser essencial para a corretude do algoritmo. Essa linha adicional deixa mais claro, entretanto, que nem todos os vizinhos de u precisam passar pelo teste da linha 14.

  Exercícios:

  1. Com relação à complexidade do tempo de execução do algoritmo, em que casos é preferível implementá-lo via montes binários, ao invés de via vetor simples?

  2. Os demais exercícios da aula anterior continuam válidos.

• Aula 18 (2014-04-30): comparação das complexidades do tempo de execução do algoritmo de Dijkstra quando implementado via vetores simples e quando via montes (“heaps”) binários; resumo de técnicas de análise de complexidade: soma de limites superiores de instruções individuais, análise agregada e análise amortizada; apresentação do custo amortizado das operações de um monte de Fibonacci; tempo de execução do algoritmo de Dijkstra quando implementado via montes de Fibonacci; montes de Fibonacci na prática (menção aos montes de pareamento – “pairing heaps”); prova escrita mas informal da corretude do passo crucial do algoritmo de Dijkstra; o problema de caminhos mínimos com único destino; o problema de caminhos mínimos com arestas de pesos negativos.

  Exercícios:

  1. Prove que o algoritmo de Dijkstra não mais funciona na presença de arestas de pesos negativos.

  2. Prove que, na presença de arestas de pesos negativos, um grafo pode não possuir um passeio de peso mínimo.

  3. Escreva um algoritmo que calcule caminhos mínimos em grafos com arestas de pesos negativos, caso o grafo não possua ciclos de pesos negativos, ou que detecte a presença de tais ciclos no grafo, em caso contrário. Em seguida, prove a correção do seu algoritmo.

  4. Escreva em detalhes duas versões especializadas do algoritmo de Dijkstra, uma supondo vetor simples e outra monte binário. A segunda versão deve deixar explícita a necessidade de um vetor auxiliar que armazene as posições dos elementos no monte.

  5. O que você acha de provar a corretude do algoritmo de Dijkstra de forma precisa, usando variantes e invariantes?

• Aula 19 (2014-05-02): apresentação do problema de caminhos mínimos com arestas de pesos possivelmente negativos; discussão de fatos básicos a respeito do problema; escolha pela versão do problema em que o grafo de entrada é direcionado; elaboração de algoritmo para o caso em que o grafo não possui circuitos de pesos negativos;

  Observação: aqui está uma versão escrita (e completa) dos resultados deixados incompletos no final da aula.

  Exercícios:

  1. Usando o último resultado demonstrado no arquivo em anexo (acima), prove que, ao fim do algoritmo, todo vértice atingível a partir de "o" tem a sua distância corretamente calculada pelo algoritmo.

  2. O algoritmo elaborado em sala funciona garantidamente apenas quando o grafo de entrada não possui circuitos de peso negativo. Escreva um algoritmo para detectar a presença de tais ciclos num grafo qualquer. Em seguida, utilize-o para escrever um algoritmo que (1) informa se um dado grafo possui ou não ciclos de pesos negativos, e (2) se o grafo não possuí-los, calcula as distâncias de um dado vértice "o" a todos os demais vértices do grafo.

  3. O problema da árvore geradora mínima é definido como segue: dados um grafo não-direcionado G=(V,E) e uma função w : E → ℜ, encontrar um subgrafo de G que seja uma árvore, que contenha todos os vértices de G – isto é, seja “geradora” – e que tenha o menor peso dentre todas as árvores geradoras de G. Tente elaborar um algoritmo para resolver esse problema.

     Tente elaborar um algoritmo para resolver esse problema.

• Aula 20 (2014-05-07): recapitulação dos lemas do anexo da aula passada; esboço de prova da correção do algoritmo da aula anterior; discussão sobre como detectar circuitos negativos.

  Exercícios:

  1. A seguinte modificação da busca em profundidade detecta corretamente circuitos de pesos negativos?

     Para cada aresta de retorno (u,v) – isto é, para cada vizinho "v" cinza de um vértice "u" –, verifique o peso do circuito <v, ..., pai(pai(u)), pai(u), u, v>, e retorne "sim" caso esse peso seja negativo. Ao fim da busca, caso nenhum circuito de peso negativo tenha sido detectado, retorne "não".

     Se sim, qual é a complexidade do tempo de execução do algoritmo? Se não, mostre um contraexemplo.

  2. Materialize num algoritmo a última ideia discutida em sala para a detecção de circuitos de pesos negativos.

  3. Tente resolver o problema da árvore geradora mínima introduzido nos exercícios da aula passada.

• Aula 21 (2014-05-09): apresentação da versão completa do algoritmo de caminhos mínimos Bellman-Ford; enunciado (e indicação da ideia de uma prova) de um lema relacionando, para cada vértice "v", o valor de "d[v]" e a atingibilidade de "v" a partir do vértice de origem (numa execução de Bellman-Ford); prova de que, se o grafo G de entrada do algoritmo tem um circuito de peso negativo atingível a partir do vértice de origem, então o algoritmo detecta esse fato; introdução do problema de árvores geradoras mínimas (AGM), e discussão sobre como resolvê-lo.

  Exercícios:

  1. Em sala, uma das ideias consideradas para resolver o problema da AGM foi começar com um subgrafo sem arestas e, considerando as arestas do grafo original em ordem crescente de peso, inserir cada aresta no grafo sendo construído, exceto se tal operação levar a um grafo cíclico, e parando-se o processo quando |V|-1 arestas já tiverem sido inseridas. Essa estratégia sempre funciona? Prove ou refute. Além disso, se funcionar, como podemos implementar de forma eficiente o teste que decide a inserção de cada aresta?

  2. Outras estratégias para resolver o problema da AGM foram consideradas em sala. (Uma sugestão, por exemplo, era a de modificar o algoritmo de Dijkstra, adaptando-o ao novo problema.) Verifique se essas outras estratégias funcionam, e a complexidade dos algoritmos correspondentes.

• Aula 22 (2014-05-14): recapitulação do problema da Árvore Geradora Mínima (AGM) e das ideias da aula anterior para solucionar o problema; escrita, em alto nível, de algoritmo para resolver o problema (estratégia baseada na ordenação de todas as arestas do grafo); discussão sobre detecção de ciclos no algoritmo; Tipo Abstrato de Dados para representar conjuntos disjuntos; ideia de estrutura de dados para implementar esse TAD.

  Exercícios:

  1. Implemente a estrutura de dados para conjuntos disjuntos cuja ideia foi discutida em sala.

  2. No caso da estrutura da questão anterior, se sobre ela são realizadas "m" operações, "n" das quais são chamadas à função "criarConjunto", qual é, no máximo, o custo das "m" operações? (Isto é, apresente um limite superior para esse custo.)

  3. Reescreva o algoritmo de AGM que foi escrito em alto nível em sala. A nova versão deve ser mais detalhada, e em particular deve explicitar o uso da estrutura de dados para conjuntos disjuntos.

  4. Em sala foi discutida também uma estratégia baseada em "expansão de fronteira", de certa forma semelhante ao algoritmo de Dijkstra, para o problema da AGM. Escreva um algoritmo que implemente essa estratégia, calculando a complexidade do tempo de execução dele.

  5. As estratégias discutidas em sala realmente levam a algoritmos corretos para o problema da AGM? Prove ou refute.

• Aula 23 (2014-05-16): escrita e explicação de algoritmos implementando a estrutura de dados para conjuntos disjuntos discutida na aula anterior; lema apresentando limite superior para o tempo de execução de uma sequência de operações nessa estrutura (prova no anexo abaixo); escrita do algoritmo de Kruskal, tomando por base as operações sobre conjuntos disjuntos.

  Observações:

  • Aqui está uma versão escrita da demonstração apresentada em sala sobre a estrutura de dados para conjuntos disjuntos.

  • As florestas de conjuntos disjuntos são outra implementação do TAD Conjuntos Disjuntos, e executam em tempo assintoticamente menor. A análise dessa estrutura, entretanto, é elaborada e está fora do escopo da nossa disciplina — mas está no Cormen para os curiosos.

  Exercícios:

  1. Qual é a complexidade do algoritmo de Kruskal, conforme apresentado em sala?

  2. Prove que o algoritmo de Kruskal é correto: qual é o passo crucial, e como se o justifica?

  3. Idem exercícios 4 e 5 da aula anterior.

• Aula 24 (2014-05-21): complexidade do algoritmo de Kruskal; discussão sobre a correção do algoritmo; definições auxiliares: sub-AGM, corte, aresta cruzar um corte, corte respeitar conjunto de arestas, aresta leve; prova do “teorema da aresta segura” [Cormen 2ª edição, teorema 23.1].

  Exercícios:

  1. Use o teorema da aresta segura para mostrar que "F é uma sub-AGM de G" é um invariante do laço principal do algoritmo de Kruskal.

  2. Idem exercício 3 da aula passada.

• Aula 25 (2014-05-23): prova da correção do passo principal do algoritmo de Kruskal; escrita e cálculo da complexidade do algoritmo de Prim; introdução ao problema de fluxo máximo em grafos.

  Exercícios:

  1. Prove a correção do algoritmo de Prim, com base no teorema da aresta segura.

  2. Com relação ao problema de fluxo máximo informalmente introduzido em sala:

     1. Formalize a definição do problema.

     2. Com base na definição formal do problema, prove que o fluxo que sai da origem é igual ao fluxo que chega ao destino.

     3. Tente obter um algoritmo para resolver o problema.

• Aula 26 (2014-05-28): discussão sobre e definição formal do problema de fluxo máximo em grafos; definição da notação de soma implícita; apresentação de exercícios.

  Observação: o argumento apresentado em sala sobre o cancelamento (local) do fluxo de dois caminhos que possuam arcos opostos pode ser formalizado como segue (veja também a figura abaixo) — atente que o argumento abaixo não faz uso da definição formal do problema de fluxo, que foi apresentada após a discussão em questão sobre o cancelamento de fluxos que passam por arestas opostas.

  

  Sejam

  • X = < a_1 = o, a_2, ..., a_p = u, a_{p+1} = v, ..., a_m = d >

  • Y = < b_1 = o, b_2, ..., b_q = v, b_{q+1} = u, ..., b_n = d >

  dois caminhos orientados de "o" a "d", o primeiro possuindo o arco (u,v) e o segundo o arco (v,u). Suponha ainda, sem perda de generalidade (por simetria), que pelo caminho X passa x de fluxo, e que por Y passa y, com x ≥ y. Assim sendo, os caminhos X e Y podem ser substituídos pelos três caminhos a seguir, pelos quais passam os valores indicados de fluxo:

  • C = < a_1 = o, a_2, ..., a_p = u, b_{q+2}, ..., b_n = d >, passando y de fluxo.

  • X, passando x-y de fluxo.

  • D = < b_1 = o, b_2, ..., b_q = v, a_{p+2}, ..., a_m = d >, passando y d fluxo.

  Observe que, com a substituição acima, a mesma quantidade de fluxo continua passando por cada aresta do grafo, exceto no caso das arestas (u,v) e (v,u), por onde passava x e y de fluxo, e onde passa a passar x-y e 0, respectivamente. Além disso, a substituição em questão não altera o saldo de fluxo (isto é, a diferença entre o fluxo que sai e o fluxo que chega) em "u" ou em "v".

  Exercícios:

  1. Prove o lema preliminar enunciado em sala, sobre conjuntos e a notação de soma implícita [Cormen 2ª edição, lema 26.1]. Não se esqueça de interpretar os resultados.

  2. Prove que, para qualquer fluxo f, |f| = f(V,d), isto é, que o fluxo que chega em "d" é igual ao fluxo que sai de "o".

  3. Prove ou refute: para qualquer fluxo f, se (1) R,S ⊆ V; (2) R ∩ S = ∅; e (3) o,d ∉ S, então f(R,S) = f(S,V \ (R ∪ S)). Além disso, como se pode interpretar esse resultado?

  4. Prove que, dado S ⊆ V tal que o ∈ S e d ∈ T = V\S, então |f| = f(S,T) ≤ c(S,T). Além disso, como se pode interpretar esse resultado?

  5. Nós definimos o problema de fluxo para grafos direcionados. Agora, levando em consideração que todo grafo não-direcionado G = (V,E) induz um grafo direcionado — a saber, o grafo G' = (V,E') tal que E' = { (u,v) : {u,v} ∈ E } (se G for ponderado, então G' também o é, sendo w(u,v) igual em G e G') —:

     1. Defina o problema de fluxo máximo para grafos não-direcionados.

     2. Prove ou refute: se G = (V,E) é um grafo não-direcionado e f é um fluxo (de valor) máximo de G, então o valor de f é igual ao de um fluxo máximo do grafo orientado G' induzido por G.

• Aula 27 (2014-05-30): definição de rede de fluxo; prova e interpretação dos lemas dos exercícios 1 a 4 da aula anterior [Cormen 2ª edição, lemas 26.(1, 5, 6) e equação 26.3].

  Observação: uma partição {S,T} de V tal que o ∈ S e d ∈ T é chamada de corte da rede de fluxo G = (V,E).

  Exercícios:

  1. Prove ou refute: um fluxo f é máximo sse |f| = c(S,T) para algum corte {S,T} da rede de fluxo G = (V,E).

  2. Tente obter um algoritmo para resolver o problema de fluxo máximo, possivelmente levando em consideração os resultados obtidos até aqui.

• Aula 28 (2014-06-02, aula extra): tira-dúvidas sobre caminhos mínimos e AGM.

  Observação: aqui está uma solução para o exercício 24.3-6 de [Cormen, 2ª edição] — variação de Dijkstra em O(nW + m), sendo W o maior peso de aresta, e sendo os pesos todos inteiros.

• 2014-06-04: sem aula (paralisação de ônibus).

• 2014-06-06: AP2.

• Aula 29 (2014-06-07, aula extra): recapitulação do problema de fluxo máximo e dos resultados demonstrados em aulas anteriores; discussão sobre o exercício 1 da aula 27 (2014-05-30), e sobre solucionar o problema de fluxo máximo por meio de algoritmo baseado na obtenção sucessiva de caminhos; exemplo de algoritmo, baseado em caminhos, que nem sempre obtém um fluxo máximo, e observação de como "consertá-lo"; definição de capacidade residual, rede residual, caminho aumentante e capacidade residual de caminho aumentante; enunciado de exercícios.

  Exercícios:

  1. Mostre que, se "p" é um caminho aumentante, então "f + f_p" é um fluxo em G, e tal que |f + f_p| > |f|, sendo f_p a função tal que f_p(u,v) vale:

     • c_f(p), se (u,v) ∈ p;

     • −c_f(p), se (v,u) ∈ p;

     • 0, em caso contrário.

  2. Mostre que as seguintes afirmações são equivalentes:

     1. "f" é um fluxo máximo.

     2. Não existe caminho aumentante relativo a "f".

     3. |f| = c(S,T), para algum corte {S,T}.

  3. Escreva um algoritmo que obtenha um fluxo máximo pela sucessiva descoberta de caminhos aumentantes. Qual é a complexidade do tempo de execução do algoritmo?

  4. O "algoritmo falho" acima passa a funcionar caso o caminho "p" escolhido em cada iteração seja mínimo em número de arestas?

• Aula 30 (2014-06-11): recapitulação das definições e enunciados da aula anterior; demonstração do teorema “fluxo máximo, corte mínimo”; escrita do algoritmo de Ford-Fulkerson na sua forma geral; ideia da prova do limite |f*| para o número de iterações do laço principal do algoritmo, no caso de rede de capacidades inteiras; exemplo de instância na qual o algoritmo executa em |f*| iterações, |f*| não sendo função de |E|.

  Observação: veja na Wikipédia um exemplo de rede com capacidades irracionais na qual o algoritmo de Ford-Fulkerson nem termina e nem sequer converge para um fluxo máximo.

  Exercícios:

  1. Prove que, se "G" é uma rede de fluxo de CAPACIDADES INTEIRAS, "f" um FLUXO INTEIRO e "p" um caminho aumentante relativo a "G" e "f", então f_p também é um fluxo inteiro.

  2. Prove que, no caso de uma rede de CAPACIDADES INTEIRAS, o algoritmo de Ford-Fulkerson executa no máximo |f*| iterações do laço principal, sendo f* um fluxo máximo da rede.

  3. Em sala, tentou-se argumentar que o algoritmo de Ford-Fulkerson executaria em no máximo |E| iterações do laço principal, pois cada caminho aumentante exaure a capacidade residual de algum par (u,v) ∈ V². Chamemos um tal par (u,v) de crítico. Nós vimos então um exemplo de que uma aresta pode ser crítica em várias iterações do algoritmo. Quantas vezes uma aresta pode ser crítica durante a execução de Ford-Fulkerson, caso os caminhos aumentantes escolhidos pelo algoritmo sejam sempre mínimos em número de arestas? Nesse caso, qual é a complexidade de Ford-Fulkerson?