Grafos y matrices

Grafos

Con esta definición y con el ejemplo anterior, podemos decir que la Fig. 1 es la representación de un grafo en el que cada punto representa un vértice y cada una de las aristas representa la conexión entre dos vértices.

Fig. 1. Representación de un grafo.

Matriz de adyacencia

El grafo es, entonces, una representación gráfica de la información. Pero, con una imagen no podemos hacer cálculos para obtener información precisa, ni calcular otros datos. Para poder hacer esto, se crea la llamada matriz de adyacencia.

Esta matriz es una representación numérica del grafo con la cual podemos hacer operaciones y obtener más datos.

Si queremos obtener la matriz de adyacencia del grafo anterior, ordenamos los vértices en las filas y las columnas de una matriz que será de dimensión \(n\times n\), siendo \(n\) el número de vértices en el grafo.

\[\begin{array}\, \space\space\space\space\space\space\space\space\space\space&A&B&C&D&E&F\end{array}\]

\[M=\begin{array}\,A\\B\\C\\D\\E\\F\end{array}\begin{pmatrix}\,&\space\space\space&\space\space&\space\space&\space\space&\space\space\space\space\space\space\space\\&&&&&\\&&&&&\\&&&&&\\&&&&&\\&&&&&\end{pmatrix}\]

A continuación, rellenamos la matriz siguiendo los siguientes pasos:

1. La completamos, elemento a elemento, empezando por el de la primera fila con la primera columna; es decir, el elemento \(a_{11}\). Esto es, si entre el vértice \(A\) y el vértice \(A\) hay alguna conexión (arista).

2. Si hay una conexión, se pone un \(1\).

3. Si no hay ninguna conexión, se pone un \(0\). En este caso, no hay ninguna conexión que lleve del vértice A de vuelta al mismo vértice, por lo que en el elemento \(a_{11}\) de la matriz pondríamos un \(0\).

Matriz de adyacencia de un grafo dirigido

También podemos tener un grafo en el que las artistas estén dirigidas; es decir, que tengan una flecha que indica el sentido de la conexión, tal como se observa en la Fig. 2. A este tipo de grafo se le denomina gafo dirigido.

Fig. 2. Grafo dirigido.

La manera de obtener la matriz de adyacencia de este grafo es similar a la del primer caso. La única diferencia es que ahora la arista solo cuenta cuando va de un vértice a otro en el sentido de la flecha, no en ambos sentidos. Por tanto, de \(A\) a \(D\) habría una conexión o arista y el elemento de matriz sería un \(1\). Sin embargo, de \(D\) a \(A\) no hay ninguna conexión o arista y el elemento de matriz sería \(0\). De este modo, podemos rellenar la matriz de adyacencia completa de este grafo dirigido:

\[\begin{array}\,\space\space\space\space\space\space\space\space\space&A&B&C&D&E&F\end{array}\]

\[M=\begin{array}\,A\\B\\C\\D\\E\\F\end{array}\begin{pmatrix}\,0\space&1\space&1\space&1\space&0\space&0\space\\1&0&0&1&0&0\\0&0&0&0&0&1\\0&0&1&0&1&1\\0&1&0&1&0&0\\0&0&0&0&0&0\end{pmatrix}\]

Esta sería la matriz de adyacencia del grafo de la Fig. 2. Si denominamos a esta matriz como \(M\), esta da cuenta de los caminos que hay para llegar a un vértice desde otro.

Pero, ahora vamos a calcular \(M^2\):

\[M^2=\begin{pmatrix}\,1&0&1&1&1&2\\0&1&2&1&1&1\\0&0&0&0&0&0\\0&1&0&1&0&1\\1&0&1&1&1&1\\0&0&0&0&0&0\end{pmatrix}\]

Si te fijas bien, la interpretación de esta matriz es el número de caminos que llegan del vértice \(i\) al vértice \(j\), haciendo una escala.

Por ejemplo, hay un solo camino para ir de \(A\) a \(A\) haciendo una escala, y este es ir de \(A\) a \(B\) y luego de \(B\) a \(A\).

Si un elemento es un \(2\), quiere decir que existen dos caminos posibles para ir de un vértice a otro, haciendo una escala.

Por último, si sumásemos la matriz \(M\) a \(M^2\), tendríamos el número total de caminos para ir de un vértice a otro, haciendo una escala o yendo directamente.

Como ves, esto tiene muchas aplicaciones en diversos campos científicos.

Matriz de incidencia de un grafo

La matriz de incidencia de un grafo es similar a la matriz de adyacencia, en el sentido en que también muestra las relaciones entre vértices; pero, en este caso, se tienen en cuenta las aristas. Como ejemplo, vamos a usar el grafo de la Fig. 1. Para ello, primero nombramos las aristas como en la Fig. 3.

Para formar esta matriz, en las filas estarán los vértices y en las columnas las aristas. El elemento de matriz será un \(1\), cuando el vértice que corresponde a la fila está conectado a la arista que corresponde a la columna.

Ahora, formamos la matriz de filas y columnas, tal como hemos explicado:

\[I=\begin{pmatrix}\,1&1&1&0&0&0&0&0&0&0\\0&1&0&1&0&1&1&0&0&0\\1&0&0&0&1&0&0&1&0&0\\0&0&1&0&1&1&0&0&0&1\\0&0&0&0&0&0&1&0&1&1\\0&0&0&0&0&0&0&1&1&0\end{pmatrix}\]

Esta sería la matriz de incidencia del grafo representado en la Fig. 3.

Tipos de grafos

Los grafos se pueden dividir en dos grandes grupos:

• Grafos no dirigidos.

• Grafos dirigidos.

Estos dos tipos de grafos ya los hemos visto en los ejemplos anteriores. Así que ya entiendes en qué se parecen y en qué se diferencian cada uno. Además, en función de las características del grafo, también hay otras clasificaciones:

• Grafo simple: es un grafo en el que siempre se da que una única arista une dos vértices.

• Multigrafo: al contrario que un grafo simple, en los multigrafos varias aristas pueden unir los mismos dos vértices.

• Grafo conexo.

• Grafo completo.

• Grafo bipartito.

• Etc.

Como puedes ver, hay muchos tipos de grafos según sus características.

Aplicaciones de grafos

Los grafos son objetos que se pueden aplicar a muchas ramas científicas, como la sociometría, la antropología, la comunicación, la geografía, las redes sociales, entre muchas otras.

Por ejemplo, los grafos son un recurso que se utiliza para crear las líneas de transporte público, como autobuses y trenes. En los planos, cada estación se trata como un vértice y cada vía entre estaciones es una arista. Además, cada arista puede recibir una ponderación o peso; es decir, un número que denota una cantidad, como puede ser la distancia.

Esto lo utilizan las aplicaciones de mapas para crear rutas entre dos estaciones, contando con el número de estaciones (vértices) y la distancia entre las mismas (aristas ponderadas). Así crean la mejor ruta, adaptada a las necesidades del usuario (menor tiempo, menor número de estaciones, menor número de transbordos, etc.).