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 1.