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:

;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 ;

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 → s_2 → 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:

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

Así podemos ver como el elemento a_21 representa la conexión s_2 → s_1, y el a_51 la s_5 → s_1, etc.

En general, a_ij representa una conexión de s_i → s_j siempre que a_ij ≥ 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:

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

Podemos interpretar esta matriz como los caminos de orden dos.

¿Pero qué representa el elemento a_52 = 2? Indica que hay dos posibles caminos para ir de s_5 → s_i → 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 ≥ 1 son s_1 y s_4. Es decir, se puede ir de s_5 a s_2 o bien mediante s_5 → s_1 → s_2 ó bien s_5 → s_4 → s_2:

Es importante notar que en los gráfos no se consideran lazos, es decir, s_i → 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:

1 ; 1 ; 0 ; 1 ; 0 1 ; 2 ;1; 0 ; 1 1 ; 0 ; 0 ; 1 ; 1 1 ; 2 ; 1 ; 1 ; 0 2 ; 0 ; 0 ; 1 ; 2

Podemos ver como ha aparecido el primer 1 en a_23, 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:

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

Sigue sin haber una conexión entre s_1 y s_3. Calculando A^4:

1 ; 2 ;1;; ;;;; ;;;; ;;;; ;;;;

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.






Parece que tu navegador no vas a poder probar el ejemplo en tu navegador :(