Programa de Ensino 20082
Aprovado pelo Departamento em: 8-7-2008
- Identificação:
- Disciplina: INE5312 - Teoria dos Grafos
- Carga horária: 54 horas-aula
Teóricas: 54
Práticas: 0
- Período:
Início da oferta da disciplina até a presente data
- Curso(s):
- Ciências da Computação (208)
- Requisito(s):
- Ciências da Computação (208)
- INE5381 - Fundamentos Matemáticos da Informática
- INE5382 - Introdução à Computação
- Ementa:
- Noções básicas de grafos. Representação de grafos. Distâncias. Coloração. Grafos acíclicos e expansão de grafos em árvores. Planaridade. Problemas do caminho mínimo. Problemas Eulerianos e Hamiltonianos. Fluxo em redes.
- Objetivo(s):
- Geral: Apresentar a teoria de grafos enquanto ferramenta para construção de modelos para algumas classes de problemas e exercitar o seu uso enquanto estrutura de dados computacional.
- Específicos:
- Apresentar os conceitos inerentes à teoria dos grafos;
- Capacitar o estudante a modelar problemas e situações utilizando grafos;
- Habilitar o estudante a manipular grafos enquanto estrutura de dados;
- Habilitar o estudante a desenvolver algoritmos para manipulação de grafos.
- Conteúdo Programático:
- CONCEITOS BÁSICOS [6 horas-aula]
- História da teoria de grafos
- Representação de problemas com grafos
- Grafos, digrafos e multigrafos
- Isomorfismo
- Grafos regulares, completos e bipartidos
- Grafos rotulados e valorados
- REPRESENTAÇÕES COMPUTACIONAIS [4 horas-aula]
- Matriz de adjacência
- Matriz de incidência
- Representações com Listas e Dicionários (mapeamento)
- Classes para grafos numa linguagem de programação orientada a objetos
- CAMINHAMENTO [12 horas-aula]
- Caminhos e ciclos
- Percursos eulerianos e hamiltonianos
- Caminho de custo mínimo
- Problemas de travessia
- CONEXIDADE [7 horas-aula]
- Grafos conexos e desconexos
- Componentes conexas e fortemente conexas
- Pontes e vértices de corte
- Base e Anti-base
- ÁRVORES [7 horas-aula]
- Propriedades elementares de árvores
- Arborescência
- Árvore geradora
- Árvore de custo mínimo
- PLANARIDADE, COLORAÇÃO E ESTABILIDADE [12 horas-aula]
- Critérios de planaridade de grafos
- Coloração aproximada
- Número cromático
- Coloração de mapas
- Estabilidade Interno (conjunto independente)
- Estabilidade Externa (conjunto absorvente)
- REDES [6 horas-aula]
- Definição de Redes
- Fluxo máximo em redes
- Caminho crítico
- Bibliografia Básica:
- NETTO, Paulo O. B. Teoria e Modelos de Grafos. Edgard blücher. São Paulo, 1979.
- CRISTOFIDES, N. Graph Theory - an Algorithmic Approach. Academic Press, 1975.
- SZWARCFILER, Jaime. L. Grafos e Algoritmos Computacionais. Campus, 1984.
- Bibliografia Complementar:
- FURTADO, A. L. Teoria dos Grafos - Algoritmos. PUC/RJ-LTC, 1973.
- WILSON, R. J. Introduction to Graph Theory. 1979.
- HARAY, F. Graph Theory. Addison-Wesley, 1969.
- GERSTING, Judith L.Fundamentos Matemáticos para a Ciência da Computação. LTC - Livros Técnicos e Científicos, 1982.
- CAMPELLO, Ruy Eduardo e MACULAN, Nelson. Algorítimos e Heurísticas. Universidade Federal Fluminense, 1994.
- CHARTRAND, Gary. Graphs as Mathematical Models. Prindle, Weber & Schmidt. Boston, 1977.