Ementa: Conceitos básicos de grafos dirigidos e não-dirigidos. Passeios, caminhos, circuitos. Grafos bipartidos e multi-partidos. Subgrafos. Isomorfismo. Conexidade. Florestas e árvores. Exemplos de problemas de interesse: coloração de vértices; clique máximo; caixeiro viajante; problemas de fluxo. Estruturas de dados para a representação de grafos. Percursos em grafos: em largura, em profundidade. Ordenação topológica. Árvores geradoras mínimas. Algoritmo de Kruskal. Caminhos mínimos em grafos: algoritmo de Dijkstra, algoritmo de Floyd-Warshall. Emparelhamentos: Teorema de Hall.

A availação consiste de três provas. Participação e entrega de exercícios serão considerados no conceito final. Todo aluno que entregar exercícios pode, eventualmente, ser arguido sobre a resolução; espera-se uma conduta honesta nessa parte da avaliação, clique aqui para uma referência de conduta.

[em 04/11] exerc 90 e 91 (na sala passei os ex. 89,90, está errado)

[em 04/12] exerc 158, pag 61.

Sub: O aluno que faltou em dia de prova por uma justificativa válida deve entrar em contato comigo em até 72hs para agendar uma substitutiva.

Exame: Qualquer aluno pode realizar o exame de recuperação. Nesse caso, o conceito final será o conceito obtido no exame. o ALUNOS QUE FOREM FAZER EXAME DEVEM ENVIAR EMAIL PARA O PROFESSOR ATÉ 9/12.

O resultado de cada avaliação é um conceito que reflete o desempenho do aluno em todo o curso até aquele instante: provas, exercícios e paricipação em aula. Isso significa que a cada cada conceito atribuído e divulgado durante o curso da disciplina leva em conta o resultado das avaliações até o momento.

O conceito final da disciplina poderá ser:

• F - Reprovado. O aluno deve cursar novamente a disciplina.
• C - Desempenho mínimo satisfatório, demonstrando capacidade de uso adequado dos conceitos da disciplina, habilidade para enfrentar problemas relativamente simples e prosseguir em estudos avançados.
• B - Bom desempenho, demonstrando boa capacidade de uso dos conceitos da disciplina.
• A - Desempenho excepcional, demonstrando excelente compreensão da disciplina e do uso da matéria.

Bibliografia

Básica:


• DIESTEL, R. Graph Theory, Springer, 2005. [511.5 / DIESgr3 / 3 ed.] [versão eletrônica]
• MANBER, Udi. Introduction to algorithms: a creative approach. Addison-Wesley.(Capítulo 7) [005.73 / MANi]


Material de apoio:


• Notas de aula pdf html
• Aqui está a versão que está sendo revisada com o andar da disciplina. Até o momentos os capítulos 1,2,3 foram revisados e corrigidos. Os exercícios atribuídos em aula referem-se à exercícios da versão não-revisada.


Complementar:


• BONDY, J. A.; MURTY, U. S. R. Graph theory. Graduate Texts in Mathematics, 244. Springer, New York, 2008.[511.5 / BONg][pdf]
• FEOFILOFF, P., KOHAYAKAWA, Y., WAKABAYASHI, Y. Teoria dos Grafos: uma introdução sucinta. [página web]
• FEOFILOFF, P. Algoritmos para Grafos em C via Sedgewick. [página web]
• CORMEN, Thomas H et al. Algoritmos: Teoria e prática// Introduction to algorithms. (capítulos sobre algoritmos em grafos)

Links

• Provas antigas.
• um jogo pras horas vagas.
• entrada no wikipedia e no mathworld.
• Graph theory in the information age, por Fan Chung.
• web pages as a graph
• Graph Algorithms Applet (manual)
• An application of graph theory to architecture
  
• Explained: Graphs, Larry Hardesty, MIT News Office.
• Beautiful conjectures in graph theory by A. Bondy
• Open problem garden -- Graph Theory
• Open problems for undergratuates
• Applications of Graph Theory, Shariefuddin Pirzada and Ashay Dharwadker
• applications of graph theory in computer science an overviewS.G.Shirinivas, S.Vetrivel , Dr. N.M.Elango Professor.
• Spectral Graph Theory and its Applications, Daniel A. Spielman
• Applications of Graph Theory in Chemistry, A. Balaban