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/2024 Desativação:

Objetivos
Estudar algoritmos para problemas fundamentais em grafos.
 
Study algorithms for fundamental problems in graphs.
 
 
Docente(s) Responsável(eis)
47490 - Arnaldo Mandel
91288 - Carlos Eduardo Ferreira
55029 - Cristina Gomes Fernandes
3463382 - Marcel Kenji de Carli Silva
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.
 
Graph and digraph connectivity. Maximum matchings. Maximum flow. Vertex coloring. Hamiltonian cycles. Optional topics.
 
 
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.
 
Graph connectivity: components, biconnected graphs. Strongly connected digraphs (Kosaraju-Sharir algorithm, Tarjan algorithm). Maximum matching in bipartite graphs. Matching in arbitrary graphs (Edmonds algorithm). Maximum flow (Ford-Fulkerson algorithm). Vertex coloring. Hamiltonian cycles. Optional topics: link analysis, network analysis, random networks.
 
 
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.
 

Clique para consultar os requisitos para MAC0328

Clique para consultar o oferecimento para MAC0328

Créditos | Fale conosco
© 1999 - 2024 - Superintendência de Tecnologia da Informação/USP