Unicamp: logo Instituto de Computação: logo

MO405 / MC878 - Teoria dos Grafos

Instrutor: Joao Meidanis, meidanis at unicamp dot br

Segundas e Quartas, 19:00-21:00. Horário da Pós

Primeiro Semestre, 2024

Visão Geral

Este é um curso introdutório à Teoria dos Grafos. Nossa principal referência será o livro de Douglas West, Introduction to Graph Theory, listado na seção de referências, onde podem ser encontradas também outras obras relevantes sobre o assunto.

Teremos aulas presenciais neste semestre. As aulas tipicamente terão uma parte inicial, cobrindo os tópicos do dia, seguida de discussões, perguntas e sugestões, e algumas vezes exercícios de várias fontes.

Pretendemos cobrir a maior parte da referência principal neste semestre. Estimamos que os alunos precisem de cerca de 12 horas por semana para acompanhar a disicplina, entre leituras, aulas, e tarefas de casa.

Atendimento

Favor marcar um horário por email.

Cronograma

Segue o cronograma planejado para o semestre. Em cada aula, temos o tópico do dia e alguns exercícios sugeridos para fixação. Pode ser que o cronograma sofra ligeiras alterações durante o semestre, devidas a circunstâncias imprevisíveis, mas esperamos que o cronograma abaixo seja seguido na maior parte do tempo.


MO405A Graph Theory 2024 1st Semester


TENTATIVE SCHEDULE Last modified: 2024-02-28





Day Date Activity Exercises Observations
Mon Feb 26

Wed Feb 28 Class overview

