Adjacency matrix: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Нет описания правки
Нет описания правки
 
Строка 11: Строка 11:
if and only if <math>\,A^{k}(i,j) = 1</math>.
if and only if <math>\,A^{k}(i,j) = 1</math>.


Another its name is '''[[Neighborhood matrix]]'''.
Another its name is '''[[Neighbourhood matrix]]'''.


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

Текущая версия от 16:41, 10 ноября 2011

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 Neighbourhood 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].