Decomposition dimension

Материал из WikiGrapp

Decomposition dimension --- декомпозитная размерность.

A decomposition [math]\displaystyle{ {\mathcal F} = \{F_{1}, \ldots, F_{r}\} }[/math] of the edge set of a graph [math]\displaystyle{ G }[/math] is called a resolving [math]\displaystyle{ r }[/math]-decomposition, if for any pair of edes [math]\displaystyle{ e_{1} }[/math] and [math]\displaystyle{ e_{2} }[/math] there exists an index [math]\displaystyle{ i }[/math] such that [math]\displaystyle{ d(e_{1},F_{i}) \neq d(e_{2},F_{i}) }[/math], where [math]\displaystyle{ d(e,F) }[/math] denotes the distance from [math]\displaystyle{ e }[/math] to [math]\displaystyle{ F }[/math]. The decomposition dimension [math]\displaystyle{ dec(G) }[/math] of a graph [math]\displaystyle{ G }[/math] is the least integer [math]\displaystyle{ r }[/math] such that there exists a resolving [math]\displaystyle{ r }[/math]-decomposition.

See also

  • Metric dimension.