Departamento de Informática e Estatística

Programas de Ensino
Visitante (Entrar)

Programa de Ensino 20231

Aprovado pelo Departamento em: 31-10-2022

  1. Identificação: Visualizar em PDF
    • Disciplina: INE5413 - Grafos
    • Carga horária: 72 horas-aula      Teóricas: 44      Práticas: 28
    • Período: 1º semestre de 2023 até a presente data
  2. Curso(s):
    • Ciências da Computação (208)
    • Engenharia, áreas Elétrica e Mecânica, habilitação Controle e Automação (220)
    • Matemática, Habilitação Bacharelado (222)
    • Sistemas de Informação (238)
  3. Requisito(s):
    • Ciências da Computação (208)
      • INE5403 - Fundamentos de Matemática Discreta para Computação
      • INE5408 - Estruturas de Dados
    • Matemática, Habilitação Bacharelado (222)
      • INE5408 - Estruturas de Dados
      • MTM3510 - Introdução à Combinatória e Probabilidade
    • Sistemas de Informação (238)
      • INE5601 - Fundamentos Matemáticos da Informática
      • INE5609 - Estruturas de Dados
      • INE5601 - Fundamentos Matemáticos da Informática
      • INE5609 - Estruturas de Dados
  4. Ementa:
    • Grafos e grafos orientados. Representação de problemas com grafos. Caminhos, ciclos e caminho de custo mínimo. Conexidade e alcançabilidade. Árvores e árvore de custo mínimo. Coloração e planaridade de grafos. Grafos hamiltonianos e eulerianos. Fluxo máximo em redes. Estabilidade e emparelhamento em grafos. Problemas de cobertura e de travessia. Representações computacionais e complexidade de algoritmos em grafos.
  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;
      5. Habilitar o estudante a avaliar a complexidade de algoritmos sobre grafos.
  6. Conteúdo Programático:
    • CONCEITOS BÁSICOS [4 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
    • COMPLEXIDADE DE ALGORITMOS SOBRE GRAFOS [6 hora-aula]
    • CAMINHAMENTO [20 horas-aula]
      • Caminhos e ciclos
      • Percursos eulerianos e hamiltonianos
      • Caminho de custo mínimo
      • Problemas de travessia
    • CONEXIDADE [8 horas-aula]
      • Grafos conexos e desconexos
      • Componentes conexas e fortemente conexas
      • Pontes e vértices de corte
      • Base e Anti-base
      • Grafo reduzido
    • ÁRVORES [8 horas-aula]
      • Propriedades elementares de árvores
      • Arborescência
      • Árvore geradora
      • Árvore de custo mínimo
    • PLANARIDADE, COLORAÇÃO E ESTABILIDADE [8 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 [8 horas-aula]
      • Definição de Redes
      • Fluxo máximo em redes
      • Caminho crítico
    • EMPARELHAMENTO (Acoplamento) [6 horas-aula]
      • Acoplamento máximo
      • Acoplamento em grafos bipartidos
      • Acoplamento em grafos quaisquer
  7. Bibliografia Básica:
    • DE SANTIAGO, R. Anotações para a Disciplina de Grafos, 2022, disponível em www.inf.ufsc.br/~r.santiago/downloads/INE5413.pdf
    • CORMEN, Thomas H. et al. Algoritmos: teoria e prática. Rio de Janeiro: Elsevier, 2012. xvi, 926 p.
    • NETTO, Paulo O. B. Teoria e Modelos de Grafos. 4º Edição. Edgard blücher. São Paulo, 2006.
    • JUNGNICKEL, D. Graphs, Networks and Algorithms, 3a Edição, Berlin: Springer, 2008. DOI: https://doi.org/10.1007/978-3-540-72780-4
    • SKIENA, S. S. 1. The Algorithm Design Manual, Springer, 2a Edição, London: Springer, 2008. DOI: https://doi.org/10.1007/978-1-84800-070-4
  8. Bibliografia Complementar:
    • KLEINBERG, Jon; TARDOS, Éva. Algorithm design. Boston: Pearson Addison Wesley, 2006.
    • CRISTOFIDES, N. Graph Theory - an Algorithmic Approach. Academic Press, 1975.
    • FURTADO, A. L. Teoria dos Grafos - Algoritmos. PUC/RJ-LTC, 1973.
    • SZWARCFILER, Jaime. L. Grafos e Algoritmos Computacionais. Campus, 1984.
    • 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.
    • SCHEINERMAN, E. R. Matemática Discreta: Uma introdução - Tradução da 3ª ed. norte-americana. Cengage Learning Brasil, 2016.
    • ZIVIANI, N. Projeto de Algoritmos: com implementações em JAVA e C++. Cengage Learning Brasil, 2012.