Nós já mostramos que uma rede pode ser representada por conjuntos de nós e arestas, onde cada aresta se apresenta na forma de uma dupla contendo os nós origem e destino. Porém, existe outra forma de representar um grafo e suas conexões denominada matriz de adjacência.
Nesta forma de representação, o enlace entre cada par de nós $(i,j)$ é representado pela posição $a_{ij}$ na matriz $A=[a_{ij}]_{n \times n}$ (lembre-se que usamos $n$ para indicar o número de nós). Se existe uma aresta entre os nós $i$ e $j$, então $a_{ij}=1$. Caso contrário, $a_{ij}=0$.
Matrizes de adjacência de digrafos são, em geral, assimétricas, enquanto que em grafos não dirigidos as matrizes são sempre simétricas (i.e., a matriz de adjacência é igual a sua transposta). Abaixo vemos a matriz G para um grafo estrela e a matriz D de um digrafo estrela, cada um com 6 nós.
$G =\begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 \end{bmatrix} D =\begin{bmatrix} 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end{bmatrix}$
Olhar os grafos como matrizes é uma estratégia interessante, pois permite usar toda o ferramental matemático já existente para tratar de grafos. Usando Álgebra Linear, por exemplo, podemos encarar a matriz $A$ como a matriz dos coeficientes de um sistema linear dinâmico que, a depender de $A$ (i.e., da estrutura da rede), determina se processos dinâmicos na rede são estáveis ou não.
Uma medida muito usada para o estudo de processos dinâmicos em redes complexas é o raio espectral, que é o maior dos autovalores absolutos de $A$. Este valor pode determinar por exemplo se um processo de infecção de uma doença persiste em uma rede ao longo do tempo, ou se ele termina naturalmente.
Este é apenas um exemplo da importância desta representação. Para finalizar, deve-se saber ainda que na matriz de adjacência as posições $a_{ii}$ são geralmente 0, para indicar que um nó não possui enlace para si mesmo. Porém existem certos tipos de sistemas complexos onde um nó pode ter enlaces para ele mesmo, como ocorre em redes metabólicas, por exemplo.
No caso de enlaces para si mesmo, a mudança na matriz é sutil, apenas fazendo $a_{ii}=1$ para todo $i$ onde haja um enlace deste tipo. Contudo, existem outros tipos de grafos (que podem ser usados para representar redes complexas) onde a matriz de adjacência vai ser diferente do que mostramos aqui. Este é o caso dos chamados Multigrafos, onde dois vértices podem ter mais de uma aresta entre si e dos Hipergrafos, onde uma aresta conecta mais de dois nós simultaneamente.
Contudo, somente com os grafos comuns já podemos fazer muitos estudos. Ficaremos com eles (por enquanto).
Comentários
Postar um comentário