Аноним

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

Материал из WEGA
нет описания правки
(Создана новая страница размером '''Adjacency matrix''' --- матрица смежности. The '''adjacency matrix''' <math>A(G)</math> of a graph <math>G = (V,E)</...)
 
Нет описания правки
Строка 1: Строка 1:
'''Adjacency matrix''' ---  матрица смежности.  
'''Adjacency matrix''' — ''[[матрица смежности]].''


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


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


Adjacency matrices are very handy when dealing with path problems in
Adjacency matrices are very handy when dealing with path problems in
graphs. Nodes <math>i,j</math> are connected by a path (chain) of length <math>k</math>
graphs. [[Node|Nodes]] <math>\,i,j</math> are connected by a path (chain) of length <math>\,k</math>
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 '''[[Neighborhood 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 1.
<math>\,a_{ii}</math> in the adjacency matrix to <math>\,1</math>.