PLANO DE ENSINO
2º SEMESTRE DE 2025
I. IDENTIFICAÇÃO
Instituto de Ciências Exatas e Tecnológicas
Curso: Ciência da Computação
Disciplina: Teoria dos Grafos
Carga horária semestral: 64 h CH Teórica: 48h CH Prática: 16h
Ano: 2025-2 Turma/turno: integral
Docente: Joslaine Cristina Jeske de Freitas
Nº de vagas: 60
Modalidade: Presencial
II. EMENTA
Noções básicas de grafos: definições, representação, propriedades notáveis e isomorfismo.
Planaridade. Caminhos e Circuitos. Coloração. Matching. Conjuntos independentes de vértices.
Grafos dirigidos. Fluxos em Redes: noções gerais.
III. OBJETIVOS
Objetivo Geral
Dar aos alunos noções de teoria dos grafos e apresentar o seu uso na resolução de problemas.
Objetivos Específicos
− Conhecer conceitos básicos e intermediários da teoria dos grafos.
− Apresentar diferentes algoritmos em grafos para problemas computacionais.
− Desenvolver a capacidade de representar problemas computacionais através de grafos.
− Implementar algoritmos através do uso das técnicas da teoria dos grafos
IV. CONTEÚDO PROGRAMÁTICO E CRONOGRAMA
➢ CONTEÚDO PROGRAMÁTICO
✓ Capítulo 1: Revisão
✓ Capítulo 2: Considerações Iniciais sobre Grafos
✓ Capítulo 3: Conceitos iniciais de Grafos
✓ Capítulo 4: Caminhos e Ciclos
✓ Capítulo 5: Representação Matricial de Grafos
✓ Capítulo 6: Árvores, Pontes e Árvores Spanning
✓ Capítulo 7: Problema do Caminho mais Curto
✓ Capítulo 8: Grafos de Euler
✓ Capítulo 9: Grafos Hamiltonianos
✓ Capítulo 10: Emparelhamentos
✓ Capítulo 11: Grafos Planos e Planares
✓ Capítulo 12: Fluxos
INFORMAÇÕES IMPORTANTES: i) o cronograma de aulas consiste em uma previsão e pode sofrer
modificações no decorrer da disciplina; ii) todas as atividades realizadas fora do horário de aula presencial,
são contabilizadas na carga horária de atividade supervisionada com carga horária variável, dependendo da
atividade.
LEGENDA
Avaliações Feriados/Férias Atividades/Eventos da UFJ Reposição Atividades Supervisionadas
Nº AULA DATA CH CONTEÚDO E ATIVIDADE
1 06/ago 2 1. Apresentação da disciplina e visão geral da Teoria dos Grafos
2 07/ago 2 1. Revisão de Conceitos Básicos
3 13/ago 2 2. Considerações iniciais sobre Grafos
5 14/ago 2 3. Conceitos Iniciais de Grafos
6 20/ago 2 4. Caminhos e Ciclos
7 21/ago 2 5. Representação Matricial de Grafos
8 27/ago 2 6. Árvores e pontes
9 28/ago 2 7. Árvores Spanning
10 03/set 2 Exercícios
11 04/set 2 Prova
12 10/set 2 8. Busca em Largura e Profundidade
13 11/set 2 9. Algoritmo de Bellman-Ford
14 17/set 2 CONACET
15 18/set 2 CONACET
16 24/set 2 10. Algoritmo de Dijkstra
17 25/set 2 11. Grafos de Euler
18 01/out 2 12. Problema do Carteiro Chinês
19 02/out 2 13. Grafos Hamiltonianos
20 08/out 2 Exercícios
21 09/out 2 Prova 2
22 15/out 2 CONEPE
23 16/out 2 CONEPE
24 22/out 2 14. Problema do Caixeiro Viajante
25 23/out 2 15. Problema do Caixeiro Viajante - Heurísticas
26 29/out 2 16. Emparelhamentos
27 30/out 2 17. Grafos Planos e Planares
28 05/nov 2 18. Fórmula de Euler e o Teorema de Kuratowski
29 06/nov 2 19. Coloração de Vértices
30 12/nov 2 20. Algoritmo de Floyd-Warshall
31 13/nov 2 21. Fluxo Máximo
32 19/nov 2 22. Método Ford-Fulkerson
20/nov Recesso
33 26/nov 2 Prova 3
27/nov Não haverá aula
03/dez Não haverá aula
34 04/dez 2 Prova Substitutiva
V. METODOLOGIA
− Aulas teóricas expositivas com o uso de projetor multimídia e quadro negro/branco;
− Tarefas dirigidas e orientadas pela investigação e resolução de problemas;
− Aulas Práticas;
− Utilização do ambiente virtual de aprendizagem (SIGAA) para disponibilização de material didático,
notas de aulas, notas de avaliações, aulas virtuais e demais informações relacionadas à disciplina.
VII. PROCESSOS E CRITÉRIOS DE AVALIAÇÃO E CRONOGRAMA:
⮚ 4 (quatro) Avaliações Escritas (AE1, AE2, AE3, ASub) com valor total de 10 (dez) pontos cada uma
e um grupo de implementações que poderão valer como até 1,0 de bônus na média.
✓ AE1: avaliação 1 – 04/09/2025
✓ AE2: avaliação 2 – 09/10/2025
✓ AE3: avaliação 3 – 26/11/2025
✓ ASub: avaliação substitutiva – 04/12/2025
✓ I: Implementações – no decorrer do semestre.
A Nota Final (NF) do aluno será dada pela fórmula:
NF = ((AE1 + AE2 + AE3 + ASub) – min (AE1, AE2, AE3, ASub)) / 3+ I
Observação: Conforme disposto no Capítulo 4 art. 82 do RGCG (RGCG: CEPEC/UFG Nº 1791/2022): Será
aprovado no componente curricular o estudante que obtiver nota final igual ou superior a 6,0 (seis) e
frequência igual ou superior a 75% (setenta e cinco por cento) da carga horária total do componente
curricular, observado o disposto no art. 87 deste RGCG.
VII BIBLIOGRAFIA
Bibliografia Básica
NICOLETTI, Maria do Carmo e HRUSCHKA JR, Estevam Rafael. Fundamentos da teoria dos grafos para
computação, 3. ed., São Paulo: Editora LTC, 2018.
BOAVENTURA NETTO, Paulo Osvaldo. Grafos – teorias, modelos, algoritmos, 4. ed., Edgar Blucher, 2006.
BOAVENTURA NETTO, Paulo Osvaldo e JURKIEWICZ, Samuel. Grafos: introdução e prática,1. ed., Edgar
Blucher, 2009.
Bibliografia Complementar
GOODAIRE, Edgar G.; PARMENTER, Michael M. Discrete mathematics with graph theory.3rd., Prentice
Hall, 2005.
GOLDBARG, Marco., GOLDBARG Elizabeth. Grafos: Conceitos, algoritmos e aplicações. Editora Campus
2012.
SZWARCFITER, Jayme Luiz. Teoria computacional de grafos. Elsevier Editora LTDA, 2018.
SIMOES-PEREIRA, J. M. S. Grafos e Redes. Teoria e Algoritmos Básicos. Editora Interciência, 2014
SCHEINERMAN, Edward R. Matemática discreta – uma introdução.1. ed., São Paulo: Thomson Pioneira,
2003.
GERSTING, Judith. Fundamentos matemáticos para a ciência da computação: Matemática Discreta e Suas
Aplicações, 5 ed. São Paulo, LTC.
Virtual (opcional):
FEOFILOFF, P; KOHAYAKAWA, Y; WAKABAYASHI, Y - Uma Introdução Sucinta à Teoria dos Grafos
https://www.ime.usp.br/~pf/teoriadosgrafos/
MELO, Gildson: Introdução à Teoria dos Grafos - https://repositorio.ufpb.br/jspui/bitstream/tede/7549/5/ar-
quivototal.pdf
BORBA, Milton - Teoria dos Grafos https://miltonborba.org/Algf/Grafos.htm
Jataí, 04 de agosto de 2025.
Joslaine Cristina Jeske de Freitas
Professora
