Matriz de caminhos

Nós já falamos anteriormente sobre caminhos na rede, agora veremos uma matriz que armazena os menores entre todos os pares de nós na rede, que é chamada matriz de caminhos.

O fato de ser uma matriz nos recorda da matriz de adjacência, porém a matriz de caminhos $P=[p_{ij}]_{n \times m}$ difere da matriz de adjacência  porque cada elemento $p_{ij}$ indica o tamanho do menor caminho entre os nós $i$ e $j$. 

Tal como vimos com a matriz de adjacência, em grafos não-dirigidos a matriz de caminhos também será simétrica e em digrafos a matriz de caminhos é geralmente assimétrica. As posições $p_{ii}$ são sempre $0$ e as posições $p_{ij}$ armazenam o tamanho do menor caminho conhecido. Caso não haja um caminho no grafo entre os nós $i$ e $j$, então $p_{ij}=\infty$. Note que nos referimos a existência de um caminho, não um enlace direto.

Considere o grafo $G$ com 4 nós a seguir.

Grafo $G$ de exemplo com 4 nós

A matriz de caminhos $P_G$ deste grafo é dada por

$P_G =\begin{bmatrix} 0 & 1 & 2 & 1 \\ 1 & 0 & 1 & 1 \\ 2 & 1 & 0 & 2 \\ 1 & 1 & 2 & 0 \end{bmatrix}$

A matriz de caminhos está relacionada com a matriz de adjacência pela fórmula $P = \min_{k=1..D}\{kA^k\}$, onde $D$ é o diâmetro da matriz, $A^k$ é a matriz de adjacência contendo os pares de nós que estão $k$ saltos distantes e a função $\min$ seleciona os menores elementos em cada posição. Deve-se notar que a matriz $A^k$ é obtida por $A^{(k-1)} \times A$ e zerando a diagonal principal da matriz obtida.

Considerando ainda o exemplo anterior temos que $A_G$ é a matriz de adjacência de $G$, assim

$A_G = \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 \end{bmatrix}$

Portanto fazendo $A^2_G$, zerando a diagonal principal e multiplicando por $k=2$ temos que

$2A^2_G = \begin{bmatrix} 0 & 2 & 2 & 2 \\ 2 & 0 & 0 & 2 \\ 2 & 0 & 0 & 2 \\ 2 & 2 & 2 & 0 \end{bmatrix}$

Como o diâmetro neste grafo é $D=2$, nós encontramos todos os caminhos de tamanho 1,...,D. O próximo passo combina as matrizes encontradas selecionando o menor elemento não-zero de cada posição, $P_G = \min_{k=1,2}\{kA^k_G\}=\min\{A_G,2A^2_G\}$. Assim temos que:

$P_G = \begin{bmatrix} 0 & 1 & 2 & 1 \\ 1 & 0 & 1 & 1 \\ 2 & 1 & 0 & 2 \\ 1 & 1 & 2 & 0 \end{bmatrix}$

A matriz de caminhos pode ser útil para ter uma visão compacta da rede. Em certas redes, padrões de regularidade são facilmente identificáveis por meio da matriz de caminhos.