Projeto - Análise de Grafos

Grafos é um assunto chato, muito chato realmente, tanto que se você pegar um livro poderá ler coisas como: Um grafo G consiste de dois conjuntos V e E. Onde V é um conjunto finito e não vazio de vértices e E é um conjunto de pares não ordenados de vértices chamados arestas. Sendo que V(G) e E(G) representam os conjuntos de vértices e arestas do grafo G, também denotado por G=(V,E). Lindo e maravilhoso para tornar os Grafos tão atrativos quanto os Logaritmos.

Porém como os Logaritmos, Grafos sao extremamente úteis para qualquer Analista ou Projetista, mas não apenas para eles e não serve apenas a área de informática, basicamente podem ser utilizados para quase toda forma de projeção futura. Vamos com calma, tentarei desmistificar seu uso e torná-los mais atrativos. Um grafo nada mais é do que a visualização de um bando de pontos ligados (lembra de um joguinho que aparecia no jornal chamado Liga Pontos, no qual após ligados formava uma figura), normalmente são utilizados para representar os diferentes caminhos que pode-se percorrer. Por exemplo, para sair da sua casa e chegar ao local onde ocorrerá aquela fantástica festa podemos seguir diversos caminhos, então poderíamos responder as seguintes perguntas:

• Qual o caminho mais curto a seguir?
• Qual o caminho onde passaremos por mais pontos turísticos?
• Qual o caminho com menos tráfego?
• Qual o caminho que passamos por um mercado?
• E diversas outras questões

Conta-se que quem primeiro se utilizou dos grafos foi Euler, em 1736, para resolver um problema de caminhar em pontes entre duas ilhas cortadas por um rio*. Só que atualmente não utilizamos mais papel e lápis para desenhar grafos, o MS Project faz isso muito bem, porém ainda prefiro um programa especialmente feito para isso, utilizo o Grafos** de Alejandro Rodríguez Villalobos, que além de permitir a construção rápida de um grafo (com o mouse se faz praticamente tudo) ainda permite várias formas de análise deste, tais como:

• Caminho Mínimo e Crítico e a Árvore Mínimo e Máximo baseado no algorítmo de Dijkstra
• Caminho Mínimo e Crítico baseado no algorítmo de BellmanFord
• Todos os Caminhos Mínimos baseado no algorítmo de FloydWarshall
• Árvore do Valor Total Mínimo e Máximo baseado no algorítmo de Kruskal
• Árvore do Valor Total Mínimo e Máximo baseado no algorítmo de Prim
• Fluxo Máximo baseado no algorítmo de FordFulkerson
• Transborde Equilibrado a Custo Mínimo
• Localização do Custo Mínimo
• E uma série de outros

Por ser um software livre, garanto que atende muito bem a todos que desejam conhecer, aprender e desfrutar do prazer de ter seu projeto (ou mesmo seu passeio) totalmente controlado.

Abraços e até a próxima
Fernando Anselmo

* Grafos e Algoritmos Computacionais de J.L Szwarcfiter, Ed. Campus, 1984.
** http://arodrigu.webs.upv.es/grafos/doku.php