Matriz de adjacências (1)

Em Matemática, uma matriz é uma entidade constituída por um conjunto bidimensional de valores arrumados num número finito de linhas e colunas, sendo Aij o valor que se encontra na linha i e na coluna j.
Uma rede ou um grafo com N vértices podem ser representados por uma matriz quadrada com N linhas e N colunas, significando Aij = 1 que existe um lado orientado do vértice i para o vértice j e Aij = 0 que não existe.
Pegando nesta rede, por exemplo

percebe-se facilmente a sua relação com esta matriz 6x6

Esta matriz diz-se a matriz de adjacências da rede em causa. Assinala os vértices que são adjacentes. Se a matriz é simétrica relativamente à sua diagonal então os lados são simétricos (sem direcção).
Por outro lado, esta representação suporta lados múltiplos e mesmo anéis (lados que ligam um nó a ele próprio).

Passeios, trilhos e caminhos

Um passeio (walk) num grafo é uma sucessão de lados adjacentes (com um vértice comum), sem qualquer outra restrição. É o que fazemos quando passeamos numa cidade, em que podemos repetir ruas, esquinas, etc.
Um trilho (trail) é um passeio em nenhum lado é percorrido mais que uma vez. Num passeio citadino, seria aquele que não passa duas vezes pela mesma rua.
Um caminho (path) é um passeio que não passa duas vezes pelo mesmo nó. Acharíamos estranho se alguém nos indicasse um caminho para um determinado ponto numa cidade que passasse duas vezes pela mesma esquina.
O caminho mais curto entre dois pontos é um caminho geodésico, e o seu comprimento é a distância entre os dois pontos.
Um circuito é um caminho fechado, que se inicia e termina no mesmo nó ou vértice.

Nesta rede, por exemplo, temos
 - um passeio: 1 - 2 - 3 - 4 - 2 - 1
 - um trilho: 1 - 2 - 3 - 4 - 6 - 2
 - um caminho: 1 - 2 - 3 - 4 - 5
 - um caminho geodésico: 1 - 6 - 5
 - um circuito: 1 - 2 - 4 - 6 - 1.

Vértices e arestas, nós e lados, actores e interacções

Uma rede é um conjunto de vértices, nós, actores, entre os quais estão definidos arestas, lados, relações, interacções. Esta multiplicidade de nomes tem a ver com a riqueza de situações em que o paradigma da rede se verifica.
Formalmente, uma rede é constituída por um conjunto não vazio de vértices V e um conjunto de arestas E.

Nesta rede muito simples
     V = {1, 2, 3, 4, 5}
     E = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 4), (4, 5)}.
Cada aresta é um par ordenado de dois vértices, a origem e o destino da relação ou interacção.
Podemos facilmente imaginar relações em que se (i, j) constituem uma aresta, então (j, i) também. São relações bidireccionais, ou não direccionadas. A relação de amizade no Facebook, ou uma rua com os dois sentidos de circulação, são relações bidireccionais. Seguir alguém no Twitter, passar uma bola num jogo de futebol, não são.
Numa rede, podem coexistir relações dos dois tipos
     V = {1, 2, 3, 4, 5}
     E = {(1, 2), (1, 3), (2, 3), (2, 4), (3, 2), (3, 4), (4, 5), (5, 4)}.

Quando numa rede todas as relações são não direccionadas, e desde que tal seja claro, podemos omitir as setas com a indicação da direcção da relação na figura que a representa.