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 filas $\times$ columnas (siendo 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 y . 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 ). El sólo está conectado al y al , por tanto ponemos un en las columnas y y un 0 en las demás:
$\left( \begin{array}{ccccc} 0 & 1 & 0 & 1 & 0 \\_ & _ & _ & _ & _ \\_ & _ & _ & _ & _ \\_ & _ & _ & _ & _ \\_ & _ & _ & _ & _ \end{array} \right)$