Disciplina: DCC059 - TEORIA DOS GRAFOS
Horas Aula: 4
Departamento: DEPTO DE CIENCIA DA COMPUTACAO /ICE
Plano de Ensino
Voltar
Ementa
1. Iniciação a Teoria dos Grafos
2. Grafos sem circuitos, árvores e arborescências
3. Busca em Grafos
Conteúdo
1 - INTRODUÇÃO A MODELOS EM GRAFOS
- Grafos e Digrafos;
- Famílias comuns de Grafos;
- Modelagem de aplicações usando Grafos;
- Passeios e distâncias;
- Caminhos, ciclos e árvores;
- Grafos rotulados nos vértices e nas arestas;
- Árvores: caracterização e propriedades.
2 - ESTRUTURA E REPRESENTAÇÃO DE GRAFOS
- Grafos isomorfos;
- Subgrafos;
- Operações comuns entre grafos;
- Testes para grafos não-isomorfos;
- Representação de grafos por matriz;
- Representação de grafos por listas de adjacência.
3 - ÁRVORES GERADORAS CAMINHOS MÍNIMOS
- Árvore de crescimento;
- Busca em largura;
- Busca em profundidade;
- Identificando componentes conexas;
- Identificando arestas ponte e nós de articulação;
- Algoritmos Gulosos
- Árvore de cobertura mínima;
Algoritmo de Prim;
Algoritmo de Kruskal;
- Algoritmos de Dijkstra e Floyd para caminho mínimo
- Corte mínimo de arestas;
4 - CONECTIVIDADE E CAMINHAMENTO EM GRAFOS
- k-conectividade de vértice;
- k-conectividade de arestas;
- Relação entre conectividades de vértice e aresta;
- Trilhas e ciclos Eulerianos;
- Caminhos e ciclos Hamiltonianos;
5 - PLANARIDADE EM GRAFOS
- Conceito de desenho planar de um grafo;
- Teorema da curva de Jordan;
- Teorema de Kuratowski;
6 - PROBLEMAS CLÁSSICOS MODELADOS EM GRAFOS
- Problema da clique;
- Problema do subconjunto independente;
- Problema do subconjunto dominante;
- Problema de Cobertura de vértices;
- Problemas de coloração;
- Problema de atribuição;
- Problema da árvore de Steiner;
- Problema do Caixeiro Viajante;
Bibliografia
SZWARCFITER, J. Grafos e Algoritmos Computacionais. Editora Campus, 1983.
BOAVENTURA NETTO, P. O. Grafos: Teoria, Modelos e Algoritmos. Editora Edgard Blucher Ltda, 1996.
CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; STEIN, C. Introduction to Algorithms. 2nd. edition. MIT Press, 2001.
Bibliografia(continuação)
Não informado
Bibliografia complementar
BOAVENTURA NETTO, P. Grafos - Teoria, Modelos e Algoritmos. 4ª ed. 2006.
BOAVENTURA NETTO, P. Grafos - Introdução e Prática. Blucher, 2009.
CORMEN, T.; LEISERSON, C.; RIVERST, R.; STEIN, C. Algoritmos - Teoria e Prática. Campus, 2002.
