DC-UFRPE/Bacharelado em Ciência da Computação/Algoritmos em grafos

Programa da Disciplina

Nome:	Algoritmos em grafos
Código:	14093
Departamento:	Departamento de Computação (DC)
Área:	Fundamentos da Computação
Carga-horária total:	60 horas
Créditos:	4
Pré-requisitos:	14103 - Algoritmos e Estruturas de Dados

Ementa

Definição formal. Grafos não-direcionados e direcionados e subtipos. Relações entre grafos. Caminhos e Ciclos. Conectividade. Problemas de grafos como modelos de tarefas reais. Representação computacional. Buscas em largura e em profundidade. Ordenação topológica. Coloração e planaridade e aplicações. Menores caminhos. Árvores espalhadas mínimas. Caminhos e ciclos Hamiltonianos e Eulerianos. Problema do Carteiro Chinês. Problema do Caixeiro-Viajante: algoritmos aproximados e heurísticas. Fluxo máximo em redes. Emparelhamento máximo. Problemas computacionalmente complexos em grafos. Aplicações.

Conteúdo Programático

1. Visão geral
2. Conceitos
3. Representação Computacional
4. Algoritmos básicos
5. Menores caminhos
6. Árvores Espalhadas Mínimas
7. Caminhos e Ciclos Eulerianos
8. Caminhos e Ciclos Hamiltonianos
9. Fluxo máximo em redes
10. Emparelhamento
11. Coloração e planaridade
12. Problemas difíceis em grafos

Bibliografia

Básica

1. JUNGNICKEL, Dieter. Graphs, networks and algorithms. 4. ed. New York: Springer, 2013. xv (Algorithms and computation in mathematics v.5). ISBN 9783642322778 (enc.).
2. CORMEN, Thomas H. et al. Introduction to algorithms. 3rd ed. Cambridge, Mass.: MIT Press, 2009. 1292 p. ISBN 9780262533058 (broch.)
3. BOAVENTURA NETTO, Paulo Oswaldo. Grafos: teoria, modelos, algoritmos. 4. ed. rev. ampl. São Paulo, SP: Edgard Blücher, 2006. xiv, 313 p. ISBN 8521203918 (broch.)

Complementar

1. MARCUS, Daniel A. Graph Theory: A Problem Oriented Approach. Washington : Mathematical Association of America, 2008. 222 p.
2. SCHEINERMAN, Edward R. Matemática discreta: uma introdução. São Paulo, SP: Cengage Learning, 2011. xviii, 532 p. ISBN 9788522107964 (broch.).
3. VOLOSHIN, Vitaly I. Introduction to Graph Theory. New York : Nova Science Publishers, Inc., 2009. 160 p.
4. BARRAT, Alain; BARTHÉLEMY, Marc; VESPIGNANI, Alessandro. Dynamical processes on complex networks. Cambridge; New York: Cambridge University Press, 2013. 347 p. ISBN 9781107626256 (broch.).
5. VASUDEV, C. Graph Theory with Applications. Daryaganj, Índia : New Age International, 2006. 487 p.