Nesta disciplina, apresentamos conceitos básicos da teoria dos grafos e como representar um grafo computacionalmente, apresentamos algoritmos eficientes para problemas clássicos em grafos e discutimos os tempos de execução e a correção dos algoritmos estudados.

Espera-se que ao final da disciplina o aluno seja capaz de modelar problemas em grafos, que o aluno conheça os principais problemas em grafos e os algoritmos eficientes que os resolvem. Espera-se também que o aluno tenha noções da complexidade de tempo de execução dos algoritmos cobertos ao longo do curso.

E-mails: Toda comunicação ‘aluno → professor’ por email deve ser com o endereço oficial.

Os comunicados gerais ‘professor → aluno’ serão pelo sigaa.

Programação da disciplina

Reposição dos feriados: não há

Programação das aulas

Ementa

Revisão da terminologia básica de Teoria dos Grafos. Noções de análise de algoritmos. Estruturas de dados para representação de grafos. Buscas em largura e profundidade e suas aplicações: caminhos mínimos sem pesos, componentes conexas. Grafos ponderados. Árvores geradoras mínimas: algoritmos de Prim e Kruskal. Grafos Eulerianos e Hamiltonianos. O Problema do Caixeiro Viajante. Digrafos: definições básicas, componentes fortemente conexas e ordenação topológica. Caminhos mínimos em digrafos ponderados: algoritmos de Dijkstra, Bellman-Ford e Floyd–Warshall. Fluxo máximo: algoritmo de Ford-Fulkerson e suas aplicações.

Bibliografia básica

• BONDY, J. A.; MURTY, U. S. R. Graph theory. New York: Springer, 2008. (Graduate Texts in Mathematics, v. 244).

• ERICKSON, Jeff. Algorithms. 1. ed. [S. l.], 2019. Disponível em: https://jeffe.cs.illinois.edu/teaching/algorithms/.

• CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford. Algoritmos: teoria e prática. 3. ed. Rio de Janeiro: Elsevier, 2012.

Bibliografia complementar

1. BRASSARD, Gilles; BRATLEY, Paul. Fundamentals of algorithmics. Englewood Cliffs: Prentice Hall, 1996.

2. SEDGEWICK, Robert. Algorithms in c, Part 5: Graph Algorithms. 3. ed. Reading, USA: Addison Wesley Professional, 2002. 482 p.

3. MANBER, Udi. Introduction to algorithms: a creative approach. Addison-Wesley.

4. DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos H.; VAZIRANI, Umesh V. Algorithms. Boston, USA: McGraw-Hill, 2008.

5. David JOYNER, Minh VAN NGUYEN, Nathann COHEN. Algorithmic Graph Theory, online, 2013.

Atendimento

Terças das 10h às 12h ou em horário previamente combinado pessoalmente ou por email.

Avaliação

2 provas: 27 ou 29/10 (ainda não decidi) e 01/12.

As avaliações são individuais, presenciais e sem consulta.

Na correção das avaliações serão considerados:

1. Apresentação clara, legível, discursiva, uniforme, objetiva das soluções dos problemas.

2. Atendimento às normas de correção ortográfica e gramatical.

3. Observância às orientações específicas da atividade/exercício.

Conceito final

Nas avaliações serão atribuídos concentos cujo resultado, ao final da disciplina, será de acordo com a seguinte tabela

Frequência mínima de 75%, caso contrário o conceito final é O.

Instruções para as provas

1. Podem utilizar lápis, desde que a escrita seja legível, ou caneta, exceto na cor vermelha.

2. Podem responder às questões em qualquer ordem.

3. Podem usar parte da folha de resposta como rascunho, identificando-a no topo da página com a palavra Rascunho.

4. Podem entregar a prova a qualquer momento, desde que assinem a lista de presença.

5. Devem trazer um documento com foto atual.

6. Devem deixar as mochilas no chão, com o celular dentro (desligado ou silenciado). É proibido o uso de eletrônicos (celular, calculadoras, smartwatches, etc), bem como bonés e chapéus.

7. Devem entregar a folha de questões juntamente com a folha de respostas.

8. Devem deixar sobre a carteira somente lápis, caneta, borracha, documento e garrafa d'água. Qualquer outro objeto deve ser guardado.

9. Ida ao banheiro apenas mediante a entrega definitiva da prova.

10. Todo aluno poderá, eventualmente e a critério do professor, ser arguido oralmente sobre as soluções apresentadas na prova e essa arguição será parte da avaliação.

O não cumprimento das instruções implica anulação da prova.

A constatação de fraude, o aluno será reprovado por conceito e frequência.

O Código de Ética da Universidade Federal do ABC

Estabelece em seu Artigo 25 que, quanto aos trabalhos acadêmicos, é eticamente inaceitável que os discentes: I. fraudem avaliações; II. fabriquem ou falsifiquem dados; III. plagiem ou não creditem devidamente autoria; IV. aceitem autoria de material acadêmico sem participação na produção; V. vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.

Recuperação

Tem direito ao exame recuperação, que engloba todo o conteúdo da disciplina, aqueles que foram aprovados com D ou reprovados com F e obtiveram frequência mínima. O resultado do exame é um conceito que compõe com o conceito final M obtido na avaliação regular da disciplina como segue:

A prova será em 8/12. O aluno interessado em realizar a recuperação deverá se manifestar de 04/12 a 06/12 por email ou através de formulário de acordo com as instruções que serão enviadas em um momento apropriado durante a disciplina.

Substitutiva

Nos casos previstos em resolução, mediante a devida comprovação. O aluno que perder prova e tiver interesse em fazer a substitutiva deve entrar em contato com o professor.

Links

1. Provas antigas

2. R. Bianconi, Como ler e estudar matemática?

3. Fernando Q. Gouvêa e Shai Simonson, How to Read Mathematics.

4. How to Read Mathematics? A study guide. Petra Schwer, Heidelberg, Summer 2026.