MO405 / MC878 - Teoria dos Grafos

Tira/Põe Menu

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.

Tira/Põe Menu

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)

Tira/Põe Menu

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.5	B
5 a 7	C
0 a 5	D

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.

Tira/Põe Menu

Referências

Introduction to Graph Theory, Douglas B. West, 2nd edition, Prentice-Hall, Inc., 2001. ISBN 978-0-131-43737-1.

Graph Theory, Adrian Bondy, U. S. R. Murty, 3rd corrected printing, Springer, 2008. ISBN 978-1-84628-969-9.

Graph Theory, Reinhard Diestel, 4th edition, Springer, 2010. ISBN 978-3-642-14278-9.