Grafos
Escrito por
Imanol H.
el 02-06-2017. Última revisión el 02-06-2017
Imaginemos 5 estaciones de autobús, que denotaremos por \(s_i\):
\(\begin{bmatrix} & s_1 & s_2 & s_3 & s_4 & s_5 \\ s_1 & & V & & & \\ s_2 & V & & & & V \\ s_3 & & & & V & \\ s_4 & & V & V & & \\ s_5 & V & & & V & \end{bmatrix}\)Esto se conoce como "cuadro de interconexiones directas".
Las \(V\) representan caminos conectados. Por ejemplo, en la primera fila partiendo de \(s_1\), llegando hasta la \(V\), se nos permite girar hacia arriba para llegar a \(s_2\).
Podemos ver esta misma tabla representada de una manera más gráfica:
Este tipo de gráfica es un grafo, y además dirigido (o digrafo), ya que el sentido en el que van las flechas sí importa. Está compuesto por vértices, unidos entre si por ejes (también llamados aristas o arcos dirigidos).
Se puede ir de un nodo otro mediante distintos caminos o tours. Por ejemplo, \(s_4 \rightarrow s_2 \rightarrow s_5\) es un camino indirecto de orden dos, porque debemos usar dos aristas para ir de \(s_4\) a \(s_5\).
Pasemos ahora a representar la matriz de adyacencia llamada A, que representa el mismo cuadro, pero usa \(1\) en vez de \(V\) para representar una conexión:
\(\begin{bmatrix} 0 & 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \end{bmatrix}\)Así podemos ver como el elemento \(a_{2,1}\) representa la conexión \(s_2 \rightarrow s_1\), y el \(a_{5,1}\) la \(s_5 \rightarrow s_1\), etc.
En general, \(a_ij\) representa una conexión de \(s_i \rightarrow s_j\) siempre que \(a_{i,j} \geq 1\).
Trabajar con matrices nos permite tener una representación computable de un grafo cualquiera, lo cual es realmente útil.
Los grafos tienen muchas más propiedades interesantes a parte de ser representables computacionalmente. ¿Qué ocurre si, por ejemplo, hallamos \(A^2\)? Resulta la siguiente matriz:
\(\begin{bmatrix} 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 \\ 0 & 2 & 1 & 0 & 0 \end{bmatrix}\)Podemos interpretar esta matriz como los caminos de orden dos.
¿Pero qué representa el elemento \(a_{5,2} = 2\)? Indica que hay dos posibles caminos para ir de \(s_5 \rightarrow s_i \rightarrow s_2\)
Es posible realizar la multiplicación de la fila y columna implicadas para ver qué elemento es el que hay que atravesar, así se tiene la fila \([1, 0, 0, 1, 0]\) y la columna \([1, 0, 0, 1, 0]\) (en vertical). Los elementos \(s_1 \geq 1\) son \(s_1\) y \(s_4\). Es decir, se puede ir de \(s_5\) a \(s_2\) o bien mediante \(s_5 \rightarrow s_1 \rightarrow s_2\) ó bien \(s_5 \rightarrow s_4 \rightarrow s_2\):
Es importante notar que en los gráfos no se consideran lazos, es decir, \(s_i \rightarrow s_i\) no está permitido; ni tampoco se trabaja con multigrafos (que permiten muchas conexiones, por ejemplo, de un número arbitrario \(n\) de veces.
Terminemos con \(A^3\):
\(\begin{bmatrix} 1 & 1 & 0 & 1 & 0 \\ 1 & 2 & \textbf{1} & 0 & 1 \\ 1 & 0 & 0 & 1 & 1 \\ 1 & 2 & 1 & 1 & 0 \\ 2 & 0 & 0 & 1 & 2 \end{bmatrix}\)Podemos ver como ha aparecido el primer \(1\) en \(a_{2,3}\), lo que representa que el camino más corto es de al menos de orden tres.
Un grafo es fuertemente conexo siempre que se pueda encontrar una conexión para todos los elementos.
Para ver todos los caminos posibles hasta ahora, basta con sumar las formas directas más las formas indirectas, por lo que hasta ahora podemos sumar \(A + A^2 + A^3\) tal que:
\(\begin{bmatrix} 2 & 2 & 0 & 1 & 1 \\ 3 & 3 & 1 & 1 & 3 \\ 1 & 1 & 1 & 2 & 1 \\ 2 & 3 & 2 & 2 & 1 \\ 3 & 2 & 1 & 2 & 2 \end{bmatrix}\)Sigue sin haber una conexión entre \(s_1\) y \(s_3\). Calculando \(A^4\):
\(\begin{bmatrix} 1 & 2 & 1 & & \\ & & & & \\ & & & & \\ & & & & \\ & & & & \end{bmatrix}\)No hace falta seguir calculando, ya tenemos un grafo totalmente conexo.
¡Felicidades! Has completado esta pequeña introducción a los gráficos. Ahora puedes jugar tú y diseñar tus propias conexiones.
Mantén pulsado el botón izquierdo del ratón en el área de arriba y arrastra hacia abajo para crear un nuevo nodo, o arrastra un nodo a este área para eliminarlo.
Para crear nuevas conexiones, mantén pulsado el botón derecho del ratón en el nodo del que quiera partir, y arrástralo hasta el nodo con el que lo quieras conectar.
Para eliminar las conexiones que salen de un nodo en concreto, haz clic con el botón central del ratón en el nodo que quieras.
|
|
|