Mon Mar 4 Ch. 1: What is a graph? 1.1.7, 1.1.19, 1.1.22, 1.1.31
Wed Mar 6 Ch. 1: Paths, cycles, trails 1.2.8, 1.2.17, 1.2.28
Mon Mar 11 Ch. 1: Vertex degrees and counting 1.3.1, 1.3.14, 1.3.36
Wed Mar 13 Ch. 1: Directed graphs t1.4.14 (Nim), t1.4.25 (de Bruijn), t1.4.30 (king)
Mon Mar 18 Ch. 2: Trees and distances: basic properties t2.1.6-7 (e/e'), t2.1.13 (tree center), t2.1.17 (bridge-it)
Wed Mar 20 Ch. 2: Spanning trees and enumeration t2.2.1-2 (Prüfer), t2.2.12 (matrix tree)
Mon Mar 25 Ch. 2: Optimization, trees t2.3.1-2-3 (Kruskal), t2.3.5-6-7 (Dijkstra), t2.3.8 (BFS)
Wed Mar 27 Ch. 3: Matching and covers 3.1.4, 3.1.8, 3.1.18
Mon Apr 1 Written Test I (up to Ch. 2)

Wed Apr 3 Ch. 3: Algorithms and applications t3.2.9 (uses 3.2.5, 3.2.6, 3.210)
Mon Apr 8 Ch. 3: Matching: general graphs 3.3.1-2-3
Wed Apr 10 Ch. 4: Cuts and connectivity 4.1.8, t4.1.23 (DFS)
Mon Apr 15 Ch. 4: k-connected graphs 4.2.1, 4.2.3, 4.2.17
Wed Apr 17 Ch. 4: Network flow problems 4.3.1, 4.3.2, 4.3.3
Mon Apr 22 Ch. 5: Vertex colorings and upper bounds t5.1.16
Wed Apr 24 Multiple Choice Test I (up to Ch. 4)

Mon Apr 29 Ch. 5: Structure of k-chromatic graphs 5.2.5, 5.2.22
Wed May 1 Holiday

Mon May 6 Ch. 5: Coloring of graphs: enumeration aspects 5.3.1, 5.3.3, 5.3.4, 5.3.5, 5.3.18
Wed May 8 Ch. 6: Embeddings and Euler's formula 6.1.3, 6.1.8, 6.1.10, 6.1.12, 6.1.13, 6.1.29
Mon May 13 Ch. 6: Characterization of planar graphs 6.2.3, 6.2.4, 6.2.5
Wed May 15 Ch. 6: Parameters of planarity 6.3.1, 6.3.4
Mon May 20 Ch. 7: Line graphs and edge coloring t7.1.10, 7.1.1, 7.1.2, 7.1.17
Wed May 22 Exercises

Mon May 27 Ch. 7: Hamilton cycles 7.2.7-8-12
Wed May 29 Ch. 7: Planarity, coloring, cycles 7.3.6-13-18
Mon Jun 3 Written Test II (up to Ch. 6)
Wed Jun 5 Ch. 8: Perfect graphs 8.1.2, 8.1.30, 8.1.38, t8.1.12
Mon Jun 10 Ch. 8: Matroids 8.2.2, 8.2.6, 8.2.7
Wed Jun 12 Ch. 8: Ramsey theory 8.3.6, 8.3.9, 8.3.39, 8.3.40
Mon Jun 17 Ch. 8: More extremal problems 8.4.15, 8.4.20
Wed Jun 19 Ch. 8: Random graphs 8.5.1, 8.5.6, 8.5.9., 8.5.19, 8.5.21
Mon Jun 24 Ch. 8: Eigenvalues of graphs 8.6.3, 8.6.7
Wed Jun 26 Multiple Choice Test II (up to Ch. 8)

Mon Jul 1 Study week


Wed Jul 3 Study week


Mon Jul 8 Holiday


Wed Jul 10 Exam (undergraduates only)


Avaliação

As notas dos alunos serão baseadas em resultados de provas e de contribuições ao blog oficial. Todas as tarefas são individuais.

As provas escritas são provas tipicamente de 4 questões, para serem respondidas em classe nas datas agendadas no cronograma. Cada prova durará 1:40 horas, e terá um resultado numérico de 0 a 10.

As provas de múltipla escolha são provas tipicamente de 10 questões, para serem respondidas através da escolha de uma de 5 alternativas, seguida de uma breve justificativa. As questões para estas provas virão necessariamente do blog oficial de questões. Aqui também cada prova durará 1:40 horas, e terá um resultado numérico de 0 a 10.

O blog oficial de questões é um blog mantido pelo instrutor, e contém questões elaboradas pelos estudantes desta disciplina ao longo dos anos, incluindo os estudantes deste oferecimento. As questões são verificadas pelo instrutor antes de serem colocadas no blog. Em toda semana em que houver matéria nova, os alunos terão que submeter uma questão de múltipla escolha, até as 23:59 da quinta-feira da semana seguinte (exceto na última semana de aula), que será verificada pelo instrutor e, se for apropriada, será incluída no blog. Alunos que tiverem suas questões aceitas para o blog ganharão 0.1 ponto na nota final por questão aprovada. Alunos que não tiverem submetido sua questão em tempo perderão 0.1 na nota final. As questões submetidas poderão ser revisadas pelo instrutor para aperfeiçoamento, mas o nome do autor original permanecerá na questão. Os alunos devem usar o formato padrão das questões, que consiste em um enunciado, seguido de 5 alternativas (sendo a última necessariamente NDA - nenhuma das anteriores), seguidas da frase "Ideia original de:", seguida de seu nome.

A nota final será simplesmente a média das quatro provas, com acréscimos e substrações relativas às questões para o blog.

As notas numéricas serão convertidas para conceitos de acordo com a seguinte tabela:

8.5 a 10  A
7 a 8.5B
5 a 7C
0 a 5D

Atrasos

Não serão admitidos atrasos na entrega de questões de múltipla escolha nem nos dias de prova.

Fraude

Qualquer tentativa de fraude nesta disciplina será punida com nota final zero para todos os envolvidos, com possíveis sansões adicionais da Universidade.

Referências

Introduction to Graph Theory, D. West, 2nd ed.    Introduction to Graph Theory,
Douglas B. West,
2nd edition, Prentice-Hall, Inc., 2001.
ISBN 978-0-131-43737-1.
Introduction to Graph Theory, D. West, 2nd ed.    Graph Theory,
Adrian Bondy, U. S. R. Murty,
3rd corrected printing, Springer, 2008.
ISBN 978-1-84628-969-9.
Introduction to Graph Theory, D. West, 2nd ed.    Graph Theory,
Reinhard Diestel,
4th edition, Springer, 2010.
ISBN 978-3-642-14278-9.