E N G E N H A R I A  A E R O E S P A C I A L
O Curso

Matriz Curricular

Projetos de Pesquisa

Docentes

Eventos & Links


Universidade Federal do ABC

Centro de Engenharia,
Modelagem e Ciências Sociais Aplicadas


BC1429
Teoria dos Grafos

T P I = 3 1 4

Ementa

Introdu��o: No��es b�sicas; grafos orientados, n�o-orientados, bipartidos; grafos conexos e n�o conexos; Subgrafos e hipergrafos; Estruturas de dados para a representa��o de grafos. Caminhos e circuitos em grafos: Circuitos Eulerianos e Hamiltonianos; Caminhos de comprimento m�nimo. Percursos em grafos: Em profundidade; Em largura. �rvores: Conceitos b�sicos; �rvores geradoras de grafos; �rvores geradoras m�nimas. Exemplos de problemas: Colora��o de v�rtices; Clique m�ximo; Conjunto independente de v�rtices; Caixeiro viajante; Problema do fluxo m�ximo em redes.

Bibliografia B�sica

CORMEN, T.H., LEISERSON, C.E., RIVEST, R.L. and STEIN, C., Algoritmos - Teoria e Pr�tica. Campus, 2002. BONDY, J.A. and MURTY, U.S.R. Graph Theory with Applications Macmillan, London, 1976.

Bibliografia Complementar

TAO, T.; VU, V. Additive CombinatoricsChris ; Royle, Gordon. Algebraic Graph TheoryR. Sedgewick. Algorithms in C (part 5: Graph Algorithms)CHARTRAND, G.; ZHANG, P. Chromatic Graph TheoryLOVASZ, L. Combinatorial Problems and ExercisesHARRIS, J. M. e outros. Combinatorics and Graph TheoryCAMERON, J. Combinatorics: Topics, Techniques, AlgorithmsCHUNG, L. L. F. Complex Graphs and Networks

Tipo

Livre