| Ementa: |
Introdução à teoria dos grafos: motivação, exemplos de aplicações, conceitos básicos (grafos e subgrafos, grau de vértices, caminhos e ciclos, grafos regulares e bipartidos, grafos eulerianos e hamiltonianos, grafos direcionados, grafos ponderados, conectividade e planaridade). Representação de grafos: tipos de representações (matrizes de adjacências, listas de adjacências e hash). Operações: união, interseção, diferença, complemento, produto, composição. Implementação de algoritmos em grafos: exploração e ordenação (algoritmos de busca em profundidade, busca em amplitude e ordenação topológica), conectividade (algoritmo de Tarjan), árvore geradora mínima (algoritmos de Kruskal e Prim), menores caminhos a partir de uma fonte (algoritmos de Dijkstra e Bellman-Ford), coloração. Aplicação dos algoritmos em problemas de Ciência da Computação. Aplicações em Problemas Ambientais. |
