Detalhes
GRAFOS E ALGORITMOS
Nome da Disciplina: GRAFOS E ALGORITMOS
Carga Horária: 60
Créditos: 4
Disciplina Regular: Sim
EMENTA
Conceitos básicos: Grafos; Figuras de grafos grandes; Estruturas de dados para grafos; Grafos aleatórios; Caminhos e ciclos em grafos; Grafos topológicos. Busca em profundidade: Acessibilidade; Busca em profundidade (DFS); Florestas DFS; DFS e pós-ordem; Ciclos. Busca em largura e distâncias; Busca em largura (BFS); Caminhos de comprimento mínimo; Algoritmo de caminhos mínimos. Florestas, árvores, conexão; Componentes conexas; Circuitos e florestas; Grafos aresta-biconexos; Componentes aresta-biconexas. Conexão forte: Grafos fortemente conexos; Componentes fortes; Algoritmo de Tarjan. Coloração; Coloração de vértices; Grafos bipartidos e circuitos ímpares. Emparelhamentos: Emparelhamentos em grafos bipartidos. Grafos com custos: Custos nos arcos e arestas. Árvores geradoras baratas: Árvores geradoras; Árvores geradoras de custo mínimo (MST); Algoritmo de Prim; Algoritmo de Kruskal. Caminhos baratos: Caminhos de custo mínimo; Algoritmo de Bellman-Ford; caminhos baratos em dags; Algoritmo de Dijkstra. Caminhos caros: Caminhos simples de custo máximo. Fluxo em redes: O problema do fluxo máximo; Algoritmo de Ford-Fulkerson; Fluxo máximo e corte mínimo; Implementação do algoritmo de Ford-Fulkerson; Caminhos aumentadores mínimos; Caminhos aumentadores de máxima capacidade.
BIBLIOGRAFIA
Robert Sedgewick, Algorithms in C (part 5: Graph Algorithms), 3rd. edition, Addison-Wesley/Longman, 2002.
R. Sedgewick e K. Wayne, Algorithms, 4th Edition, Addison-Wesley, 2011.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition, MIT Press & McGraw-Hill, 2001.
David Joyner, Minh Van Nguyen, Nathann Cohen, Algorithmic Graph Theory.
Donald E. Knuth, The Stanford GraphBase, ACM Press e Addison-Wesley, 1993
John A. Bondy, U.S. Rama Murty, Graph Theory, Springer, 2008.
John A. Bondy, U.S. Rama Murty, Graph Theory with Applications, Macmillan, 1976.
A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
James A. McHugh, Algorithmic Graph Theory, Prentice Hall, 1990.
G. Chartrand, O.R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, 1993.
M. van Steen, Graph Theory and Complex Networks: An Introduction, Maarten van Steen, 2010.
R. Sedgewick e K. Wayne, Algorithms, 4th Edition, Addison-Wesley, 2011.
T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein, Introduction to Algorithms, 3rd edition, MIT Press & McGraw-Hill, 2001.
David Joyner, Minh Van Nguyen, Nathann Cohen, Algorithmic Graph Theory.
Donald E. Knuth, The Stanford GraphBase, ACM Press e Addison-Wesley, 1993
John A. Bondy, U.S. Rama Murty, Graph Theory, Springer, 2008.
John A. Bondy, U.S. Rama Murty, Graph Theory with Applications, Macmillan, 1976.
A.V. Aho, J.E. Hopcroft, J.D. Ullman, The Design and Analysis of Computer Algorithms, Addison-Wesley, 1974.
James A. McHugh, Algorithmic Graph Theory, Prentice Hall, 1990.
G. Chartrand, O.R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, 1993.
M. van Steen, Graph Theory and Complex Networks: An Introduction, Maarten van Steen, 2010.
VOLTAR
