Programa de Ensino 20231
Aprovado pelo Departamento em: 31-10-2022
- Identificação:
- 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
- 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)
- 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
- 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.
- 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;
- Habilitar o estudante a avaliar a complexidade de algoritmos sobre grafos.
- 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
- 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
- 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.