Metric dimension

Metric dimension --- метрическая размерность.

Let [math]\displaystyle{ G }[/math] be a graph. For a pair of vertices [math]\displaystyle{ v_{1} }[/math] and [math]\displaystyle{ v_{2} }[/math] of [math]\displaystyle{ G }[/math], let [math]\displaystyle{ d(v_{1},v_{2}) }[/math] denote the length of a shortest path from [math]\displaystyle{ v_{1} }[/math] to [math]\displaystyle{ v_{2} }[/math]. A vertex set [math]\displaystyle{ S \subset V(G) }[/math] is called a metric basis of [math]\displaystyle{ G }[/math] if for any pair of vertices [math]\displaystyle{ x,y }[/math] of [math]\displaystyle{ G }[/math], there exists a vertex [math]\displaystyle{ v \in S }[/math] such that [math]\displaystyle{ d(x,v) \neq d(y,v) }[/math]. The metric dimension [math]\displaystyle{ \beta(G) }[/math] is the cardinality of a smallest metric basis of [math]\displaystyle{ G }[/math]. See also Decomposition dimension.