DC-UFRPE/Bacharelado em Ciência da Computação/Algoritmos em grafos
Programa da Disciplina editar
| 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 editar
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 editar
- Visão geral
- Conceitos
- Representação Computacional
- Algoritmos básicos
- Menores caminhos
- Árvores Espalhadas Mínimas
- Caminhos e Ciclos Eulerianos
- Caminhos e Ciclos Hamiltonianos
- Fluxo máximo em redes
- Emparelhamento
- Coloração e planaridade
- Problemas difíceis em grafos
Bibliografia editar
Básica editar
- JUNGNICKEL, Dieter. Graphs, networks and algorithms. 4. ed. New York: Springer, 2013. xv (Algorithms and computation in mathematics v.5). ISBN 9783642322778 (enc.).
- CORMEN, Thomas H. et al. Introduction to algorithms. 3rd ed. Cambridge, Mass.: MIT Press, 2009. 1292 p. ISBN 9780262533058 (broch.)
- 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 editar
- MARCUS, Daniel A. Graph Theory: A Problem Oriented Approach. Washington : Mathematical Association of America, 2008. 222 p.
- SCHEINERMAN, Edward R. Matemática discreta: uma introdução. São Paulo, SP: Cengage Learning, 2011. xviii, 532 p. ISBN 9788522107964 (broch.).
- VOLOSHIN, Vitaly I. Introduction to Graph Theory. New York : Nova Science Publishers, Inc., 2009. 160 p.
- BARRAT, Alain; BARTHÉLEMY, Marc; VESPIGNANI, Alessandro. Dynamical processes on complex networks. Cambridge; New York: Cambridge University Press, 2013. 347 p. ISBN 9781107626256 (broch.).
- VASUDEV, C. Graph Theory with Applications. Daryaganj, Índia : New Age International, 2006. 487 p.