Matriz de Adyacencia

Un grafo se puede representar mediante una matriz. Es la forma más sencilla de representar un grafo. A esta matriz se le denomina matriz de adyacencia.

Esta matriz consiste en un arreglo bidimensional de tamaño “n”, donde “n” es la máxima cantidad de nodos en el grafo. Cada casilla de la matriz se carga con valores verdadero “V” o falso “F” en caso de que posea un camino de un nodo o fila con columna. En caso de los grafos no dirigidos la matriz será simétrica.

Esto no ocurre en los dígrafos, donde se considera la dirección de cada uno de los arcos. Para el caso de los grafos ponderados, la matriz podrá ser cargada con el peso asociado a cada uno de los arcos.

La ventaja principal es su simplicidad, dado que facilita las operaciones que puedan realizarse sobre el grafo. La desventaja es que se limita a un número máximo de nodos en el grafo, lo que provoca que sea imposible almacenar más información en la matriz.

Si la matriz es muy grande para representar un grafo pequeño, se desperdicia el espacio de almacenamiento de la matriz y de la memoria. Para un grafo no dirigido, el desperdicio será mayor porque al ser simétrica la matriz, su información se duplicaría.

Grafo representado por la matriz de adyacencia

En esta figura se muestra un grafo representado mediante una matriz de adyacencia. Se observa que cada camino une dos nodos.

Ejemplo: de “A” hacia “C” existe un camino por lo que el valor de la casilla es “V” (verdadero), de la misma forma de “A” hacia “B” no existe un camino, por lo que el valor de la casilla de la matriz es “F” (falso).

Ejemplo de Matriz de Adyacencia

Para hacer la matriz de adyacencia a un grafo se debe sacar lo siguientes grafos:

· La matriz de adyacencia para el Grafo A:

Comprobaremos cada elemento de la matriz Aij (i=Fila j=Columna)

A11 ¿arista del v1 al v1? Si existiese pondríamos 2 ya que sería un bucle pero como no es el caso 0.

A12 ¿arista del v1 al v2? Si, ¿cuántas? 1

A13 ¿arista del v1 al v3? Si, ¿cuántas? 1

Y así lo haremos con cada fila y con cada columna quedando la matriz así:

| 0 1 1 |

| 1 0 0 |

| 1 0 2 |

Al tratarse de un grafo no dirigido obtenemos una matriz simétrica, por lo que si usamos cada fila o cada columna obtendremos el grado de cada vértice.

· La matriz de adyacencia para el Grafo B:

Se comprueba exactamente igual que el grafo A, con la diferencia que los arcos tienen una dirección. El resultado es:

| 0 0 1 |

| 1 0 0 |

| 0 0 1 |

Al tratarse de un grafo dirigido si sumamos las columnas obtenemos el grado de entrada y si sumamos las filas el grado de salida.

• Otro Ejemplo de una Matriz de Adyacencia