GRAFO, QUE BICHO É ESSE?
Grafo é uma estrutura abstrata que pode representar uma série de objetos do dia a dia e comumente denotado por G(V,A) onde V é um conjunto não vazio de objetos denominados vértices e A é um conjunto de pares (ordenados ou não) de V, chamado arestas (ligações entre os vértices). Veja figura abaixo:
Uma definição clara para grafos seria: abstração que permite codificar relacionamentos entre pares de objetos.
Que objetos?
Qualquer um! Ex. setores, pessoas, cidades, empresas, países, páginas da web, filmes, etc...
Que relacionamentos?
Qualquer um! Ex. amizade, conectividade, produção, língua falada, etc.
Veja abaixo um exemplo simples:
O grafo acima poderia representar as linhas de transporte de passageiros da empresa Águia-Real entre as cidades indicadas.
Esta idéia simples pode ser ampliada, por exemplo:
Um mapa rodoviário (cidades se relacionam através das várias estradas), Um sistema de distribuição de água (os canos e entre as centrais de distribuição), O relacionamento social entre pessoas (as pessoas são os vértices e as arestas são as relações de amizades).
O Orkut é um exemplo de rede de relacionamentos, ou seja um grafo. Quando o Orkut sugere para uma usuário novos possíveis amigos, o que ele está fazendo na verdade e enxergar as ligações dos seus amigos que não se ligam a você, ou seja, amigos dos seus amigos, possivelmente, são seus amigos.
Enfim os grafos são muito úteis na representação de problemas da vida real e a teoria dos grafos vem sendo largamente utilizada para representar o formalismo das redes complexas, onde o número de nós e de conexões entre esses nós é muito alto e complexamente estabelecido. Não é preciso dizer que o uso de tecnologias se faz necessária para resolução de problemas ainda que aparentemente simples.
Prof. Renato Santos Pereira.
