MCTA027-17 - Teoria dos Grafos (2018 Q3)
Professora: Carla Negri Lintzmayer, Sala 508-2
Avisos importantes (fique atento sempre!)
[18/12] Notas finais após a recuperação.― novos ―
[14/12] Horário de atendimento extra: segunda, dia 17/12, das 10h às 12h. [13/12] Houve um erro no comunicado anterior: o horário da prova de recuperação é das 10h às 12h, no dia 18/12. Entrem em contato caso haja algum problema.
[10/12] Informativos importantes:
- Notas finais.
- Formulário opcional e anônimo sobre a disciplina.
- Dúvidas sobre as correções de qualquer atividade podem ser respondidas em qualquer horário de atendimento ou, em último caso, por e-mail.
- Horário extra de atendimento: sexta-feira, dia 14/12, das 10h às 12h.
- Prova de recuperação: terça-feira, dia 18/12, das 8h às 10h, na sala de aula usual.
- A prova de recuperação pode ser feita por aqueles que ficaram com conceito final D ou F e não ultrapassaram o limite de faltas.
[21/11] Liberada Lista 4 de exercícios.
[05/11] O atendimento de terça-feira, dia 6/11, está excepcionalmente cancelado. Ele será transferido para outra data, que será posteriormente informada.
[05/11] Liberada Lista 3 de exercícios.
[03/11] Notas da prova 1 e da lista 1. Dúvidas específicas sobre a correção da sua prova podem ser retiradas nos meus horários de atendimento (não haverá vista de prova na sala de aula).
[15/10] Data de entrega da lista 2 adiada. Você pode, se quiser, substituir os exercícios 7, 8 e 9 por outros 3 da seção de extras.
[09/10] Liberada Lista 2 de exercícios.
[24/09] Liberada Lista 1 de exercícios.
[12/09] Criada página do tidia.
[12/09] Página da disciplina no ar.
Conteúdo dessa página
 |
