MCTA027-17 - Teoria dos Grafos Terceiro Quadrimestre de 2019


Avisos importantes

  • 🆕 24/02 - Nota da REC e média final disponibilizadas
  • 03/02 - Avisos sobre a prova de recuperação:
    • Plantão de atendimento profa. Carla: dia 10/02/2020, das 18h às 22h (sala 508-2).
    • Plantão de atendimento prof. Maycon: dia 12/02/2020, das 18h às 22h (sala 518-2).
    • A prova de recuperação será na sala S-301-2, a partir das 9h, no dia 15/02/2020 (sábado).
    • Por favor, me envie um e-mail se você for realizar a prova, para que eu possa imprimir uma quantidade correta de provas.
    • Tenha certeza de que leu o e-mail sobre detalhes da prova (enviado ano passado).
    • Mande um e-mail em caso de qualquer dúvida.
  • 06/12 - O atendimento do dia 09/12 (18h-20h) será realizado pelo Professor Guilherme Mota (Sala 530-2)
  • 03/12 - Mudança no horário de atendimento do dia 02/12 para o dia 03/12 das 18h às 20h.
  • 01/12 - Mudança nas datas da L4, P2, REC
  • 29/11 - Notas da L2 disponibilizadas
  • 29/11 - Formulário de consulta sobre as datas da P2 e da REC
  • 21/11 - Critério de avaliação atualizado para contemplar a nota substitutiva da P1
  • 21/11 - Lista 4 está disponível
  • 20/11 - Notas da P1 disponibilizadas
  • 20/11 - Prazo final para entrega da lista 3 foi adiado para o dia 24/11
  • 16/11 - Prazo final para entrega da lista 3 foi adiado para o dia 21/11
  • 07/11 - Lista 3 atualizada (um exercício extra foi adicionado)
  • 06/11 - Lista 3 de exercício está disponível
  • 28/10 - Envio da lista 1 corrigida por e-mail
  • 28/10 - Notas da Lista 1 (parte teórica) disponibilizada
  • 16/10 - Lista 2 de exercício está disponível
  • 10/10 - Entrega da Lista 1 foi adiada para 20/10
  • 10/10 - Atendimento do dia 14/10 será dado pela Profa. Carla na sala 508-2
  • 07/10 - Atendimento do dia 07/10 será dado pela Profa. Carla na sala 508-2
  • 03/10 - Criada a página da disciplina no Tidia
  • 02/10 - Lista 1 de exercício disponibilizada
  • 02/10 - Notas de aula da aula 2 e 3 disponibilizadas
  • 24/09 - Página da disciplina no ar.

Dias, horários e locais das aulas

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

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:

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

  • Conhecimentos de programação (em linguagem C), com boas noções de algoritmos
  • Familiaridade com estruturas de dados básicas (vetores, listas, pilhas, filas e árvores)
  • Capacidade para reconhecer argumentos lógicos em uma prova matemática (por indução, contradição, construção)
  • Familiaridade com linguagem matemática (como quantificadores lógicos, conjuntos, somatórios e manipulação de funções)

Materiais de apoio para esses tópicos:

Bibliografia e outros materiais

Livros

  • [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.

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.

  • As soluções dos exercícios teóricos deverão ser feitas à mão (capriche na letra!), escaneadas e um único arquivo em formato PDF deve ser entregue (sugestão de aplicativo: CamScanner).
  • As soluções dos exercícios práticos deverão ser feitas em linguagem C e um único arquivo em formato c deve ser entregue.

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).

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

Critérios de avaliação regular

  • A avaliação da disciplina constituirá da nota de duas provas, respectivamente denotadas por P1 e P2, e da média simples das notas das listas de exercícios, denotada por L, onde 0 ≤ P1,P2,L ≤ 10.
  • A prova 1 (P1) vale 40% da nota.
  • A prova 2 (P2) vale 40% da nota.
  • As listas (L) valem 20% da nota.
  • Sua média final (MF) antes da recuperação, portanto, será MF = 0.4 x P1' + 0.4 x P2 + 0.2 x L
    • onde P1' = max {P1, P2}
  • Seu conceito final será:
    • A, se MF ≥ 8.5
    • B, se 7.0 ≤ MF < 8.5
    • C, se 6.0 ≤ MF < 7.0
    • D, se 5.0 ≤ MF < 6.0
    • F, se MF < 5.0
    • O, se ausência total exceder 25%

Mecanismo de recuperação

  • A recuperação será aplicada apenas aos alunos que tiverem conceito final D ou F e cujas ausências não excederem 25% da quantidade de aulas.
  • Consistirá numa prova, em formato similar às aplicadas ao longo do curso.
  • O conteúdo da prova englobará todos os temas vistos durante o quadrimestre.
  • A nota obtida na prova de recuperação (NR) será usada obter a nota final com recuperação (NFR), que consiste na média:
    NFR = max {MF, (MF + 2 x NR) / 3}
  • O conceito final obtido na recuperação substituirá o conceito original e será
    • C, se NFR ≥ 6.0
    • D, se 5.0 ≤ NFR < 6.0
    • F, se 0.0 ≤ NFR < 5.0

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

  • [[][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!

  • Regra 1: Você não pode enviar para avaliação um trabalho que não seja de sua própria autoria ou que seja derivado/baseado em soluções elaboradas por outros.
  • Regra 2: Você não pode compartilhar a sua solução com outros alunos nem pedir aos seus colegas que compartilhem as soluções deles com você.
  • Regra 3: Nos trabalhos enviados para avaliação você deve indicar eventuais assistências que você tenha recebido.
  • Nós encorajamos fortemente que você procure outras pessoas quando houver a necessidade. Discuta o problema e possíveis ideias para soluções, mas elabore sua própria solução, por conta própria.
  • *Qualquer violação às regras descritas acima 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.*
  • Possível denúncia à Comissão de Transgressões Disciplinares Discentes da Graduação, a qual decidirá sobre a punição adequada à violação que pode resultar em advertência, suspensão ou desligamento, de acordo com os artigos 78-82 do Regimento Geral da UFABC.