Representación de grafos

Existen múltiples formas de representar grafos en la computadora. En particular, vamos a ver tres de ellas: la lista de aristas, la lista de adyacencias y la matriz de adyacencias.

Una lista de aristas consiste en un array de vectores de dos dimensiones, donde cada vector representa una arista del grafo. Por ejemplo, el grafo:

flowchart LR

id1((1))
id2((2))
id3((3))
id4((4))
id5((5))
id6((6))

id1 --- id4
id4 --- id2
id4 --- id5
id5 --- id2
id5 --- id6

Podríamos representarlo como ${(6, 5), (5, 2), (2, 4), (5, 4), (4, 1)}$ . Normalmente esta va a ser la única representación con la que se van a expresar los input de grafos.

Si junto con la lista se pasa el tamaño del grafo, como por convención las etiquetas de los vértices están numeradas podemos deducir qué vértices no tienen vecinos.

Por otro lado, la lista de adyacencia es un vector donde cada elemento es una lista de tamaño $d (v)$ conteniendo los nodos vecinos de dicho elemento. Para representar el grafo dibujado antes, podríamos hacer una lista tal que:

\begin{aligned} 1 & : 4 \\ 2 & : 4 \to 5 \\ 3 & : \\ 4 & : 5 \to 1 \to 2 \\ 5 & : 2 \to 6 \to 4 \\ 6 & : 5 \end{aligned}

Esta es una forma de escribir la lista de adyacencia, ya que podríamos ordenarla de distintas formas. Las listas dentro del vector, podrían ser arrays convencionales, o listas enlazadas, o quizás nos interese mantener el orden entre los nodos. Eso ya dependerá del contexto.

Finalmente, tenemos la matriz de adyacencia. Consiste en una matriz de tamaño $n \times n$ , donde $M_{j i} = 1$ , si los vértices $i$ y $j$ son adyacentes, y $0$ cuando no. En base al grafo dibujado antes, podríamos hacer la siguiente matriz:

(\begin{matrix} 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 1 & 0 \end{matrix})

Esta representación podría optimizarse de muchas formas. Para empezar, podemos notar que la matriz se encuentra espejada. Esto sucede porque en la definición de grafo se cumple que $(v, u) = (u, v)$ , por lo que podríamos utilizar solo uno de los lados que divide la diagonal de la matriz. Y hablando de la diagonal, esta siempre va a contener 0's, ya que dentro de la definición de grafo no puede existir un vértice $(u, u)$ , salvo que hablemos de un pseudografo.

Para aprovechar al máximo la matriz de adyacencia tendríamos que estar hablando de un dígrafo, y donde se permitan los nodos conectados así mismos.

Las distintas complejidades de cada operación según la representación usada se pueden ver comparadas en la siguiente tabla:

	Lista de aristas	Lista de adyacencias	Matriz de adyacencias
Construcción	$O (m)$	$O (n + m)$	$O (n^{2})$
Adyacentes	$O (m)$	$O (d (v))$	$O (1)$
Vecinos	$O (m)$	$O (d (v))$	$O (n)$
agregar arista	$O (m)$	$O (d (u) + d (v))$	$O (1)$
remover arista	$O (m)$	$O (d (u) + d (v))$	$O (1)$
agregar vértice	$O (1)$	$O (n)$	$O (n^{2})$
remover vértice	$O (m)$	$O (n + m)$	$O (n^{2})$

Como el tamaño del grafo está dado por su cantidad de nodos y aristas, una complejidad

O (n + m)

es lineal respecto al tamaño del grafo.