Chebyshevskii Sbornik
 RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Chebyshevskii Sb.: Year: Volume: Issue: Page: Find

 Chebyshevskii Sb., 2019, Volume 20, Issue 2, Pages 140–155 (Mi cheb758)

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.

DOI: https://doi.org/10.22405/2226-8383-2018-20-2-140-155

Full text: PDF file (631 kB)
References: PDF file   HTML file

UDC: 519.1
Accepted:12.07.2019

Citation: E. I. Deza, “Cones and polytopes of geleralized metrics”, Chebyshevskii Sb., 20:2 (2019), 140–155

Citation in format AMSBIB
\Bibitem{Dez19} \by E.~I.~Deza \paper Cones and polytopes of geleralized metrics \jour Chebyshevskii Sb. \yr 2019 \vol 20 \issue 2 \pages 140--155 \mathnet{http://mi.mathnet.ru/cheb758} \crossref{https://doi.org/10.22405/2226-8383-2018-20-2-140-155}