Adjacency matrix

Материал из WikiGrapp
Перейти к:навигация, поиск

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

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

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

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

Another its name is Neighbourhood matrix.

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