Introdução a Teoria dos Grafos

Antes de mais nada, vamos tentar entender o que é um grafo. Um grafo é uma estrutura matemática usada para representar as relações entre as coisas. Imagine:

  • Um mapa rodoviário: nele, as cidades se relacionam entre si através das várias estradas.
  • Um sistema de distribuição de água: nele, as casas se relacionam entre si (e entre as centrais de distribuição) através dos canos de água. Esse exemplo também vale para distribuição de energia (casas/postes), de gás (casas/canos), etc.
  • A hierarquia de uma empresa: nela, os funcionarios se relacionam entre si através da relação "é chefe de". Podemos desenhar então aquelas hierarquias, com o presidente no topo (pois é chefe de todo mundo) e os estagiários lá no fim (pois não mandam em ninguém).
  • O relacionamento social entre pessoas: nele, as pessoas se interligam entre si atráves da amizade. Se A é amigo de B e B é amigo de C, indiretamente, A está "conectado" a C. O Orkut é um exemplo de rede de amigos que, no fim das contas, é um grafo. Você possui amigos e está "conectado" a eles. Estes, eventualmente estão conectados a outras pessoas. Já notou quando você entra no perfil de alguém que você não conhece (diretamente) e o Orkut mostra um "caminho" de pessoas, de você até aquela pessoa? Aquilo é um clássico problema de grafos! Devemos partir de uma pessoa (você) e, percorrendo seus relacionamentos, encontrar um "caminho" até outra pessoa.

Essas "coisas" que se relacionam entre si são chamados de nós do grafo. Cada relacionamento entre os nós é chamado de aresta. Normalmente, para facilitar sua visualização e sua compreensão, grafos são representados graficamente. Atenção! Não confunda as duas palavras! Grafos são entidades matemáticas, abstratas, que possuem nós (coisas) e arestas (relacionamento entre essas coisas). Gráficos são imagens. Grafos podem ser representados graficamente, mas o grafo não é a sua representação gráfica - existem várias outras maneiras de representar grafos que não graficamente. Para acabar com essa bagunça toda, vamos dar uma olhada em um grafo.

Grafo.png

A partir da imagem acima já podemos perceber algumas coisas: geralmente, em sua representação gráfica, os nós são representados por círculos e as arestas por linhas que conectam esses círculos. Outro detalhe interessante é que os nós da figura acima tem números dentro deles. Esses números servem somente para distinguir os nós - na verdade, podem representar os números das casas no sistema de distribuição de água, poderia ser o nome da cidade no mapa, etc. Para tentar deixar ainda mais claro, dêem uma olhada em outros exemplos de grafos encontrados em nosso cotidiano:

Dá para perceber a partir de todos esses exemplos que o conceito de grafos é bastante abrangente - podemos representar muitas coisas do mundo (e suas relações) utilizando esse conceito. É isso que torna a teoria dos grafos um campo tão estudado: as pessoas se debruçam para estudar esse modelo matemático (o modelo abstrato, não aplicado a um caso especifico como rede de energia, gás ou mapas de cidades) porque sabem que, se conseguirem desenvolver novos trabalhos em cima desse modelo abstrato, esses trabalhos serão aplicáveis a inúmeros problemas reais. Imagine que você conseguiu desenvolver um trabalho muito bom sobre, digamos, aumentar o fluxo entre dois nós de um grafo. Esse seu trabalho poderá ser aplicado desde redes de água (aumentando o fluxo de água) até redes de computadores (aumentando o fluxo de dados transmitidos). A isso se dá o nome de "modelar" o problema: "Modelei meu problema em um grafo".

Nesse ponto, acho que só é necessário apresentar mais um conceito para que o problema da AGM possa ser compreendido: arestas podem estar associadas a valores, comumente denominado pesos. Em um mapa de estradas, por exemplo, esse valor pode representar o comprimento das rodovias (a distância entre as cidades). Em uma rede de distribuição de água, pode representar o quanto de água é possível levar de um ponto a outro. Em uma rede social (de amigos), pode representar o "peso" da relação - conhecido, amigo, muito amigo, etc. Enfim, dependendo do que estamos querendo modelar, esse valor associado as arestas pode representar diversas coisas: custos, confiabilidade, lucro, vazão, entre outros. Grafos que possuem pesos associados as arestas são chamados também de redes.

Essa foram somente algumas definições iniciais de teoria dos grafos. Não preciso nem dizer que esse é um campo vastíssimo, que eu nunca conseguiria cobrir com apenas alguns parágrafos. Tentei explicar só o suficiente para que você consiga compreender os problemas que abordo em minhas pesquisas (árvore geradora mínima multi-objetivo e problema quadrático de alocação multi-objetivo). Se quiser mais informações sobre grafos, a Wikipédia é sempre um bom ponto de partida.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-Share Alike 2.5 License.