Aulas Teóricas: 78

A) EMENTA
Grafos e Árvores. Grafos e Algoritmos.


B) OBJETIVOS / COMPETÊNCIAS
Capacitar os alunos com os conceitos teóricos a respeito de grafos e fornecer os recursos da teoria dos grafos para resolução de problemas e dando-lhes oportunidade de desenvolver suas habilidades de programação, elaborando programas para a manipulação de grafos.


C) BASES TECNOLÓGICAS (CONTEÚDO PROGRAMÁTICO)
1. Revisão de operação booleana
2. Grafos e Árvores
2.1. Definição de grafos
2.2. Terminologia de grafos
2.2.1. Grafos simples e completos
2.2.2. Grafos isomorfos
2.2.3. Grafos bipartites completos
2.2.4. Grafos planares
2.2.5. Grafos homeomorfos
2.2.6. Grafos direcionados
2.2.7. Teorema sobre o número de vértices e arestas
2.3. Teorema de Kuratowski
2.4. Coloração
2.4.1. Coloração e número cromático
2.4.2. Teorema das quatros cores
2.4.3. Teorema das cinco cores
2.5. Árvores
2.5.1. Definição de árvore
2.5.2. Árvore binária
2.5.3. Teorema do número de arestas de uma árvore
2.6. Representações computacionais de grafos
2.6.1. Representação de um grafo através de sua definição
2.6.2. Representação através de matrizes de adjacências
2.6.3. Representação através de lista de adjacências
2.6.4. Implementação de listas de adjacências através de vetores e ponteiros
2.6.5. Representação através de árvores binárias
2.6.6. Árvores de decisão
2.6.7. Código de Huffman
3. Grafos e Algoritmos
3.1. Complexidade de algorítmo
3.2. Caminho Euleriano e ciclo Hamiltoniano
3.2.1. Definição de um caminho Euleriano
3.2.2. Solução do problema do caminho Euleriano
3.2.3. Análise do algoritmo
3.2.4. Discussão do problema do ciclo Hamiltoniano
3.3. Caminho mínimo e árvore geradora mínima
3.3.1. Algoritmo de Dijkstra
3.3.2. Análise do algoritmo
3.3.3. Discussão do algoritmo para obtenção da árvore geradora mínima
3.4. Algoritmos de Busca
3.4.1. Algoritmo para busca em profundidade e em largura
3.4.2. Análise dos algoritmos de busca
3.5. Articulações e redes de computadores
3.5.1. Discussão sobre articulações e componentes biconexas em um grafo para redes de
computadores e de comunicações
3.5.2. Algoritmo para detecção de articulações em um grafo simples conexo


D) ATIVIDADES DISCENTES
1. Provas
2. Trabalhos
3. Listas de exercícios
4. Seminários


E) AVALIAÇÃO
1. Prova escrita
2. Seminários
3. Trabalhos práticos


F) BIBLIOGRAFIA BÁSICA
FURTADO, A. L. Teoria dos Grafos - Algoritmos. Rio de Janeiro: PUC/RJ-LTC, 1973.
GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação. Rio de Janeiro: LTC, 1993.
SZWARCFITER, J. L. Grafos e Algoritmos Computacionais. Rio de Janeiro: Campus, 1992.

BIBLIOGRAFIA COMPLEMENTAR
CHARTRAND, Gary. Graphs as Mathematical Models. Boston: Prindle, Weber & Schmidt, 1977.
CRISTOFIDES, N. Graph Theory - an Algorithimic Approach. Academic Press, 1975.
HARAY, F. Graf Theory. Addison-Wesley, 1969.
NETTO, Paulo O. B. Teoria e Modelos de Grafos. São Paulo: Edgard Blücher, 1979.
SIPSER, Michael. Introdução à teoria da computação. Cengage Learning, 2011.
SZWARCFILER, Jaime L. Grafos e algoritmos Computacionais. Rio de Janeiro: Campus, 1984.
WILSON, R. J. Introduction to Graph Theory. 1979.