Adjacency matrix

Adjacency matrix — матрица смежности.

The adjacency matrix [math]\displaystyle{ \,A(G) }[/math] of a graph [math]\displaystyle{ \,G = (V,E) }[/math] and an ordering [math]\displaystyle{ (v_{1}, \ldots, v_{n}) }[/math] of [math]\displaystyle{ \,V }[/math] is the [math]\displaystyle{ \,(0,1) }[/math]-matrix [math]\displaystyle{ \,(a_{ij}) }[/math] defined by

[math]\displaystyle{ a_{ij} = \left \{\begin{array}{l} 1, \mbox{ if } (v_{i}, v_{j}) \in E \\ 0, \mbox{ otherwise} \end{array} \right. }[/math]

Adjacency matrices are very handy when dealing with path problems in graphs. Nodes [math]\displaystyle{ \,i,j }[/math] are connected by a path (chain) of length [math]\displaystyle{ \,k }[/math] if and only if [math]\displaystyle{ \,A^{k}(i,j) = 1 }[/math].

Another its name is Neighborhood matrix.

The augmented adjacency matrix is formed by setting all values [math]\displaystyle{ \,a_{ii} }[/math] in the adjacency matrix to [math]\displaystyle{ \,1 }[/math].