Matriz de adyacencia de un grafo

|

Todo grafo simple puede ser representado por una matriz, que llamamos matriz de adyacencia.

Se trata de una matriz cuadrada de n filas \times n columnas (siendo n el número de vértices del grafo).

Para construir la matriz de adyacencia, cada elemento a_{ij} vale 1 cuando haya una arista que una los vértices i y j. En caso contrario el elemento a_{ij} vale 0.

La matriz de adyacencia, por tanto, estará formada por ceros y unos.

Ejemplo 1

Vamos a construir la matriz de adyacencia del siguiente grafo:

– Como tiene 5 vértices, será una matriz de 5 filas x 5 columnas
\left( \begin{array}{ccccc} X & X & X & X & X \\X & X & X & X & X \\X & X & X & X & X \\X & X & X & X & X \\X & X & X & X & X \end{array} \right)

Completamos la primera fila (la del 1). El 1 sólo está conectado al 2 y al 4, por tanto ponemos un 1 en las columnas 2 y 4 y un 0 en las demás:
\left( \begin{array}{ccccc} 0 & 1 & 0 & 1 & 0 \\_ & _ & _ & _ & _ \\_ & _ & _ & _ & _ \\_ & _ & _ & _ & _ \\_ & _ & _ & _ & _ \end{array} \right)

Procedemos de igual forma con el resto de filas y ya tenemos la matriz de adyacencia:

\left( \begin{array}{ccccc} 0 & 1 & 0 & 1 & 0 \\1 & 0 & 1 & 0 & 1 \\0 & 1 & 0 & 1 & 0 \\1 & 0 & 1 & 0 & 0 \\0 & 1 & 0 & 0 & 0 \end{array} \right)

En la siguiente imagen podemos ver las conexiones entre el 1 y el 4

Matriz de adyacencia de un grafo
Matriz de adyacencia de un grafo