In the thesis, the problem of search of metric dimension for finite ultrametric spaces and for some finite metric spaces constructions is described. The thesis considers the problem of finding the metric dimension for finite ultrametric spaces, as well as for some constructions of metric spaces with finiteness conditions.
The Definition of the metric dimension for metric spaces was firstly introduced by Blumenthal in 1953. 20 years later Harari and Melter in their paper applied it to the metric spaces defined on graphs. After that, the metric dimension concept found a range of applications, like in combinatorial analysis, robotics, biology, chemistry, etc.
In 2013 S. Bau and F. Beardon proceeded with the research of Blumenthal's ideas about the metric spaces metric dimension. They have calculated 6 the metric dimension of the k-dimensional sphere in Euclidean space. Later, M. Heydarpour and S. Maghsoudi calculated the metric dimensions of geometric spaces.
It is known, that finding the metric dimension of a metric space is an NP-hard problem. This is why there are several ways of conducting metric dimension research. One of those is researching the metric dimension of some specific families of metric spaces or graphs. Second one - research constructions of metric spaces, which is being created using metric spaces for which metric dimension is known.
In thesis research is being conducted in both ways. Namely, the metric dimension of ultrametric spaces is completely characterized. It is shown that for an arbitrary finite ultrametric space its metric dimension can be found in polynomial time. To do this, it was shown that the tree image of ultrametric space can be constructed by O(n 5 ), where n - the number of points of ultrametric space. It is also shown that the metric dimension of the ultrametric space defined on the rooted tree is either equal to the metric dimension of this tree as a graph, or is lesser by one. The paper fully characterizes ultrametric spaces whose metric dimension is equal to one.
In addition to ultrametric spaces, the thesis considers the metric dimension of different constructions of metric spaces. In particular, it is shown that for an arbitrary transform scale the metric dimension of the metric space and its metric transform coincide
It is shown that isomorphic spaces have the same metric dimensions. A formula for calculating the metric dimension is given for the wreath product of finite metric space and uniformly discrete space. Besides, for the direct sum of metric spaces of finite diameter, it is shown that its 7 metric dimension will be equal to the sum of the metric dimensions of these spaces. All direct sums whose metric dimension is equal to two are characterized. The last section also considers the metric dimension of the direct product of equidistant metric spaces with d1, d2 òà d∞ metrics.It is shown that although these metrics are topologically equivalent, the corresponding metric spaces have different metric dimensions.
Thus, the thesis contains the following new scientific results: 1.The algorithm of constructing isometric tree to the ultrametric space by a rooted tree with time complexity O(n 5 ) is given. 2. For an arbitrary finite ultrametric space, it is shown that there is a polynomial algorithm for calculating its metric dimension. 3. All ultrametric spaces whose dimension is equal to one are characterized. 4. The metric dimension of the metric transform of the metric space is described. 5. The metric dimension of the wreath product of a finite metric space and uniformly discrete metric space is described. 6. The metric dimension of the direct sum of metric spaces of finite diameter is described. 7. Describes the metric dimension of the direct product of equidistant metric spaces with metrics d1, d2 and d∞.
The practical significance of the results. The results of this work are mainly theoretical. They can be used in graph theory, robotics, theory of metric spaces. The thesis can be used for lecturing special courses of the graph theory for students learning at mathematical specialties.
Key words: metric space, ultrametric space, metric basis, metric dimension, rooted tree, time complexity, polynomial algorithm.
