Cinco ciudades están comunicadas por líneas de autobús y ferrocarril como indican los grafos siguientes [ 1 ]:
Éstos son grafos no dirigidos pues las líneas que unen las ciudades se pueden recorrer en ambos sentidos. La información que contiene cada uno de los grafos puede representarse mediante una matriz llamada matriz de adyacencia. Para las rutas por autobús: $$\begin{matrix} & & \text{hasta} & \\[1.2ex] & & \begin{matrix} \quad a & b & c & d & e & \end{matrix} \\[1.2ex] \text{desde } & \begin{matrix} a \\ b \\ c \\ d \\ e \end{matrix} & \left ( \begin{matrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{matrix} \right ) &= \bf B \end{matrix}$$ donde un \(1\) representa que las ciudades están conectadas directamente por autobús y un \(0\) indica ausencia de enlace. La matriz \(\bf B\) es simétrica, \({\bf B}^T = \bf B\), debido a que la conexión entre dos ciudades existe en ambos sentidos. Los elementos de la diagonal principal \(\; b_{ii} \;\) con \(\; i=1,\dotsc,5\;\) deben ser \(0\) ya que no se considera comunicada una ciudad consigo misma.
El grafo sería dirigido si alguna conexión solo existiera en uno de los dos sentidos, lo que se indicaría con una punta de flecha en la conexión, la matriz de adyacencia perdería su simetría y tendría más sentido distinguir que las filas de esta matriz representan los servicios de autobús que salen desde una ciudad hacia las otras, y que las columnas indican los autobuses que llegan a una ciudad desde las otras. Esta forma de interpretar la matriz se utilizará más adelante.
De la misma forma se puede construir la matriz de adyacencia para la red ferroviaria: $$\begin{matrix} & & \text{hasta} & \\[1.2ex] & & \begin{matrix} \quad a & b & c & d & e & \end{matrix} \\[1.2ex] \text{desde } & \begin{matrix} a \\ b \\ c \\ d \\ e \end{matrix} & \left ( \begin{matrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{matrix} \right ) &= \bf F \end{matrix}$$
La ciudad mejor comunicada
¿Qué hay si superponemos los dos grafos? 
Es la red de comunicaciones entre las cinco ciudades. Contando el número de conexiones entre ciudades, sin distinguir el medio de transporte, obtenemos la siguiente matriz: $$\begin{matrix} & & \text{hasta} & \\[1.2ex] & & \begin{matrix} \quad a & b & c & d & e & \end{matrix} \\[1.2ex] \text{desde } & \begin{matrix} a \\ b \\ c \\ d \\ e \end{matrix} & \left ( \begin{matrix} 0 & 1 & 2 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 2 & 1 & 0 & 1 & 2 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 2 & 1 & 0 \end{matrix} \right ) &= \bf C \end{matrix}$$
Esta información la obtenemos de las matrices de adyacencia de las redes de transporte. Si observamos lo que ha ocurrido, vemos que un elemento de la matriz \(\bf C\) se obtiene sumando los términos que ocupan las mismas posiciones en las dos matrices de adyacencia, es decir: \(\; c_{ij}=b_{ij} + f_{ij} \;\) para \(\; i,j=1,\dotsc,5 \;\), así \(\bf C\) es la matriz suma: $$\begin{align} \bf C &= \bf B + \bf F \\[1.2ex] &= \left ( \begin{matrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \\ \end{matrix} \right ) + \left ( \begin{matrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ \end{matrix} \right ) \\[1.2ex] &= \left ( \begin{matrix} 0 & 1 & 2 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 \\ 2 & 1 & 0 & 1 & 2 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 2 & 1 & 0 \\ \end{matrix} \right )\end{align}$$
La calidad de la comunicación la medimos por el número de conexiones en la red. Este número se obtiene por suma de las columnas de la matriz de comunicaciones. Si consideramos la matriz \({\bf u}^T = \begin{pmatrix} 1 & 1 & 1 & 1 & 1 \end{pmatrix}\) el producto $${\bf C} \cdot {\bf u} = \begin{pmatrix} 3 \\ 3 \\ 6 \\ 3 \\ 3 \end{pmatrix}$$ presenta a la ciudad (c) superando a las demás con \(6\) conexiones. Siendo más rigurosos, este valor sería el número de conexiones salientes desde la ciudad (c). El número de conexiones entrantes lo daría el producto \({\bf u}^T \cdot {\bf C} \). En nuestro caso los valores coincidirán.
Viajes con una escala
Vamos a ver que también es posible obtener alguna información extra con las matrices de adyacencia \(\bf B\) y \(\bf F\). Hemos planeado realizar un traslado entre dos ciudades haciendo escala en una ciudad intermedia, el primer viaje se hará en tren y el segundo en autobús. Consideremos todas las conexiones de la ciudad (c) por tren con las demás. Extraemos esta información de la tercera fila de la matriz \(\bf F\): $$\left ( \begin{matrix} f_{31} & f_{32} & f_{33} & f_{34} & f_{35} \end{matrix} \right ) = \left ( \begin{matrix} 1 & 1 & 0 & 0 & 1 \end{matrix} \right )$$ Los trayectos en autobús que llegan a cada ciudad están en las columnas de la matriz \(\bf B\). \(\def \boxcyan{\bbox[cyan,5px]} \def \boxyellow{\bbox[yellow,5px]}\)
Desde la ciudad (c) llegar a la ciudad (a): $$\small \begin{align} \left ( \begin{matrix} 1 & \boxcyan 1 & 0 & 0 & 1 \end{matrix} \right ) \left ( \begin{matrix} 0 \\ \boxyellow 1 \\ 1 \\ 0 \\ 0 \end{matrix}\right ) &= 1 \cdot 0 + \underbrace {{\boxcyan 1} \cdot { \boxyellow 1} }_{1}+ 0 \cdot 1 + 0 \cdot 0 + 1 \cdot 0 \\ &= 1 \text{ trayecto.}\end{align}$$
Aparecerá un producto igual a la unidad cuando ambos factores sean \(1\) y esto ocurre cuando provienen de un viaje con escala intermedia como el que buscamos: $$\begin{cases}\boxcyan 1 && \longrightarrow \text{ desde $\bf (c)$ hasta $\bf (b)$ en tren} \\ \boxyellow 1 && \longrightarrow \text{ llega a la ciudad $\bf (a)$ desde $\bf (b)$ en bus} \end{cases}$$
Desde la ciudad (c) llegar a la ciudad (d): $$\small \begin{align} \left ( \begin{matrix} 1 & \boxcyan 1 & 0 & 0 & \boxcyan 1 \end{matrix} \right ) \left ( \begin{matrix} 0 \\ \boxyellow 1 \\ 1 \\ 0 \\ \boxyellow 1 \end{matrix}\right ) &= 1 \cdot 0 + \underbrace {{\boxcyan 1} \cdot {\boxyellow 1}}_{1} + 0 \cdot 1 + 0 \cdot 0 + \underbrace {{\boxcyan 1} \cdot {\boxyellow 1}}_{1} \\ &= 2 \text{ trayectos.} \end{align}$$
Si ampliamos los cálculos para todas las ciudades destino, $$\small \begin{align} \left ( \begin{matrix} 1 & 1 & 0 & 0 & 1 \end{matrix} \right ) \cdot \bf B &= \left ( \begin{matrix} \boxcyan 1 & \boxcyan 1 & 0 & 0 & \boxcyan 1 \end{matrix} \right ) \left ( \begin{matrix} 0 & \boxyellow 1 & \boxyellow 1 & 0 & 0 \\ \boxyellow 1 & 0 & 0 & \boxyellow 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & \boxyellow 1 & \boxyellow 1 & 0 \end{matrix} \right ) \\[1.2ex] &= \left ( \begin{matrix} 1 & 1 & 2 & 2 & 0 \end{matrix} \right ) \end{align}$$
Desde la ciudad (c) no se puede viajar hasta la ciudad (e) con esta modalidad de viaje. Ampliamos el cálculo para todas las ciudades origen, $$\small \begin{align} \bf M \equiv \bf F \cdot \bf B &= \left ( \begin{matrix} 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 \end{matrix} \right ) \cdot \left ( \begin{matrix} 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 0 \end{matrix} \right ) \\[1.2ex] &= \left ( \begin{matrix} 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 2 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 \end{matrix} \right ) \end{align}$$
El elemento \(m_{33}\) es igual a \(2\) lo que significa que hay dos trayectos que parten de la ciudad (c) y regresan a la misma ciudad. Observemos que esta matriz \(\bf M\) ya no es simétrica, por tanto, la lectura de esta matriz hay que hacerla necesariamente como $$\begin{matrix} & & \text{hasta} & \\[1.2ex] & & \begin{matrix} \quad a & b & c & d & e & \end{matrix} \\[1.2ex] \text{desde } & \begin{matrix} a \\ b \\ c \\ d \\ e \end{matrix} & \left ( \begin{matrix} 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 2 & 2 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 \end{matrix} \right ) &= \bf M \end{matrix}$$
Con el mismo razonamiento podemos concluir que si nos trasladásemos primero en autobús y luego en tren, la matriz que contiene el número de trayectos posibles sería \(\bf B \cdot \bf F\). Esta matriz es justamente \({\bf M}^T\). Esto no es una coincidencia ya que, por las características de simetría del problema, $${\bf M}^T = \left ( \bf F \cdot \bf B \right )^T \stackrel {*}{=} {\bf B}^T \cdot {\bf F}^T = \bf B \cdot \bf F$$ (El paso señalado con * es una propiedad de la trasposición sobre el producto de matrices.)
Seguro que nos podemos aventurar a dar una interpretación de la matriz \({\bf B}^2 = \bf B \cdot \bf B\). (Ésta es simétrica.) $${\bf B}^2 = \left ( \begin{matrix} 2 & 0 & 0 & 2 & 1 \\ 0 & 2 & 2 & 0 & 1 \\ 0 & 2 & 3 & 1 & 1 \\ 2 & 0 & 1 & 3 & 1 \\ 1 & 1 & 1 & 1 & 2\end{matrix} \right )$$
[ 1 ] Adaptado de: R. W. Thomas & R. J. Huggett. Modelling in Geography: A Mathematical Approach, Barnes & Noble Books, 1980.