A Teoria dos Grafos, um ramo da matemática e também da computação, serve de base para a Ciência das Redes, por isso é importante entender um pouco desta teoria para conhecer os principais termos empregados nesta área, tais como: nós, enlaces, caminhos, distância etc.
Se você cursa ou cursou um bacharelado na área de informática/computação, você certamente já teve uma introdução formal ao tema e estes conceitos abaixo lhe serão familiares. Se você nunca ouviu falar disso, espero que esta introdução lhe ajude. Para entendê-la, você deve apenas conhecer estruturas matemáticas discretas como conjuntos e tuplas.
Você acha que falarmos de redes usando matemática é um rigor desnecessário? Se sim, encare a matemática como uma língua, similar ao português ou inglês, mas com uma propriedade especial: é livre de dubiedades. Em outras palavras, a linguagem matemática nos permite comunicar ideias de forma clara (e concisa), bastando que você conheça o vocabulário dela.
Voltemos aos grafos. Formalmente, um grafo é uma dupla cujo primeiro elemento é o conjunto de nós (conjunto $N$) e o segundo o conjunto de enlaces (conjunto $E$), os quais conectam dois nós. Portanto, todo enlace é também uma dupla $(i,j)$ onde $i \in N$ e $j \in N$. Comumente, representamos a quantidade de nós em um grafo por $n$ e a quantidade de enlaces por $m$. Os nós (nodes, em inglês) também podem ser chamados de vértices (vertex) enquanto os enlaces (links) são também chamados arestas (edges).
Um exemplo de um grafo seria definido por $G=(N,E)$, onde $N=\{0,1,2,3,4,5,6,7,8,9\}$ e $E=\{(0,1),(0,2),(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,5),(4,6),(5,6),(5,7),(6,7),(6,8),(7,8),(7,9),(8,9),(8,0),(9,0),(9,1)\}$. Neste grafo temos que $n=10$ e $m = 20$. A partir desta definição, podemos traçar a representação pictórica que comumente encontramos, como mostrado abaixo.
Grafos podem ser dirigidos ou não dirigidos. O que muda em cada tipo é a ausência ou presença de sentido nas arestas do grafo. Em grafos dirigidos, também chamados digrafos, temos que os enlaces $(i,j)$ e $(j,i)$ são distintos, os quais são representados pictoricamente como setas que partem do nó à esquerda da tupla e chegam no nó à direita da tupla. Já em grafos não dirigidos temos que $(i,j) = (j,i)$. Os enlaces representados na figura acima são todos não dirigidos.
O uso de um ou outro tipo de grafo na modelagem de um sistema complexo depende de qual propriedade deste sistema queremos representar. Podemos encontrar exemplos destes tipos na modelagem de redes sociais. Associações do tipo seguidor/seguido, como nos perfis do Twitter ou canais no Youtube, são representadas por enlaces dirigidos. Já associações de amizade, como em perfis do Facebook, são representadas por enlaces não-dirigidos.
Podemos, a título de exemplo, definir um digrafo $D=(N,E)$, onde $N=\{0,1,2,3,4,5,6,7,8,9\}$ e $E=\{(0,1),(0,2),(1,2),(1,3),(2,3),(2,4),(3,4),(3,5),(4,5),(4,6),(5,6),(5,7),(6,7),(6,8),(7,8),(7,9),(8,9),(8,0),(9,0),(9,1)\}$. Neste grafo temos que $n=10$ e $m = 20$. Observe que toda a definição é a mesma usada para o G e o que muda é a interpretação que damos para a estrutura. Abaixo temos a representação gráfica deste digrafo.
Representação do grafo direcionado D
No contexto da ciência das Redes, uma rede será como um grafo, com nós e arestas interligando-os, mas com a diferença de que a rede é dinâmica, ou seja, a rede se modifica com o passar do tempo, adicionando e removendo nós e arestas. Desta forma, os grafos passam a ser como que uma visão instantânea de uma rede em um dado instante do tempo.
O formalismo dos grafos é usado na modelagem de redes complexas em diversos contextos como ciências sociais, física, matemática, etc. O que os torna tão versáteis é a generalidade para representação entre objetos e suas relações. Portanto, a teoria dos grafos nos dá o ferramental necessário para modelagem das redes complexas.
Em outros posts veremos algumas propriedades dos grafos, também chamadas de métricas, que são úteis para estudar as redes complexas.
Comentários
Postar um comentário