Dias, horários e local das aulas (voltar ao topo)
Segundas-feiras, das 10h às 12h, sala S-301-3.Quartas-feiras, das 8h às 10h, sala S-301-3.
Dias, horários e local de atendimento (voltar ao topo)
Terças e Quintas, das 13h às 15h, com a professora, na sala 508-2 do bloco A.Quintas, das 17h às 18h30h, com os monitores Gabriel Fernandes e Richard Raphael, na sala S-308-3 do bloco A.
Além disso, você pode marcar um horário por e-mail, caso não puder (excepcionalmente) comparecer a nenhum dos horários acima.
| Hora | Seg | Ter | Qua | Qui | Sex |
|---|---|---|---|---|---|
| 8h | Aula | ||||
| 9h | Aula | ||||
| 10h | Aula | ||||
| 11h | Aula | ||||
| 12h | |||||
| 13h | Atendimento Carla | Atendimento Carla | |||
| 14h | Atendimento Carla | Atendimento Carla | |||
| 15h | |||||
| 16h | |||||
| 17h | Atendimento Monitores | ||||
| 18h | Atendimento Monitores |
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.Recomendação (voltar ao topo)
Disciplinas: Matemática Discreta; Processamento da Informação; Algoritmos e Estruturas de Dados IPara facilitar o acompanhamento do curso, é recomendado que você possua:
- conhecimentos de programação (em qualquer linguagem imperativa), 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, somatórios e manipulação de funções).
- O que é uma prova matemática, do prof. Paulo Feofiloff, da USP.
- Matemática discreta para computação, dos profs. Anamaria Gomide e Jorge Stolfi, da Unicamp.
- Indução matemática, do prof. Cid Carvalho de Souza, da Unicamp.
- Portal da Matemática da OBMEP.
- Indução e contagem, do prof. Rogério Steffenon e de Felipe Guarnieri, da Unisinos.
Bibliografia e outros materiais (voltar ao topo)
- Diestel, R. Graph Theory, 5th edition, Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume 173. 2016.
- West, D. B. Introduction to Graph Theory, 2nd edition, Pearson Education. New Jersey. 2001.
- Bondy, J. A.; Murty, U. S. R. Graph theory. Graduate Texts in Mathematics, 244. Springer. New York. 2008.
- Bondy, J. A.; Murty, U. S. R. Graph theory with applications. Elsevier. 1976.
- Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 3rd ed. MIT Press. 2009.
- Notas de aulas de grafos dos Profs. Paulo Feofiloff, Yoshiharu Kohayakawa e Yoshiko Wakabayashi do IME/USP.
Cronograma e notas de aula (voltar ao topo)
Neste quadrimestre o conteúdo da disciplina está unificado com a turma do Prof. Guilherme Mota.Assim, os tópicos que estão sendo dados, listados abaixo, podem ser vistos detalhados em suas notas de aula.
| Aula | Data | Conteúdo |
|---|---|---|
| 1 | 17/9 | Introdução ao curso / Grafos (slides) |
| 2 | 19/9 | Conceitos básicos e representações (grafo, adjacência, grau, grafo simples, grafo completo, regular, bipartido, conjunto independente, clique). |
| 3 | 24/9 | Subgrafos, passeios, trilhas, caminhos, ciclos. Caracterização de grafos bipartidos. Teorema de Mantel. (Lista 1) |
| 4 | 26/9 | Prova do teorema de Mantel. Cintura e diâmetro. Componentes, arestas e vértices de corte. |
| 5 | 1/10 | Grafos Eulerianos e caracterizações. Decomposição em ciclos. |
| 6 | 3/10 | Grafos Eulerianos e algoritmo de Fleury |
| 7 | 8/10 | Busca em largura (com corretude) (Lista 2) |
| 8 | 10/10 | Dijkstra (com corretude) |
| 9 | 15/10 | Árvores |
| 10 | 17/10 | Caracterizações de árvores e árvores geradoras |
| 11 | 22/10 | Digrafos |
| 12 | 24/10 | Revisão / Resolução de exercícios |
| 13 | 29/10 | Prova 1 |
| 14 | 31/10 | Emparelhamentos e Teorema de Berge |
| 15 | 5/11 | Teorema de Hall e corolários. Cobertura por vértices e Teorema de Konig. (Lista 3) |
| 16 | 7/11 | Conexidade (vértices e arestas) |
| 17 | 12/11 | Grafos Hamiltonianos. Teorema de Dirac e Teorema de Rédei. |
| 18 | 14/11 | Coloração de vértices. Limitantes e grafos intervalos. |
| -- | 19/11 | Feriado |
| 19 | 21/11 | Coloração de arestas. Limitantes. Teorema de Konig e Teorema de Vizing (Lista 4) |
| 20 | 26/11 | Conjuntos independentes e cliques |
| 21 | 28/11 | Planaridade |
| 22 | 3/12 | Revisão / Resolução de exercícios |
| 23 | 5/12 | Prova 2 |
| 24 | 18/12 | Prova de recuperação |
Plágio (voltar ao topo)
- Entre outros, o código de ética da UFABC estabelece em seu artigo 25
que é eticamente inaceitável que os discentes:
- fraudem avaliações
- fabriquem ou falsifiquem dados
- plagiem ou não creditem devidamente autoria
- aceitem autoria de material acadêmico sem participação na produção
- 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.
- ATENÇÃO: todos os trabalhos enviados para avaliação poderão ser verificados por um sistema automatizado de detecção de plágio.
- 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.
Listas de exercícios (voltar ao topo)
- Ao todo teremos 4 listas, cujos enunciados serão disponibilizados aqui e no tidia, nas datas indicadas acima.
- As listas deverão ser feitas individualmente e devem ser escritas à mão (não serão aceitas soluções em LaTeX, por exemplo).
- Você deve escanear suas soluções e um único PDF deve ser entregue no tidia, dentro do prazo divulgado junto com os enunciados.
- Dica de aplicativo para escanear suas soluções: CamScanner (Google Play).
- Soluções entregues fora do prazo, em no máximo 24h após o prazo dado, valerão 50% da nota.
- ATENÇÃO: Não haverá listas de exercícios substitutivas.
Critérios de avaliação regular (voltar ao topo)
- A avaliação da disciplina constituirá em duas provas e nas 4 listas de exercícios.
- A prova 1 vale 35% da nota.
- A prova 2 vale 45% da nota.
- As listas valem 20% da nota. A nota das listas será calculada por média simples das notas das 4 listas.
- Sejam P1, P2 e L as notas (entre 0 e 10) da prova 1, da prova 2 e das listas, respectivamente.
- Sua média final (MF) antes da recuperação, portanto, será
MF = 0.35 x P1 + 0.45 x P2 + 0.2 x L - 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 0.0 ≤ MF < 5.0
O, se ausência total exceder 25%
Mecanismo de recuperação (voltar ao topo)
- 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 a seguir:
NFR = max {MF, (MF + NR) / 2}
- O conceito final obtido na recuperação substituirá o conceito anterior
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 (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° 227. 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