4625
правок
Adjacency matrix: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Создана новая страница размером '''Adjacency matrix''' --- матрица смежности. The '''adjacency matrix''' <math>A(G)</math> of a graph <math>G = (V,E)</...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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>. | ||