PT | EN

MINISTÉRIO DA EDUCAÇÃO

UNIVERSIDADE FEDERAL DE SANTA CATARINA

CENTRO TECNOLÓGICO

DEPARTAMENTO DE INFORMÁTICA E ESTATÍSTICA

PROGRAMA DE ENSINO

1. Identificação

Disciplina:INE5413 - Grafos
Nível:Graduação
Carga Horária:72 horas-aula (Teórica: 44; Prática: 28)
Vigência:De 2023-1 até a presente data

2. 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.

3. Cursos Relacionados

4. Objetivos

4.1 Objetivo 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

4.2 Objetivos 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.

5. Conteúdo Programático

  1. CONCEITOS BÁSICOS [4 horas-aula]
    1. História da teoria de grafos
    2. Representação de problemas com grafos
    3. Grafos, digrafos e multigrafos
    4. Isomorfismo
    5. Grafos regulares, completos e bipartidos
    6. Grafos rotulados e valorados
  2. REPRESENTAÇÕES COMPUTACIONAIS [4 horas-aula]
    1. Matriz de adjacência
    2. Matriz de incidência
    3. Representações com Listas e Dicionários (mapeamento)
    4. Classes para grafos numa linguagem de programação orientada a objetos
  3. COMPLEXIDADE DE ALGORITMOS SOBRE GRAFOS [6 hora-aula]
  4. CAMINHAMENTO [20 horas-aula]
    1. Caminhos e ciclos
    2. Percursos eulerianos e hamiltonianos
    3. Caminho de custo mínimo
    4. Problemas de travessia
  5. CONEXIDADE [8 horas-aula]
    1. Grafos conexos e desconexos
    2. Componentes conexas e fortemente conexas
    3. Pontes e vértices de corte
    4. Base e Anti-base
    5. Grafo reduzido
  6. ÁRVORES [8 horas-aula]
    1. Propriedades elementares de árvores
    2. Arborescência
    3. Árvore geradora
    4. Árvore de custo mínimo
  7. PLANARIDADE, COLORAÇÃO E ESTABILIDADE [8 horas-aula]
    1. Critérios de planaridade de grafos
    2. Coloração aproximada
    3. Número cromático
    4. Coloração de mapas
    5. Estabilidade Interno (conjunto independente)
    6. Estabilidade Externa (conjunto absorvente)
  8. REDES [8 horas-aula]
    1. Definição de Redes
    2. Fluxo máximo em redes
    3. Caminho crítico
  9. EMPARELHAMENTO (Acoplamento) [6 horas-aula]
    1. Acoplamento máximo
    2. Acoplamento em grafos bipartidos
    3. Acoplamento em grafos quaisquer

6. Bibliografia Básica

  1. DE SANTIAGO, R. Anotações para a Disciplina de Grafos, 2022, disponível em www.inf.ufsc.br/~r.santiago/downloads/INE5413.pdf
  2. CORMEN, Thomas H. et al. Algoritmos: teoria e prática. Rio de Janeiro: Elsevier, 2012. xvi, 926 p.
  3. NETTO, Paulo O. B. Teoria e Modelos de Grafos. 4º Edição. Edgard blücher. São Paulo, 2006.
  4. JUNGNICKEL, D. Graphs, Networks and Algorithms, 3a Edição, Berlin: Springer, 2008. DOI: https://doi.org/10.1007/978-3-540-72780-4
  5. 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

7. Bibliografia Complementar

  1. KLEINBERG, Jon; TARDOS, Éva. Algorithm design. Boston: Pearson Addison Wesley, 2006.
  2. CRISTOFIDES, N. Graph Theory - an Algorithmic Approach. Academic Press, 1975.
  3. FURTADO, A. L. Teoria dos Grafos - Algoritmos. PUC/RJ-LTC, 1973.
  4. SZWARCFILER, Jaime. L. Grafos e Algoritmos Computacionais. Campus, 1984.
  5. WILSON, R. J. Introduction to Graph Theory. 1979.
  6. HARAY, F. Graph Theory. Addison-Wesley, 1969.
  7. GERSTING, Judith L.Fundamentos Matemáticos para a Ciência da Computação. LTC - Livros Técnicos e Científicos, 1982.
  8. CAMPELLO, Ruy Eduardo e MACULAN, Nelson. Algorítimos e Heurísticas. Universidade Federal Fluminense, 1994.
  9. CHARTRAND, Gary. Graphs as Mathematical Models. Prindle, Weber & Schmidt. Boston, 1977.
  10. SCHEINERMAN, E. R. Matemática Discreta: Uma introdução - Tradução da 3ª ed. norte-americana. Cengage Learning Brasil, 2016.
  11. ZIVIANI, N. Projeto de Algoritmos: com implementações em JAVA e C++. Cengage Learning Brasil, 2012.