MCTA027-17 - Teoria dos Grafos (2019 Q3)

Professora: Carla Negri Lintzmayer, Sala 508-2, carla.negri@ufabc.edu.br

Avisos importantes (fique atento sempre!)

[25/02] Notas da prova de recuperação. Entre em contato por e-mail em caso de qualquer dúvida.
―― novos ↑ ――

[03/02] Avisos sobre a prova de recuperação: [13/12] Atenção! Avisos semifinais: [12/12] Atenção! Hoje, no horário da aula (19h-21h) estarei na minha sala para atendimentos em geral.
[08/12] O atendimento do prof. Maycon dessa segunda (9/12) será realizado pelo prof. Guilherme Mota (sala 530-2).
[01/12] Atenção para mudança nas datas das provas. Havendo qualquer problema, entrem em contato por e-mail o quanto antes. A lista 4 pode ser entregue até o dia 05/12 às 19h, sem penalidade na nota.
[29/11] Formulário de consulta sobre as datas da P2 e da REC.
[26/11] As notas da lista 2 e da parte teórica da lista 3 estão disponíveis. Anotações nos pdfs foram enviadas para seus e-mails.
[20/11] Lista 4 disponível.
[20/11] A lista 3 pode ser entregue até o dia 24/11 às 23h, sem penalidade na nota.
[16/11] A lista 3 pode ser entregue até o dia 21/11 às 19h, sem penalidade na nota.
[08/11] As notas da prova 1 estão disponíveis. Dúvidas podem ser tiradas no horário de atendimento ou em outro horário melhor, marcado por e-mail. Não deixem de me procurar!
[04/11] Lista 3 disponível.
[30/10] Material (extra) disponível sobre indução e solução dos exercícios de indução das listas 1 e 2.
[28/10] A lista 2 pode ser entregue até amanhã, 29/10, às 20h, sem penalidade na nota.
[28/10] As notas da parte teórica da lista 1 está disponível. Anotações no pdfs foram enviadas para seus e-mails.
[15/10] Lista 2 disponível.
[12/10] Data de entrega da Lista 1 adiada. Feliz dia das crianças!
[01/10] Lista 1 disponível.
[19/09] Página da disciplina no ar.

Conteúdo dessa página

piadinha

Dias, horários e local das aulas (voltar ao topo)

Terças-feiras, das 21h às 23h, sala S-302-2.
Quintas-feiras, das 19h às 21h, sala S-311-2.

Dias, horários e local de atendimento (voltar ao topo)

Neste quadrimestre o conteúdo da disciplina será unificado com as turmas dos Profs. Guilherme Mota e Maycon Sambinelli.

Hora Seg Ter Qua Qui Sex
10h Diogo Mota
11h Diogo Mota
12h
13h
14h
15h
16h
17h
18h Maycon Carla
19h Maycon Carla Aula
20h Aula
21h Aula
22h Aula
     

Assim, alunos de todas as turmas podem escolher livremente entre os horários abaixo:

  • Quartas-feiras, das 18h às 20h, com a profa. Carla, na sala 508-2 do bloco A.
  • Segundas-feiras, das 18h às 20h, com o prof. Maycon, na sala 518-2 do bloco A.
  • Quintas-feiras, das 10h às 12h, com o prof. Mota, na sala 530-2 do bloco A.
  • Quartas-feiras, das 10h às 12h, com o monitor Diogo, sala 310-2 do bloco A.

Nesse horários não é preciso confirmar ou marcar, apenas apareça!
(Traga seu código em um pendrive ou mesmo seu notebook para as dúvidas relacionadas a implementação.)

Se não puder, me mande um e-mail para combinarmos algo.

Algumas dúvidas (mais simples) podem ser tiradas por e-mail.

Ementa da disciplina (voltar ao topo)

Conceitos básicos de grafos dirigidos e não dirigidos. Passeios, caminhos, circuitos. Grafos bipartidos e multipartidos. 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.

Objetivos: (i) Apresentar os conceitos e resultados básicos da Teoria dos Grafos; (ii) Permitir o uso de grafos e suas propriedades para modelar problemas computacionais; (iii) Apresentar algoritmos eficientes para problemas recorrentes em computação; (iv) Tornar familiares certos padrões de soluções que ocorrem frequentemente em problemas envolvendo grafos.

(Disponível na pg. 79 do projeto pedagógico.)

Recomendação (voltar ao topo)

Disciplinas: Matemática Discreta; Processamento da Informação; Algoritmos e Estruturas de Dados I

Para facilitar o acompanhamento do curso, é recomendado que você já possua: Materiais de apoio para esses tópicos:

Bibliografia e outros materiais (voltar ao topo)

[BM] Bondy, J. A.; Murty, U. S. R. Graph theory. Graduate Texts in Mathematics. Springer. New York. 2008.
[V] Velleman, D. J.. How to Prove It: A Structured Approach. Second Edition. Cambridge University Press. 2006.
[S] Sedgewick, R.. Algorithms in C, part 5: graph algorithms. 3rd edition. Addison-Wesley. 2002.
[BMwa] Bondy, J. A.; Murty, U. S. R.. Graph theory with applications. Elsevier. 1976.
[D] Diestel, R.. Graph Theory. 5th edition. Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume 173. 2016.
[W] West, D. B.. Introduction to Graph Theory. 2nd edition. Pearson Education. New Jersey. 2001.
[CLRS3] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 3rd ed. MIT Press. 2009.
[M] Mota, G. O.. Notas de aulas - Teoria dos grafos. Em constante atualização.
[LM] Lintzmayer, C. N.; Mota, G. O.. Notas de aulas - Análise de algoritmos e estruturas de dados. Em constante atualização.
Grupo de Whatsapp criado e mantido pelos alunos.

