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