A figura 1 mostra um diagrama que representa três empresas e o tempo, em horas, para ir de uma empresa a outra. O diagrama indica, por exemplo, que para ir da empresa 1 até a empresa 3 (ou ir da empresa 3 até a empresa 1) o tempo necessário é de 2 horas.
Esse diagrama pode ser representado na forma de uma matriz A de ordem 3, pois são três empresas, em que cada elemento aij representa o tempo, em horas, para ir da empresa i até a empresa j. A matriz A, chamada matriz de adjacência, que representa o diagrama da figura 1 é:
!$ A = \begin{bmatrix} 0 & 0 & 2 \\ 0 & 0 & 5 \\ 2 & 5 & 0 \end{bmatrix} !$
Observe que, quando não existe indicação de tempo entre duas empresas, os elementos da matriz que representam essas duas empresas são iguais a zero. Observe também que aij = 0 sempre que i = j.
Considere o diagrama da figura 2, que representa 7 empresas.
Uma das linhas da matriz de adjacência que representa o diagrama da figura 2 é
