Jupiterweb

Disciplina

Informações da Disciplina

Preparar para impressão

Júpiter - Sistema de Graduação

Instituto de Matemática e Estatística

Ciência da Computação

Disciplina: MAC0328 - Algoritmos em Grafos

Créditos Aula:	4
Créditos Trabalho:	0
Tipo:	Semestral

Objetivos

Estudar algoritmos para problemas fundamentais em grafos.

Docente(s) Responsável(eis)

	Arnaldo Mandel
	Carlos Eduardo Ferreira
	Cristina Gomes Fernandes
	Marcel Kenji de Carli Silva
	Paulo Feofiloff
	Yoshiharu Kohayakawa

Programa Resumido

Conexão de grafos e digrafos. Emparelhamentos máximos. Fluxo máximo. Coloração de vértices. Circuitos hamiltonianos. Tópicos opcionais.

Programa

Conexão de grafos: componentes, grafos biconexos. Digrafos fortemente conexos (algoritmo de Kosaraju-Sharir, algoritmo de Tarjan) Emparelhamentos máximos em grafos bipartidos. Emparelhamentos em grafos arbitrários (algoritmo de Edmonds). Fluxo máximo (algoritmo de Ford-Fulkerson). Coloração de vértices. Circuitos hamiltonianos. Tópicos opcionais: link analysis, network analysis, redes aleatórias.

Avaliação

	Método
	Listas de exercícios e provas.

	Critério
	Média ponderada de provas e exercícios.

	Norma de Recuperação
	: Em caso de média geral maior ou igual a 3 e menor que 5, a nova média geral consiste de uma média ponderada entre a média geral e uma prova e/ou projeto de recuperação.

Bibliografia

Bibliografia Básica: 1. J.A. Bondy, U.S. Rama Murty, Graph Theory, Springer, 2007. 2. T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., McGraw-Hill, 2009. 3. D. Easley, J. Kleinberg, Networks, Crowds, and Markes: Reasoning About a Highly Connected World, Cambridge University Press, 2010 4. D.E. Knuth, The Stanford GraphBase, Addison-Wesley, 1993. 5. D. Joyner, M. Van Nguyen, N. Cohen, Algorithmic Graph Theory, http://code.google.com/p/graph-theory-algorithms-book/, Google Code, 2010. 6. R. Sedgewick, Algorithms in C (part 5: Graph Algorithms), 3rd ed., Addison-Wesley/Longman, 1998. 7. R. Sedgewick, K. Wayne, Algorithms, 4th. ed., Addison-Wesley, 2011. 8. M. van Steen, Graph Theory and Complex Networks: An Introduction, Maarten van Steen, 2010.

Requisitos

Os Requisitos variam conforme o curso para o qual ela é oferecida.

Clique para consultar o oferecimento para MAC0328.