Horário: 2ª 10-12hs e 5ª 08-10hs sala 301-3
Horário: 2ª 21-23hs e 5ª 19-21hs sala 301-3
TPI: 3-1-4
Carga Horária: 48 horas
Monitor: AOC
Ementa:
Introdução. Caminhos e circuitos em grafos. Percursos em
grafos. Árvores. Exemplos de problemas e algoritmos em grafos.
Avaliação:
A availação consiste de três
provas. Participação e entrega de exercícios serão considerados
no conceito final. Todo aluno que entregar exercícios pode,
eventualmente, ser questionado sobre a resolução. O aluno que
faltar em dia de provar deve entrar em contato por email o
quanto antes para agendar a 2a chamada.
A avaliação final de cada aluno não será o resultado de
alguma média feita a partir das avaliações. O resultado de
cada avaliação reflete o desempenho do aluno
em todo o curso até aquele instante. Isso significa que
a cada cada conceito atribuído durante o curso leva em conta o
resultado das avaliações até o momento.
O conceito final da disciplina poderá ser:
- F - Reprovado. O aluno deve cursar novamente a disciplina.
- C - Desempenho mínimo satisfatório, demonstrando
capacidade de uso adequado dos conceitos da disciplina, habilidade
para enfrentar problemas relativamente simples e prosseguir em
estudos avançados.
- B - Bom desempenho, demonstrando boa capacidade de uso dos
conceitos da disciplina.
- A - Desempenho excepcional, demonstrando excelente
compreensão da disciplina e do uso da matéria.
Bibliografia
Básica:
- Notas de aula pdf html
- BONDY, J. A.; MURTY, U. S. R. Graph theory. Graduate
Texts in Mathematics, 244. Springer, New York,
2008.[511.5 / BONg][pdf]
- DIESTEL, R. Graph Theory, Springer,
2005. [511.5 / DIESgr3 / 3 ed.] [versão
eletrônica]
- MANBER, Udi. Introduction to algorithms: a creative
approach. Addison-Wesley.(Capítulo 7)
[005.73 / MANi]
Complementar:
- BOLLOBÁS, B. Modern graph theory. New York:
Springer. [511.5 / BOLm]
- CHARTRAND, Gary; LESNIAK, Linda. Graphs &
digraphs. 4th ed. Boca Raton: CRC Press. [511.5 /
CHAg4]
- CHARTRAND, Gary. Introductory graph theory. New
York: Dover. [511.5 / CHAi]
- FEOFILOFF, P., KOHAYAKAWA, Y., WAKABAYASHI, Y. Teoria
dos Grafos: uma introdução sucinta.
[página
web]
- FEOFILOFF, P. Algoritmos para Grafos em C via
Sedgewick.
[página
web]
-
CORMEN, Thomas H et al. Algoritmos: Teoria e prática//
Introduction to algorithms. (capítulos sobre algoritmos em grafos)
Exercícios
Os números dos exercícios abaixo referem-se às notas de aula, versão em pdf.
- § 1: 1 até 19, 20 a 22, 25, 26, 29, 31,41;
45,46,49,51,52;56-58,66,67.
- § 2: 69(b),71, 72, 75, 76, 78, 79, 81, 83, 84, 86, 90, 91, 93,94,99
-
§ 3: 103,104,120
-
§ 4: 139--146, 151--159
-
§ 5: 160--165;167,168,170,172,177-182
Links
Programa
14/01 - Apresentação da disciplina; definições iniciais.
exerc 1 -- 19
17/01 - Exercícios 1 e 9; subgrafo; clique e conjunto independente
exerc 20 -- 22, 25, 26
21/01 - exercício 25; isomorfismo; representação computacional;
exerc 45, 46, 49, 51, 52, 56 -- 58, 66, 67
24/01 - exercício 67; grafo bipartido; corte
exerc 29, 31, 41
28/01 - exercicios 32, 33; percusos em grafos
exerc 69(b)
31/01 - busca em largura e busca em profundidade; caminhos e distância;
exerc 71, 72, 75, 76, 78, 79
04/02 - Circuitos
exerc 81, 83, 84, 86
07/02
-
PROVA Matunino Noturno
11/02 -
Carnaval
14/02 - Resolução da prova. Grafos com pesos nas arestas.
exerc 90,91
18/02 - Algoritmo de Dijkstra;
exerc 93,94,99
21/02 - grafos conexos, componentes; grafos biconexos, componentes;
algoritmo para determinar articulação.
exerc 103,104,120
25/02 - árvores;
exerc 139--146
28/02 - árvores geradoras de custo mínimo; algs. Prim e
Kruskal exerc 151--159
04/03 - aula de exercícios
07/03 -
PROVA Matut Notur
11/07 - Resolução da prova;
14/03 - emparelhamento;
exerc. 160--165;
18/03 - emparelhamento em grafos bipartidos; teoremas de Konig e
Hall, algoritmo de Edmonds; exerc:167,168,170,172,177-182
21/03 - exercício 165; coloração de arestas (
pdf)
exerc.: todos do pdf
25/03 - Coloração de vértices.(
pdf)
exerc.: todos do pdf
último dia pra entrega de exercícios que serão considerados no nota o prazo é o fim da aula.
28/03 -
PROVA NOTURNO pdf
01/04 -
PROVA DIURNO pdf
04/04 - Vista de provas