Matriz de adyacencia de un grafo

La matriz de adyacencia de un Grafo $G=(V,E)$ con $V=\{v_1,v_2,\dots ,v_N\}$ es una matriz $\Gamma \in {\mathbb{R}}^{N\times N}$ donde cada elemento $[\Gamma {]}_{ij}$ se define como:

$$[\Gamma {]}_{ij}=\{\begin{array}{ll}1& \text{si }\{v_i,v_j\}\in E,\\ 0& \text{en caso contrario.}\end{array}$$

Observe que la matriz de adyacencia es simétrica para grafos no dirigidos.

En el caso de Grafos ponderados, la matriz de adyacencia especifica el peso de la arista, i.e.

$$[\Gamma {]}_{ij}=\{\begin{array}{ll}\varphi (\{v_i,v_j\})& \text{si }\{v_i,v_j\}\in E,\\ 0& \text{en caso contrario.}\end{array}$$

donde $\varphi :E\to \mathbb{R}$ es la función de peso.

notación-elemento-de-matriz