CI065 - Algoritmos e Teoria dos Grafos

Bibliografia básica:

1. Graph Theory, R. Diestel.
2. Graph Theory with applications, A. Bondy e U.S.S.R. Murty. Veja aqui.
3. Algorithms, R. Sedgewick. (Capítulos sobre algoritmos em grafos)

Bibliografia complementar:

4. Graph Theory: An Introductory course, B. Bollobás.
5. Graph Theory, F. Harary.
6. Grafos e Algoritmos Computacionais, J.L. Szwarcfiter.
7. Grafos: Teoria, Modelos, Algoritmos, P.O. Boaventura Neto.
8. Data Structures and Algorithms, A.V. Aho, J.E. Hopcroft, J.D. Ullman.
9. Introduction to Algorithms, Cormen, Leiserson, Rivest e Stein (Capítulos sobre algoritmos em grafos). A biblioteca tem esse livro em português.

Sistema de avaliação

• Média ponderada de duas provas com peso dois com média das tarefas domésticas com peso um dá a média final.
• Tendo 75% de freqüência, o aluno com nota maior ou igual a 70 estará aprovado.
• Tendo 75% de freqüência, o aluno com nota maior ou igual a 40 e menor do que 70 estará habilidato a fazer a prova final.
• Em qualquer outro caso o aluno estará reprovado e será indicado se houve ou não infreqüência.
• O aluno que fizer a prova final estará aprovado apenas se a média aritmética da prova final e da média final for maior ou igual a 50.

• 1a. Lista de exercícios (pdf)
• 2a. Lista de exercícios (pdf)
• 3a. Lista de exercícios (pdf)
• 4a. Lista de exercícios (pdf)
• 5a. Lista de exercícios (pdf)
• 6a. Lista de exercícios (pdf)
• 7a. Lista de exercícios (pdf)
• 8a. Lista de exercícios (pdf)
• 9a. Lista de exercícios (pdf)
• 10a. Lista de exercícios (pdf)
• 11a. Lista de exercícios (pdf)

Aula 01 - Grafos: definição, representação geométrica, nomeclatura.

Aula 02 - Grau de um vértice. Vizinhança. Subgrafos.

Aula 03 - Subgrafo induzido. No. max. de arestas em grafos sem triangulos.

Aula 04 - Isomorfismo. Outras noções de grafos.

Aula 05 - Representação computacional.

Aula 06 - Percuros em grafos, Busca em largura e Busca em profundidade.

Aula 07 - Caminhos.

Aula 08 - Circuitos.
 
Aula 09 - Grafos conexos.

Aula 10 - Grafos biconexos.

Aula 11 - Conexidade e aresta-conexidade de grafos.

Aula 12 - Prova de  aresta-conexidade >= conexidade. Construção de grafos conexos com mínimo de arestas.

Aula 13 - Árvores.

Aula 14 - Aula suspensa pelo reitor.

Aula 15 - Aula exercicios.

Aula 16 - Prova.

Aula 17 - Árvores.

Aula 18 - Trilhas eulerianas.

Aula 19 - Circuitos hamiltonianos.

Aula 20 - Emparelhamentos: Teorema de Konig.

Aula 21 - Emparelhamentos: Teorema de Hall.

Aula 22 - Emparelhamentos: Metodo Hungaro.

Aula 23 - Caminhos mínimos: Dijkstra.

Aula 24 - Caminhos mínimos: Floyd-Warshall.

Aula 25 - Árvore geradora mínima: Prim.

Aula 26 - Árvore geradora mínima: Kruskal.

Aula 27 - Union-Find com vetor e lista-ligada

Aula 28 - Union-Find com foresta/uniao por rank/compressao de caminhos

Aula 29 - Aula de exercicios.

Aula 30 - Aula de exercicios.

Aula 31 - Prova.




       September 2004            October 2004            November 2004    
     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa     Su Mo Tu We Th Fr Sa 
               1  2  3  4                     1  2         1  2  3  4  5  6 
      5  6  7  8  9 10 11      3  4  5  6  7  8  9      7  8  9 10 11 12 13 
     12 13 14 15 16 17 18     10 11 12 13 14 15 16     14 15 16 17 18 19 20 
     19 20 21 22 23 24 25     17 18 19 20 21 22 23     21 22 23 24 25 26 27 
     26 27 28 29 30           24 25 26 27 28 29 30     28 29 30 
                              31