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