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.