|
Cones and polytopes of geleralized metrics
E. I. Deza Moscow State Pedagogical University (Moscow)
Abstract:
In this paper the problems of construction and research of cones and polytopes of generalized metric structures are considered: finite quasisemimetrics, which
are oriented analogs of classical — symmetric — case of semimetrics, and finite $m$-semimetrics, which are multidimensional analogs of classical — two-dimensional — case of semimetrics.
In the introduction the background of the research is considered, examples of use of metrics, quasimetrics and $m$-metrics in Mathematics and in Applications are given, a review of main ideas and results presented in the article is represented.
In the first section definitions of main generalized metric structures considered in the paper are given: finite metrics and semimetrics, their oriented analogs — finite quasimetrics and quasisemimetrics, and their multidimensional analogs — finite $m$-metrics and $m$-semimetrics.
In the second section classical examples of the corresponding generalized metric structures are given. The concept of a metric is shown by four basic examples (discrete metric — Hausdorff metric — symmetric difference metric — path metric of connected graphs). For the oriended case four corresponding quasimetrics are presented, while for the multidimensional case four corresponding $m$-metrics are constructed.
In the third section an interesting example of a special case of quasimetrics is reviewed: the mean first passage time for Markov's chains. During the analysis of properties of this special structure its connections with weightable quasimetrics, partial metrics and other, rather exotic, metric structures are shown.
In the fourth section the most important special cases of semimetrics are considered: cuts and multicuts. Their oriented and multidimensional analogs are constructed: oriented cuts,
oriented multicuts and also partition $m$-semimetrics.
In the fifth section creation of cones and polytopes of the considered generalized metric structures is carried out. Metric and cut cones and polytopes on $n$ points are considered. The oriented and multidimensional analogs of these cones and polytopes are constructed. The properties of these classes of generalized discrete metric structures are marked out.
Special attention is paid
to the questions of symmetries of the constructed objects. Results of the calculations devoted to cones of semimetrics, cuts, quasisemimetrics, oriented cuts and multicuts, $m$-semimetrics and partition $m$-semimetrics on small number of points (3, 4, 5 and 6 points) are presented. In fact, the dimension of an object, the number of its extreme rays (vertices)
and their orbits, the number of its facets and their orbits, the diameters of the
skeleton and the the ridge graph of the constructed cones and polyhedrons are
specified.
In the conclusion the main research results are presented.
Keywords:
Semimetric, cut, multicut, cones and polytopes of semimetrics and cuts, quasisemimetric, oriented cut and multicut, cones and polytopes of quasisemimetrics, oriented cuts and multicuts, $m$-semimetric, partition $m$-semimetric, cones and polytopes of $m$-semimetrics and partition $m$-semimetrics.
Received: 28.05.2019 Accepted: 12.07.2019
Citation:
E. I. Deza, “Cones and polytopes of geleralized metrics”, Chebyshevskii Sb., 20:2 (2019), 140–155
Linking options:
https://www.mathnet.ru/eng/cheb758 https://www.mathnet.ru/eng/cheb/v20/i2/p140
|
Statistics & downloads: |
Abstract page: | 146 | Full-text PDF : | 117 | References: | 15 |
|