Sabemos que a área da informática é intimamente ligada à matemática. Tanto que em cursos de engenharia da computação, por exemplo, encontramos diversas disciplinas da área em sua grade. Poderíamos citar diversas características de matemática que vemos em informática, como: lógica em algoritmos, probabilidade na análise de entrada de dados, geometria em computação gráfica e cálculo em nanotecnologia. Mas uma bem interessante que vemos em estrutura de dados e que tem suas raízes em matemática é a área dos modelos de reprodução de dados. É a base de estrutura de dados e muitas vezes é o ponto determinante para se resolver problemas específicos em sistemas.

Nesse artigo, falarei de um dos mais extensos modelos de dados e que tem diversas aplicabilidades práticas e também estudos teóricos e livros
publicados sobre o assunto… São os grafos. Muitas faculdades têm disciplinas especificas sobre teoria dos grafos, outras os estudam dentro
de disciplinas como estrutura de dados ou algoritmos.

Como um exemplo, imagine o seguinte problema: um usuário de uma loja quer saber que rota seguir do ponto X, que pode ser sua casa ou algum lugar em que estiver acessando o site, até o ponto Y, que é a loja mais próxima, sendo que quer pegar a rota mais curta possível.

Outro exemplo seria o seguinte: estamos construindo uma cidade nova em algum lugar antes inabitado e queremos fazer de forma que tenhamos o
maior número de ruas com sentido único possível. O problema é saber quais ruas podem ter mão-única e para que sentido apontarão, mantendo todas as ruas alcançáveis de qualquer outro ponto na cidade.

Esses dois exemplos acima são bem interessantes e nos dão uma base de onde podemos aplicar grafos. Claro que a teoria  dos grafos é bem mais ampla, mas como idéia base e para nossa modelagem, já são ótimos exemplos.

Como podemos ver nos exemplos, grafos são modelos de dados que armazenam e facilitam na manipulação, estruturas com características de ligações entre pontos. Para armazenar esses modelos podemos utilizar duas estruturas de dados: vetores e listas encadeadas. Algumas vezes as listas são mais rápidas em questão de acesso, mas na maioria dos casos é mais fácil  de se fazer utilizando os vetores, ainda mais quando a maioria dos artigos com algoritmos específicos dão exemplos com vetores.

Para transpor o problema para modelo matemático, precisamos entender algumas terminologias. Com o exemplo simples de um ponto A se conectar com B, e B se conectar com A, já podemos dizer que temos um grafo. Dizemos que o grafo possui dois vértices (A e B) e uma aresta, que é representada pela ligação entre A e B. Na verdade, como estamos direcionando os pontos, estamos falando de uma subdivisão dos grafos chamado digrafo, que significa grafos direcionados. Assim, o ponto A poderia ligar-se com B, mas B poderia não se ligar com A. Grafos são sempre bidirecionais, ou seja, se A->B, então B->A, sempre. Mas vou continuar tratando por grafos ambos os casos, pois a diferença é apenas essa.

Agora que temos o conceito de vértice e aresta, podemos definir o conceito de adjacência e custo.

Quando dizemos A->B,  B->C,  C->A, temos:

• o ponto A é adjacente ao ponto B, mas o ponto B não é adjacente ao ponto A;
• o ponto B é adjacente ao ponto C, mas o ponto C não é adjacente ao ponto B;
• o ponto C é adjacente ao ponto A, mas o ponto A não é adjacente ao ponto C.

Dizer que o ponto A não é adjacente ao ponto C, não que dizer que A não alcance C, pois o A poderia passar por B para chegar em C.

Para terminar vou explicar os custos… Imagine o cenário seguinte, duas ligações saindo de A, e uma saindo de B, mas com valores: A->(2)->B, A->(5)->C, B->(1)->C.

Queremos ir de A a C. Vemos que conseguiríamos chegar até C diretamente (A é adjacente ao ponto C), ou poderíamos passar por B e depois seguir para C. Os custos servem para dar pesos às arestas, ou seja, ir diretamente de A a C, custaria 5, mas poderíamos escolher a rota auxiliar passando por B  que custaria 2+1 (A->B->C): 3.

Esse tema é uma ótima leitura para aqueles que gostam de desafios, ainda mais nos dias atuais, onde a web liga cada vez mais computadores, pesquisas sobre DNA estão cada vez mais avançadas e redes sociais cada vez com mais usuários… Ops! Esses três tópicos também são ligados com a teoria dos grafos!