Teoria de Grafos

Segundo o professor Paulo Feofiloff, do Instituto de Matemática e Estatística da USP, a teoria dos grafos e sua linguagem são úteis em muitas áreas da computação, da matemática e da engenharia pois grafos são um bom modelo para muitos problemas fundamentais nessas áreas. Uma das preocupações centrais da teoria dos grafos é a construção de algoritmos eficientes para a solução de problemas sobre grafos. Muitos desses problemas foram motivados por importantes aplicações práticas.[2]

Ainda segundo Paulo Feofiloff, alguns dos problemas computacionais da teoria dos grafos são: isomorfismo, caminho mínimo, circuito máximo (e circuito hamiltoniano), decomposição em circuitos e cobertura por circuitos, conjunto estável máximo, emparelhamento máximo, coloração mínima de vértices, coloração mínima de arestas, coleções disjunta máximo de caminhos (fluxo máximo), planaridade.[2]

Segundo o Currículo de Referência, "Teoria dos Grafos" deve abranger os sub-tópicos: Grafos orientados e não-orientados. Caminhos. Planaridade. Conectividade. Coloração. Grafos Infinitos. Algoritmos em grafos. Problemas intratáveis.[1]

Na Universidade Federal de Sergipe o tema "Teoria dos Grafos" é abordado na disciplina "Grafos e Algoritmos Computacionais" sob o código 103453. A disciplina possui a seguinte ementa:

Introdução à Teoria dos Grafos: histórico, terminologia básica, grafos orientados e não orientados, subgrafos, passeios, caminhos, trilhas, conectividade, árvores, emparelhamento, planaridade, coloração, fluxo em redes.
Representação de grafos: matrizes de adjacência, incidência e estruturas de adjacência. Algoritmos fundamentais em grafos: ordenação por caixas, ordenação topológica, busca em largura, em profundidade, lexicográfica, irrestrita, determinação de componentes biconexos e fortemente conexos, árvores geradoras mínimas, caminhos mínimos, coloração aproximada, emparelhamento em grafos bipartidos e fluxo máximo em redes.
Corretude dos algoritmos.
NP-completude: introdução, a classe P, NP, Co-NP e NP-completo, transformações polinomiais, reduções, restrições e extensões de problemas, noções de algoritmos de aproximação.

[1] Currículo de Referência
[2] http://www.ime.usp.br/~pf/grafos-exercicios/index.html



Por Alan Vinícius