Si tenemos un grafo $G=(V,E)$ donde $V=\{v_1,…,v_n\}$, llamamos matriz de adyacencia del grafo a la matriz cuadrada nxn, $A=[a_{ij}]$, donde
$$a_{ij}=\left\{\begin{matrix}1 & \mbox{si } \{v_i,v_j\}\in E\\ 0 & \mbox{si } \{v_i,v_j\}\not\in E\end{matrix}\right.$$
En caso de que hubiera un bucle en $v_i$ $a_{ii}=1$. Si es el multigrafo $a_{ij}$ seríe en número de arcos que conecten los vértices.
La matriz de adyacencia de un grafo es simétrica, pues la arista une dos vértices independiente del comienzo y el final, pero si el grafo es un digrafo entonces los arcos sólo van en una dirección y $a_{ij}$ no tiene por qué coincidir con $a_{ji}$.
Del mismo modo podemos construir la matriz de incidencia, donde las columnas de la matriz representan las aristas del grafo y las filas representan a los distintos nodos. Por cada nodo unido por una arista, ponemos un uno 1 en el lugar correspondiente, y llenamos el resto de las ubicaciones con ceros 0. Un lazo cuenta doble. Si es un digrafo atenderemos como 1 si es un vertice de salida y -1 si es de entrada.
Terminamos viendo propiedades de estas matrices.
Ejercicio: Determinar la matriz de adyacencia y de incidencia del grafo |