MCTA027-17 - Teoria dos Grafos

Terceiro Quadrimestre de 2019


Avisos importantes

Dias, horários e locais das aulas

Dias, horários e local de atendimento

Neste quadrimestre o conteúdo da disciplina será unificado com as turmas dos Profs. Guilherme Mota e Carla Negri Lintzmayer. Assim, alunos de todas as turmas podem escolher livremente entre os horários abaixo:

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

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.) Caso não possa comparecer em nenhum dos horários disponíveis, me avise por e-mail para combinarmos uma solução alternativa.

Ementa da disciplina

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

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

Livros

Notas de aula

Cronograma e notas de aula

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 [V].
2 1/10 Conceitos básicos e representações.
Referências: Cap. 1.1 [BM]. Extras: Notas da aula, Cap. 1 [M], exemplos de implementação.
3 3/10 Subgrafos e passeios. Grafos bipartidos. Teorema de Mantel.
Referências: Cap. 2.1, 2.2 [BM]. Extras: Notas da aula, Cap. 1 [M].
4 8/10 Cintura e diâmetro. Componentes. Arestas e vértices de corte.
Referências: Cap. 1.4, 2.1, 3.2, 5.1 [BM]. Extras: Notas da aula, Cap. 1 [M].
5 10/10 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]
6 15/10 Algoritmo de Fleury.
Referências: Cap. 3.3 [BM]. Extras: Notas da aula, Cap. 22 [LM]
7 17/10 Árvores e caracterizações.
Referências: Cap. 4.1 [BM]. Extras: Notas da aula, Slides, Cap. 4 [M]
8 22/10 Caracterizações de árvores e árvores geradoras.
Referências: Cap. 4.1 [BM]. Extras: Notas da aula, Slides, Cap. 4 [M]
9 24/10 Busca em largura (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.
11 31/10 Prova 1
12 5/11 Solução da P1. Algoritmo de Dijkstra.
Referências: Cap. 6.3 [BM], Cap. 24.3 [CLRS3]. Extras: Notas da aula, Slides, Cap. 23 [LM], Animação do Dijkstra
13 7/11 Emparelhamentos. Teorema de Berge.
Referências: Cap. 16.1, 16.2 [BM]. Extras: Notas da aula, Cap. 6 [LM]
14 12/11 Teorema de Hall e corolários. Cobertura por vértices. Teorema de Konig.
Referências: Cap. 16.1, 16.2 [BM]. Extras: Notas da aula, Cap. 6 [LM]
15 14/11 Grafos 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.
Referências: Cap. 14.1, 14.3 [BM]. Extras: Notas da aula, Cap. 9 [M]
17 21/11 Coloração de arestas.
Referências: Cap. 17.2, 17.2 [BM]. Extras: Notas da aula, Slides Cap. 10 [M]
18 26/11 Conjuntos independentes. Cliques.
19 28/11 Grafos planares e não-planares. Teorema de Kuratowski.
Referências: Cap. 10.1-10.3, 10.5 [BM]. Extras: Notas da aula, Slides Cap. 12 [M]
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 15/02/2020 Prova de recuperação (Sala a definir, 9h)

Listas de exercícios

Ao todo teremos 4 listas, cujos enunciados serão disponibilizados aqui, nas datas indicadas abaixo. As listas conterão exercícios teóricos e práticos.

A entrega deverá ser feita apenas pelo tidia (a menos que haja problemas no tidia nas datas em questão, caso em que elas podem ser entregues por e-mail).

Todos os prazos de entrega já estão definidos (marque na sua agenda!). Soluções entregues em no máximo 12h após o prazo serão aceitas em casos bem justificados. O critério de correção de uma lista será indicado na mesma. Qualquer detecção de plágio nas listas implicará em descarte dos conceitos atribuídos a TODAS as tarefas avaliativas regulares de TODOS os envolvidos, causando assim suas reprovações automáticas com conceito F (vide Seção plágio).

Critérios de avaliação regular

Mecanismo de recuperação

Mecanismos de avaliação substitutivos

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 o professor por e-mail o quanto antes, assim que o aluno estiver em condições de realizá-la.

Notas

Plágio

Entre outros, o código de ética da UFABC estabelece em seu artigo 25 que é eticamente inaceitável que os discentes:

  1. fraudem avaliações,
  2. fabriquem ou falsifiquem dados,
  3. plagiem ou não creditem devidamente autoria,
  4. aceitem autoria de material acadêmico sem participação na produção,
  5. vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.

Muitos ainda têm dúvidas sobre a interpretação das regras definidas pelo Código de Ética da UFABC. Por esta razão, diversos professores elaboraram um documento (disponível aqui) com vários exemplos e esclarecendo a interpretação das regras acima. Abaixo uma versão resumida, que não substitui de modo algum sua leitura. Sempre consulte o documento completo ou converse com o seu professor em caso de dúvidas!