Teoria dos Grafos e Aplicações

Prof. Eduardo Ono

 

Descrição

• Introdução à Teoria dos Grafos, aplicações e implementação computacional.

 

Binder

• https://mybinder.org/v2/gh/eduardo-ono/Teoria-dos-Grafos-e-Aplicacoes/main

 

Conteúdo Programático

Aula	Data	Descrição
01	11/08	Apresentação da disciplina; Introdução à Teoria dos Grafos; Aplicações; História da Teoria dos Grafos; Problema das sete pontes de Königsberg; Fundamentos de Lógica.
02	18/08	Ambiente de desenvolvimento; Fundamentos da programação em Python.
03	25/08	Conceitos básicos e terminologias: grafo, subgrafos, grafos rotulados e valorados; Representação de grafos: Diagrama gráfico, matriz de adjacências, matriz de incidência e lista de adjacências.
04	01/09	Percursos em grafos; Algoritmos de busca: Busca em largura (BFS) e busca em profundidade (DFS).
05	08/09	Algoritmos de busca: Busca em profundidade (DFS); Conexidade, conectividade e problemas de caminhos.
06	14/09	Caminhos de custo mínimo; Algoritmos de Dijkstra, Bellman-Ford e Floyd-Warshall.
	29/09	1ª Avaliação
07	13/10	Conceitos de percurso (passeio), caminho, ciclo (circuito); Grafos e circuitos Eulerianos; Algoritmo de Fleury.
08	20/10	[Grafos e Caminhos Eulerianos]; Problema do Carteiro Chinês.
09	27/10	[Grafos Hamiltonianos]; Problema do Caixeiro Viajante.
10	03/11	Planaridade (Grafos planares); Coloração; Coloração de mapas.
11	10/11	Coloração: Teorema das quatro cores; Aplicação: Sudoku.
12	17/11	Coloração própria; Número cromático.
13	24/11	Grafos Planares: Teorema de Kuratowsky; Revisão para a prova.
	01/12	2ª Avaliação
14		Árvores e árvore geradora mínima
15		Fluxos em Redes

 

Pré-Requisitos

• Introdução à Programação
• Estrutura de Dados

 

Recursos

• https://graphclasses.org

• https://cmps-people.ok.ubc.ca/ylucet/DS/Algorithms.html

• https://colab.research.google.com

• https://networkx.org/documentation/stable/reference/index.html

• NetworkX: https://walkenho.github.io/graph-theory-and-networkX-part1/

• LaTeX: https://www.caam.rice.edu/~heinken/latex/symbols.pdf

 

Bibliografia Básica

Capa	Descrição
	[SZWARCFITER_2018] SZWARCFITER, Jayme Luiz; Teoria Computacional de Grafos: Os Algoritmos. 1. ed., GEN LTC, 2018.
	[BONDY_2007] BONDY, J. A.; MURTY, U. S. R.; Graph Theory. 1. ed., 2007.
	[TRUDEAU_1993] TRUDEAU, Richard J. Introduction to Graph Theory. 1. ed. Cidade: Editora, Ano. Resenha: https://www.youtube.com/watch?v=dJL4_p4f2Qg
	[BOAVENTURA-NETTO_2017] BOAVENTURA NETTO, Paulo Oswaldo; JURKIEWICZ, Samuel. Grafos: Introdução e Prática. 2. ed. São Paulo: Blucher, 2017. Online: https://plataforma.bvirtual.com.br/Acervo/Publicacao/177879
	[SIMOES-PEREIRA_2013] SIMÕES-PEREIRA, J. M. S. Grafos e Redes: Teoria e Algoritmos Básicos. 1. ed. Rio de Janeiro: Interciência, 2013. Online: https://plataforma.bvirtual.com.br/Acervo/Publicacao/42049

 

Bibliografia Complementar

Capa	Descrição
	[DOWNEY-2e_2016] DOWNEY, Karin R. Pense em python: Pense como um cientista da computação. 1. ed. Boca Raton: Taylor & Francis, 2017. epub: https://github.com/PenseAllen/PensePython2e/raw/master/ebooks/PenseEmPython2e.epub
	[KURGALIN-2e_2020] KURGALIN, Sergei; BORZUNOV, Sergei. The Discrete Math Workbook. 2. ed., 2020.
	[GOLDBARG_2012] GOLDBARG, Marco Cesar; GOLDBARG, Elizabeth. Grafos: conceitos, algoritmos e aplicações. 1. ed. Rio de Janeiro: Elsevier, 2012.
	[GROSS_2019] GROSS, Jonathan L.; YELLEN, Jay; ANDERSON, Mark. Graph Theory and Its Applications, 1. ed. Cidade: Editora, Ano.
	[SAOUB_2017] SAOUB, Karin R. A Tour Through Graph Theory. 1. ed. Boca Raton: Taylor & Francis, 2017.
	[_2019] . Problemas Clássicos da Computação com Python. 1. ed. , 2019.
	[GOODRICH_2013] Data Structures and Algorithms in Python. 1. ed., 2013.
	[DROZDEK-4e_2012] Data Structures and Algorithms in C++. 4. ed. Cengage Learning, 2012.
	[DIESTEL-3e_2005] Graph Theory. 3. ed., 2005.

 

Vídeos Recomendados

Thumb	Descrição
	[Reducible] Introduction to Graph Theory: A Computer Science Perspective (16:25, YouTube, Jun/2020)
	[Ciência Todo Dia] O Problema de 1 MILHÃO de DÓLARES (13:20, YouTube, Set/2021)
	[Reducible] PageRank: A Trillion Dollar Algorithm (25:25, YouTube, Mai/2022)

 

Filmes e Documentários Recomendados

Thumb	Descrição
	The Man Who Knew Infinity (2015) / O Homem que Viu o Infinito (1:48:35, YouTube, Jan/2020)
	Good Will Hunting (1997) / Gênio Indomável (4:16, YouTube, Abr/2020)
	[Andrew Rozario] The Right Match: A Short Documentary (21:42, YouTube, Nov/2013)
	[Cederj : Tec em Sistemas de Computação : UFF] Matemática e computação: uma união estável (22:39, YouTube, Abr/2018)
	[フジテレビ公式] SUSPECT X Trailer 【Fuji TV Official】 (1:30, YouTube, Mar/2013)