Carregando...

DISCIPLINA Listagem de Ementa/Programa

TEORIA E APLICAÇÃO DE GRAFOSDISCIPLINA 117901

VER OFERTA

ÓrgãoCIC Departamento de Ciência da Computação
Código117901
DenominaçãoTeoria e Aplicação de Grafos
NívelGraduação
Início da Vigência em1962/1
Pré-requisitos CIC 116319 ESTRUTURAS DE DADOS
EmentaInício da Vigência em 1971/2

Introdução à teoria dos grafos: motivação, exemplos de aplicações, conceitos básicos (grafos e subgrafos, grau de vértices, caminhos e ciclos, grafos regulares e bipartidos, grafos eulerianos e hamiltonianos, grafos direcionados, grafos ponderados, conectividade e planaridade). Representação de grafos: tipos de representações (matrizes de adjacências, listas de adjacências e hash). Operações: união, interseção, diferença, complemento, produto, composição. Implementação de algoritmos em grafos: exploração e ordenação (algoritmos de busca em profundidade, busca em amplitude e ordenação topológica), conectividade (algoritmo de Tarjan), árvore geradora mínima (algoritmos de Kruskal e Prim), menores caminhos a partir de uma fonte (algoritmos de Dijkstra e Bellman-Ford), coloração. Aplicação dos algoritmos em problemas de Ciência da Computação. Aplicações em Problemas Ambientais.

BibliografiaInício da Vigência em 1971/2

Bibliografia Básica:
Douglas B. West. Introduction to Graph Theory. Prentice Hall, 2001. Second edition, ISBN 0-13-014400-2.
Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms. Massachusetts Institute of Technology. 2009. ISBN 978-0-262-03384-8.
John Harris e Jeffry L. Hirst. Combinatorics and Graph Theory (Undergraduate Texts in Mat-hematics), Springer, 2008.
Bibliografia Complementar:
Tarjan, R., Data Structures and Network Algorithms, SIAM Pub., 1987.
Sedgewick, R., Algorithms in C (Part5 - Graphs), Addison-Wesley, 1997.
Skiena, S., The Algorithm Design Manual, Springer-Verlag, 1997.
Bondy, J. A. and Murty, U. S. R., Graph Theory, Springer, 2008.
Szwarcfiter, J. L., Grafos e Algoritmos Computacionais, Editora Campus Ltda., Rio de Janei-ro, 2ª ed., 1986.