Carga horária da disciplina: 4 horas/aula

Professor(es) em 2024-2

Turma 11

Professor: Marco Antonio Moreira de Carvalho - www | e-mail Horários: Segunda-feira (10h10 - 11h50) Quarta-feira (10h10 - 11h50)

Objetivos

Ao final do curso espera-se que os alunos possuam os seguintes conhecimentos e habilidades:
Conhecimentos básicos sobre teoria dos grafos;
Capacidade de modelagem de problemas na forma de grafos;
Compreensão do funcionamento alguns algoritmos sobre grafos.

Ementa

Grafos orientados e não-orientados; caminhos; planaridade; conectividade; coloração; grafos infinitos; problemas intratáveis; busca em largura e profundidade; algoritmos do menor caminho; árvore geradora; ordenação topológica.

Conteúdo Programático

- Introdução e estruturas de dados para grafos
- Formalização: definições
- Isomorfismo
- Complementaridade e subgrafos
- Teorema do aperto de mãos e bipartição
- Passeio, cadeia e caminho
- Transitividade e conectividade
- Busca em grafos: busca em profundidade e largura
- Algoritmos de caminhos mínimos:
        - Dijkstra
        - Bellman-Ford
        - Floyd-Warshall
- Ordenação topológica
- Fluxo em redes: Ford-Fulkerson
- Problemas Intratáveis
- Casamento em grafos e Algoritmo Húngaro
- Conjuntos independentes, cliques e conjuntos dominantes
- O problema das 4 cores: coloração de mapas
- Coloração de grafos
- Planaridade em grafos
- Busca de soluções usando grafos

Bibliografia

- BOAVENTURA NETTO, Paulo Oswaldo. Grafos:  teoria, modelos, algoritmos. 2. ed. rev. e ampl. São Paulo: Edgard Blucher, 2001.
- GOLDBARG, Marco Cesar; GOLDBARG, Elizabeth Ferreira Gouvêa. Grafos:  conceitos, algoritmos e aplicações . Rio de Janeiro: Elsevier, 2012.
- AHUJA, Ravindra K.; MAGNANTI, Thomas L; ORLIN, James B. Network flows: theory, algorithms and applications. Englewood Cliffs: Prentice-Hall, 1993.

Bibliografia complementar

- JUNGNICKEL, D. Graphs, networks, and algorithms. 3. ed. Berlin: New York: Springer, 2008.
- GROSS, Jonathan L; YELLEN, Jay. Graph theory and its applications. 2.ed. Boca Raton: CRC Press, 2006.
- WILSON, Robin J. Introduction to graph theory. 3. ed. New York: John Wiley & Sons, 1990.
- HARARY, Frank. New directions in the theory of graphs. New York: London: Academic Press, 1973.
- CORMEN, Thomas H. Algoritmos:  teoria e prática. Rio de Janeiro: Campus, 2002.
- GIBBONS, Alan. Algorithmic graph theory. New York: Cambridge, 1994.