Departamento de Informática e Estatística

Programas de Ensino
Visitante (Entrar)

Programa de Ensino 20082

Aprovado pelo Departamento em: 8-7-2008

  1. Identificação: Visualizar em PDF
    • 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
  2. Curso(s):
    • Ciências da Computação (208)
  3. Requisito(s):
    • Ciências da Computação (208)
      • INE5381 - Fundamentos Matemáticos da Informática
      • INE5382 - Introdução à Computação
  4. 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.
  5. 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:
      1. Apresentar os conceitos inerentes à teoria dos grafos;
      2. Capacitar o estudante a modelar problemas e situações utilizando grafos;
      3. Habilitar o estudante a manipular grafos enquanto estrutura de dados;
      4. Habilitar o estudante a desenvolver algoritmos para manipulação de grafos.
  6. 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
  7. 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.
  8. 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.