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