O que é e pra que serve um grafo?
For geeks dezembro 20th, 2008
Dando continuidade aos posts com breves definições e explicações sobre assuntos interessantes na ciência da computação, hoje vou falar sobre grafos. Você já parou pra se perguntar, por exemplo, como funciona o orkut? A teoria dos grafos está por trás disso e muito mais…
Basicamente um grafo é uma estrutura de dados que possui vértices e arestas, onde os vértices são representações de “coisas” e as arestas são ligações que essas “coisas” podem ter entre si.
Um exemplo prático:
Qualquer rede social (myspace, facebook, orkut, etc) utiliza a idéia de grafos, onde cada usuário é um vértice desse grafo. O usuário pode ter suas próprias características, mas no final das contas é somente um vértice do grafo. A característica mais importante de cada usuário é a quem ele mantém ligações/conexões, no nosso caso quem são os amigos do usuário. Essas ligações são arestas entre os usuários. Note que o número de arestas partindo de um vértice é variável. É possível ser amigo de quantas pessoas quiser dentro de uma rede social, mas questões de implementação às vezes limitam esse número de arestas partindo de um vértice.
Um outro exemplo de grafo pode ser uma representação das ruas de uma cidade e quadras (que contém um conjunto de casas), os vértices são as casas e as arestas são as ruas. Uma diferença básica entre esse grafo e o das redes sociais é que no caso das ruas de uma cidade as arestas são direcionadas, ou seja, existem ruas que só podem ser percorridas em uma direção (na direção oposta seria contra-mão se você fosse de carro), portanto esse grafo é chamado grafo direcionado. Em outras palavras, no caso da rede social a direção não importa, afinal se A é amigo de B, B necessáriamente é amigo de A, já o caminho pra ir de um ponto X para o ponto Y pode precisar passar pela rua a e depois b para chegar, enquanto o caminho de volta de Y para X precise ir de b -> c -> a por alguma rua ser contra-mão.
Mais uma característica interessante que pode ser explicada nesse exemplo é o de peso das arestas: podem existir vários caminhos diferntes de A para B, digamos:
A->B;
A->C->B;
A->D->C->B.
Consideremos que o peso nesse caso é o tempo que leva para ir do ponto A para o ponto B. a rua (aresta) de A->B (o caminho direto) pode estar constantemente engarrafada, portanto o tempo (peso) dessa aresta é 30 (minutos, por exemplo).A aresta A->C possui peso 10, e cada aresta desse grafo com os vértices A, B, C e D desse exemplo tem seus pesos como segue:
A->B = 30
A->C = 10
C->B = 15
A->D = 8
D->C = 10.
Com esses pesos não é difícil concluir que o menor caminho é o segundo, pois levará 25 minutos, enquanto o primeiro leva 30 e o terceiro 28. O peso pode estar associado a muitas outras coisas, como a quantidade de gasolina gasta, o número de vezes que é passada a marcha, enfim, depende unicamente do que se pretende avaliar.
No caso das redes sociais o peso entre quaisquer arestas é 1, assim pode ser avaliada a distância que uma pessoa está de outra.
Existem vários algoritmos usados para manipular grafos. Esses algoritmos basicamente caminham por um grafo usando as arestas como “ruas” nesse caminho, portanto só é possível chegar de um vértice a outro a partir de algum caminho, se for sempre possível chegar de algum vértice a qualquer outro seguindo alguma sequência de arestas o grafo é chamado conexo, caso contrário ele é desconexo. Pra quem usa orkut há muito tempo, uma coisa interessante que existia antes é que só era possível ser membro da rede social através de um convite. Ao aceitar esse convite e se tornar membro, o novo usuário automaticamente se tornava amigo de quem o convidou. Isso fazia com que o orkut fosse um grafo conexo, ou seja, sempre haverá algum caminho para chegar de um usuário a outro, por maior que seja. Falando nisso, um dos principais tipos de algoritmos usado em grafos trata do caminho mínimo entre dois vértices, ou seja, qual o melhor modo de chegar a um vértice partindo de outro? Na wikipedia alguns algoritmos são descritos, vale a pena olhar. Talvez eu fale sobre algum(ns) deles em outro post.
Há um tempo o orkut mostrava um caminho entre você e alguém que você estava visitando, mesmo que esse alguém não fosse amigo de um amigo seu. Para mostrar isso era usado algum algoritmo de caminho mínimo, verificando qual o número de vértices mínimo que era preciso passar para chegar ao vértice (usuário) que estava sendo visitado.
Claro que os algoritmos de grafos não se restringem a ruas e redes sociais, alias, existem muito mais aplicações para grafos do que se possa imaginar, dois exemplos que eu acho muito interessantes são o de redes e páginas web:
Como todos devem saber, a Internet é basicamente uma rede de redes de computadores, todas conectadas entre si. Por si só isso já mostra que ela pode ser enxergada como um grafo, onde cada vértice é um roteador – vale lembrar que o roteador é o dispositivo responsável por rotear pacotes na rede, enviando pacotes de uma subrede para outra, ou pacotes vindos de uma rede para um computador, ou partindo de um computador para uma rede. Tanto pode ser considerada como é um grafo. Como todas as redes são conectadas de alguma forma, é um grafo conexo. Os roteadores possuem uma fila de pacotes a serem repassados para outras redes, mas existem vários problemas que podem impedir (ou atrasar) a transmissão de pacotes a outros roteadores para chegar ao destinatário final, com isso o as arestas modificam constantemente os pesos (pode ser o tempo de confirmação de envio de pacotes) das arestas (caminhos entre roteadores) e melhor (ou pelo menos um bom) caminho deve ser constantemente recalculado, daí a importância de algoritmos eficientes para que a internet continue funcionando bem.
Fora a infra-estrutura da Internet, as próprias páginas web são um exemplo de grafo. Imagine cada página como um vértice, onde os links são as arestas que ligam cada página com outras. É exatamente assim que as máquinas de busca vêem a web. Para poder fazer buscas em tantas páginas, elas primeiro precisam ser coletadas e, pra isso, navegar pelo máximo de páginas possível, mas não existe uma lista de todas as páginas do mundo, por isso a web poderia modelada, para o coletor, como um grafo que pode ser gerado a partir de uma única página, sendo expandida a várias outras páginas a que são linkadas, mas começar a partir de uma página e percorrer todas as subestruturas de links não significa encontrar todas as páginas que existem na web. Imagine, por exemplo, um blog pessoal. Talvez hajam links para outros blogs que linkem para o primeiro, gerando um ciclo de amigos, mas se nenhum deles estiver sendo ligado por algum outro site de fora, serão apenas um subgrafo desconexo do resto. Grafo desconexo – essa é a melhor forma de definir o grafo das páginas web, pois ela é cheia de páginas ou conjunto de páginas (subgrafos) que não se conectam ao resto. Por isso é preciso uma lista de páginas geradoras a partir das quais o grafo é gerado e será percorrido para que outros algoritmos sejam aplicados, como o pagerank, por exemplo.
Existem muitas outras aplicações interessantes e algoritmos para tratamento de grafos, mas acho que essa foi uma introdução razoável 
by offsFX
English 
Português 