Cronograma e notas de aula (voltar ao topo)

As referências utilizadas nas aulas serão atualizadas durante o curso.

Sobre qualquer material feito por mim, participe do banco de informantes.

Aula Data Tópicos
1 24/9 Apresentação da disciplina. Introdução à teoria dos grafos. Métodos de demonstração.
Referências: Cap. 3, 6 [V], Cap. 4, 5 Matemática discreta para computação.
Extras: slides usados na aula.
26/9 Sem atividades acadêmicas: UFABC para todos
Dica de leitura: capítulos 3 e 6 do livro "Velleman, D. J.. How to Prove It: A Structured Approach. Second Edition. Cambridge University Press. 2006."
2 1/10 Conceitos básicos.
Referências: Cap. 1.1 [BM].
Extras: Notas da aula, Cap. 1 [M], exemplos de implementação.
3 3/10 Representações. Subgrafos e passeios. Grafos bipartidos.
Referências: Cap. 2.1, 2.2 [BM].
Extras: Notas da aula, Cap. 1, 2 [M].
4 8/10 Caracterização de bipartidos. Teorema de Mantel.
Extras: Notas da aula, Cap. 1, 2 [M].
5 10/10 Minimalidade e maximalidade. Cintura e diâmetro. Componentes.
Referências: Cap. 2.1 [BM].
Extras: Notas da aula, Cap. 1 [M].
6 15/10 Arestas e vértices de corte. Grafos Eulerianos e caracterizações. Decomposição em ciclos.
Referências: Cap. 3.1, 3.2, 3.3, 2.4 [BM].
Extras: Notas da aula, Cap. 3 [M].
7 17/10 Algoritmo de Fleury. Árvores e caracterizações.
Referências: Cap. 3.3, 4.1 [BM].
Extras: Notas da aula, Cap. 22 [LM], Cap. 4 [M].
8 22/10 Caracterizações de árvores.
Referências: Cap. 4.1 [BM].
Extras: Notas da aula, Cap. 4 [M].
9 24/10 Busca em largura (com corretude).
Referências: Cap. 6.1 [BM], Cap. 22.1, 22.2 [CLRS3].
Extras: Notas da aula, Cap. 20 [LM].
10 29/10 Revisão e solução de exercícios.
Referências: listas.
Extras: sobre indução e solução dos exercícios de indução das listas 1 e 2.
11 31/10 Prova 1
12 5/11 Solução da P1. Algoritmo de Dijkstra e corretude.
Referências: Cap. 6.3 [BM], Cap. 24.3 [CLRS3].
Extras: Notas da aula, Cap. 23 [LM], animação do Dijkstra.
13 7/11 Emparelhamentos. Teorema de Berge. Cobertura por vértices.
Referências: Cap. 16.1, 16.2 [BM].
Extras: Notas da aula, Cap. 6 [M].
14 12/11 Teorema de Konig. Teorema de Hall.
Referências: Cap. 16.2 [BM].
Extras: Notas da aula, Cap. 6 [M].
15 14/11 Corolário do Teorema de Hall. Caminhos e ciclos Hamiltonianos. Teorema de Dirac.
Referências: Cap. 18.1, 18.3 [BM].
Extras: Notas da aula, Cap. 8 [M].
16 19/11 Coloração de vértices. Limitantes.
Referências: Cap. 14.1, 14.3 [BM].
Extras: Notas da aula, Cap. 9 [M].
17 21/11 Coloração de vértices. Coloração de arestas. Limitantes.
Referências: Cap. 17.1, 17.2 [BM].
Extras: Notas da aula, Cap. 10 [M].
18 26/11 Coloração de arestas. Limitantes. Grafos planares.
Referências: Cap. 17.1, 17.2 [BM].
Extras: Notas da aula, Cap. 10 [M], vídeo sobre grafos planares, por uma das melhores grafeiras que existem.
19 28/11 Grafos planares e não-planares. Teorema de Kuratowski.
Referências: Cap. 10.1, 10.3, 10.5, 15.1, 15.2 [BM].
Extras: Notas da aula, Cap. 12 [M], vídeo sobre grafos planares, por uma das melhores grafeiras que existem.
20 3/12 Revisão e solução de exercícios.
Referências: listas.
21 5/12 Revisão e solução de exercícios.
Referências: listas.
22 10/12 Prova 2
23 12/12 Atendimento na sala da professora.
24 15/02/2020 Prova de recuperação, 9h, sala S-301-2.

Plágio (voltar ao topo)

Listas de exercícios (voltar ao topo)

Lista 1: conteúdo das aulas 1 a 5 (disponível em 01/10 - entrega até 13/1020/10)
Lista 2: conteúdo das aulas 6 a 9 (disponível em 15/10 - entrega até 28/10)
Lista 3: conteúdo das aulas 12 a 15 (disponível em 5/11 - entrega até 19/1124/11)
Lista 4: conteúdo das aulas 16 a 19 (disponível em 20/11 - entrega até 3/1205/12)

Critérios de avaliação regular (voltar ao topo)

Mecanismo de recuperação (voltar ao topo)

Mecanismos de avaliação substitutivos (voltar ao topo)

A prova substitutiva será aplicada ao aluno que possuir justificativa de ausência em uma das provas. A listagem dos documentos aceitos como justificativa consta na resolução ConsEPE n° 181.
A nota obtida na prova substitutiva necessariamente substituirá a prova para a qual o aluno tem justificativa.

A data para realização da prova substitutiva deverá ser combinada com a professora por e-mail o quanto antes, assim que o aluno estiver em condições de realizá-la.
Carla Negri Lintzmayer - carla.negri@ufabc.edu.br