Algoritmos em Grafos

Programa da Disciplina

Nome: Algoritmos em Grafos	Código: 14093
Departamento: Departamento de Computação	Área: Ciência da Computação
Carga-horária total: 60 horas	Créditos: 4
Carga-horária semanal: 4 horas (teóricas: 4; práticas: 0; EAD*: 0)

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.

Prática como componente curricular (30h):

Não possui.

Objetivos:

Entender os grafos enquanto objeto matemático, e conhecer os conceitos e teoremas mais relevantes, do ponto de vista de aplicações. Entender como os grafos podem modelar diversas situações relevantes para aplicações. Entender os problemas computacionais em grafos como modelos de tarefas do mundo real. Conhecer os principais problemas de grafos, com seus algoritmos e suas aplicações em diversas áreas.

Turmas

Bibliografia básica:[editar | editar código-fonte]

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.)

Bibliografia complementar:[editar | editar código-fonte]

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, India: New Age International, 2006. 487p