Público
Relação de Convocados
Relação de Matriculados
____________________
Calendário Escolar
2022
2021
Cursos de ingresso
Disciplina
Busca por Disciplinas
Busca por Turmas
Editais
Programa Unificado de Bolsas(PUB)
Edital 2021-2022
Edital 2022-2023
PEEG
PAP
FAQ
Matrícula Interativa
FAQ
Informações gerais
TUTORIAL - NOVA MATRÍCULA
Jupiterweb em Vídeos
Informações gerais sobre a Graduação
Acesso Restrito
Entrar
Esqueci a Senha
Primeiro Acesso
Informações da Disciplina
Preparar para impressão
Júpiter - Sistema de Gestão Acadêmica da Pró-Reitoria de Graduação
Instituto de Matemática e Estatística
Ciência da Computação
Disciplina: MAC0328 - Algoritmos em Grafos
Graph Algorithms
Créditos Aula:
4
Créditos Trabalho:
0
Carga Horária Total:
60 h
Tipo:
Semestral
Ativação:
01/01/2015
Desativação:
Objetivos
Estudar algoritmos para problemas fundamentais em grafos.
Docente(s) Responsável(eis)
47490 - Arnaldo Mandel
91288 - Carlos Eduardo Ferreira
55029 - Cristina Gomes Fernandes
26472 - Paulo Feofiloff
88134 - 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
Critério
Média ponderada de provas e exercícios.
Norma de Recuperação
Bibliografia
J.A. Bondy, U.S. Rama Murty, Graph Theory, Springer, 2007.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., McGraw-Hill, 2009.
D. Easley, J. Kleinberg, Networks, Crowds, and Markes: Reasoning About a Highly Connected World, Cambridge University Press, 2010
D.E. Knuth, The Stanford GraphBase, Addison-Wesley, 1993.
D. Joyner, M. Van Nguyen, N. Cohen, Algorithmic Graph Theory, http://code.google.com/p/graph-theory-algorithms-book/, Google Code, 2010.
R. Sedgewick, Algorithms in C (part 5: Graph Algorithms), 3rd ed., Addison-Wesley/Longman, 1998.
R. Sedgewick, K. Wayne, Algorithms, 4th. ed., Addison-Wesley, 2011.
M. van Steen, Graph Theory and Complex Networks: An Introduction, Maarten van Steen, 2010.
Clique para consultar os requisitos para MAC0328
Clique para consultar o oferecimento para MAC0328
Créditos
|
Fale conosco
© 1999 - 2022 - Superintendência de Tecnologia da Informação/USP