#Educador

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 chamados de arestas (ligações entre os vértices).

Uma definição clara para grafos seria: abstração que permite codificar relacionamentos entre pares de objetos.

Que objetos:

Qualquer um! Ex. pessoas, cidades, empresas, países, páginas da Web, filmes etc.

Que relacionamentos:

Qualquer um! Ex. amizade, conectividade, produção, língua falada etc.

Exemplos práticos:

Um mapa rodoviário (cidades se relacionam através de várias estradas), um sistema de distribuição de água (os canos e entre as centrais de distribuição), relacionamento social entre as pessoas (as pessoas são os vértices e as arestas são as relações de amizade).

O orkut é um exemplo de rede de relacionamentos, ou seja, um grafo. Quando o Orkut sugere para o usuário novos possíveis amigos, o que ele está fazendo na verdade é 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 vendo 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 estabelecidos. Não é preciso dizer que o uso de tecnologias se faz necessaria para resolução  de problemas ainda que aparentemente simples.

Texto elaborado pelo prof. Renato Santos Pereira.

Mestre em Engenharia de Produção (COPPE/UFRJ).