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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''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>.

Версия от 11:52, 8 ноября 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 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].