chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2015-16-2-79-92cheb-169Research ArticleСтатьиArticleПОЛИЭДРАЛЬНЫЕ КОНСТРУКЦИИ, СВЯЗАННЫЕ С КВАЗИ-МЕТРИКАМИPOLYHEDRAL STRUCTURES ASSOCIATED WITH QUASI-METRICSДезаМ. М.DezaM. M.

M. Dutour Sikiri´c (Zagreb, Croatia)

ДезаЕ. И.DezaE. I.Дютур СикиричМ.Dutour Sikiri´cM.Ecole Normale SuperieureFranceМосковский педагогический государственный университет.Russian Federation2015040720161627992Copyright © Деза М.М., Деза Е.И., Дютур Сикирич М., 20162016Деза М.М., Деза Е.И., Дютур Сикирич М.Deza M.M., Deza E.I., Dutour Sikiri´c M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/169

В данной работе рассмотрены проблемы, связанные с построением и исследованием конусов и многогранников конечных квази-метрик, кото­ рые являются несимметричными аналогами классических метрик. Во введении рассмотрена история вопроса, приведены примеры ис­ пользования метрик и квазиметрик в математике и ее приложениях, в том числе задачи, связанные с проблемой максимального разреза. В первом разделе даны определения конечных метрики и полуметри­ ки, а также их важнейших частных случаев: разреза, мультиразреза и гиперсемиметрики; построены конусы и многогранники указанных объек­ тов; исследованы их свойства. Рассмотрены связи конуса разрезов с мет­ рическими l1-пространствами. Особое внимание уделено симметриям по­ строенных конусов, которые состоят из перестановок и так называемых свичингов; именно преобразование свичинга служит основанием для вы­ бора неравенств, определяющих соответствующий многогранник. Во втором разделе рассмотрены конечные квази-метрики и квази-по­ луметрики, которые являются несимметричным аналогом конечных ме­ тик и полуметрик; даны определения ориентированного разреза и ориен­ тированного мультиразреза — важнейших частных случаев квази-полу­ метрики; введены понятия взвешиваемой квази-метрики и родственной ей частичной метрики; построены конусы и многогранники указанных объектов; исследованы их свойства. Рассмотрены связи ориентированных разрезов с кази-метрическим l1-пространством. Особое внимание уделено симметриям построенных конусов, которые состоят из перестановок и ори­ ентированных свичингов; как и в симметричном случае, преобразование ориентированного свичинга служит основанием для выбора неравенств, определяющих соответствующий многогранник. Рассмотрены резные под­ ходы к построению конуса и многогранника несимметричных гиперполу­ метрик. В последнем разделе представлены результаты вычислений, посвящен­ ных конусам и многогранникам квази-полуметрик, ориентированных раз­ резов, ориентировнных мультиразрезов, взвешиваемых квази-метрик и ча­ стичных метрик на 3, 4, 5 и 6 точках. Указаны размерность объекта, число экстремальных лучей (вершин) и их орбит, число гиперграней и их орбит, диаметры скелетона и реберного графа построенных конусов и многогран­ников.

 

In this paper the problems of construction and description of cones and polyhedra of finite quasi-metrics are considered. These objects are asymmetrical analogs of classical finite metrics. The introduction presents the historical background and examples of applications of metrics and quasi-metrics. In particular, the questions connected with maximum cut problem are represented. In the first section definitions of finite metrics and semi-metrics are given, and also their major special cases are considered: cuts, muluticuts and hypersemimetrics. Cones and polyhedrons of the specified objects are constructed; their properties are investigated. Connections of the cut cone with metric l1-spaces are indicated. The special attention is paid to symmetries of the constructed cones which consist of permutations and so-called switchings; transformation of a switching serves the basis for a choice of the inequalities defining the corresponding polyhedron. In the second section finite quasi-metrics and quasi-semimetrics are considered. They are asymmetrical analogs of the usual finite metrics and semimetrics. Definition of the oriented cuts and oriented multicuts are given: they are the most important special cases of the quasi-semimetrics. Concept of weightable quasi-metrics and related to them partial metrics is introduced. Cones and polyhedrons of these objects are constructed; their properties are investigated. Connections of the oriented cut cone with quasi-metric l1-space are considered. The special attention is paid to symmetries of the constructed cones, which consist of permutations and oriented switchings; as well as in symmetric case, transformation of the oriented switching serves the basis for a choice of the inequalities defining the corresponding polyhedron. Different approaches to creation of a cone and a polyhedron of asymmetrical hypersemimetrics are considered. In the last section results of the calculations devoted to cones and to polyhedrons of quasi-semimetrics, the oriented cuts, the oriented multicuts, weighed quasimetrics and partial metrics for 3, 4, 5 and 6 points are considered. 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.

 

Полуметрикаразрези мультиразрезгиперполумет рикаконусы и многогранники полуметрикразрезов и гиперполуметрикквази-полуметрикаориентрованные разрез и мультиразрезвзвешиваемая метрикачастичная метрикаконусы квази-полуметрикориентированных разрезов и мультиразрезоввзвешиваемых и частичных метрикмногогранники квази-полуметрикориентированных разрезов и мульти­ разрезоввзвешиваемых и частичных метрикSemi-metricscut and multicuthypersemimetriccones and polyhedra of semimetricscuts and hypersemimetricsquasi-semimetricsoriented cut and multicutweightable metricpartial metriccones of quasisemimetricsof oriented cuts and oriented multicutsof weightable and partial metricspolyhedra of quasi-semimetricsof oriented cuts and multicutsof weightable and partial metricsReferencesCharikar M., Makarychev K., Makarychev V. Directed metrics and directed graph partitioning problem // Proc. of 11-th ACM-SIAM Symposium on Discrete Algorithms. 2006. P. 51–60.Charikar M., Makarychev K., Makarychev V. Directed metrics and directed graph partitioning problem // Proc. of 11-th ACM-SIAM Symposium on Discrete Algorithms. 2006. P. 51–60.Deza M. M., Deza E. I. Encyclopedia of Distances / 3-rd edition. Berlin: SpringerVerlag, 2014. 716 p.Deza M. M., Deza E. I. Encyclopedia of Distances / 3-rd edition. Berlin: SpringerVerlag, 2014. 716 p.Deza M. M., Deza E. I. Cones of partial metrics // Contrib. Discrete Math. 2011. № 6(1). P. 26–47.Deza M. M., Deza E. I. Cones of partial metrics // Contrib. Discrete Math. 2011. № 6(1). P. 26–47.Deza M. M., Deza E. I., Vidali J. Cones of weighted and partial metrics // Proceedings of the International Conference on Algebra 2010. NJ: World Sci. Publ., 2012. P. 177– 197.Deza M. M., Deza E. I., Vidali J. Cones of weighted and partial metrics // Proceedings of the International Conference on Algebra 2010. NJ: World Sci. Publ., 2012. P. 177– 197.Deza M. M., Dutour Sikiri´c M. The hypermetric cone on 8 vertices and some generalizations // Preprint at arxiv:arXiv:1503.04554. 2013. Aviable at: http://arxiv.org/abs/ 1503.04554.Deza M. M., Dutour Sikiri´c M. The hypermetric cone on 8 vertices and some generalizations // Preprint at arxiv:arXiv:1503.04554. 2013. Aviable at: http://arxiv.org/abs/ 1503.04554.Deza M. M., Dutour M., Panteleeva E. I. Small cones of oriented semi-metrics // Forum for Interdisciplinary Mathematics Proceedings on Statistics, Combinatorics & Related Areas. 2002. Vol. 22. P. 199–225.Deza M. M., Dutour M., Panteleeva E. I. Small cones of oriented semi-metrics // Forum for Interdisciplinary Mathematics Proceedings on Statistics, Combinatorics & Related Areas. 2002. Vol. 22. P. 199–225.Deza M. M., Grishukhin V. P., Deza E. I. Cones of weighted quasi-metrics, weighted quasi-hypermetrics and of oriented cuts // Mathematics of Distances and Applications. Sofia: ITHEA, 2012. Р. 31–53.Deza M. M., Grishukhin V. P., Deza E. I. Cones of weighted quasi-metrics, weighted quasi-hypermetrics and of oriented cuts // Mathematics of Distances and Applications. Sofia: ITHEA, 2012. Р. 31–53.Deza M. M., Laurent M. Geometry of cuts and metrics. Berlin: Springer-Verlag, 1997. 517 c.Deza M. M., Laurent M. Geometry of cuts and metrics. Berlin: Springer-Verlag, 1997. 517 c.Deza M. M., Panteleeva E. I. Quasi-semi-metrics, oriented multi-cuts and related polyhedra // European Journal of Combinatorics. 2000. № 21(6). P. 777–795.Deza M. M., Panteleeva E. I. Quasi-semi-metrics, oriented multi-cuts and related polyhedra // European Journal of Combinatorics. 2000. № 21(6). P. 777–795.Fr´echet M. Sur quelques points du calcul fonctionnel // Rend. Circolo mat. Palermo. 1906. Vol. 22. PP. 1–74.Fr´echet M. Sur quelques points du calcul fonctionnel // Rend. Circolo mat. Palermo. 1906. Vol. 22. PP. 1–74.Hausdorff F. Grundz¨uge der Mengenlehre. Leipzig, 1914.Hausdorff F. Grundz¨uge der Mengenlehre. Leipzig, 1914.Hitzler P. Generalized Metrics and Topology in Loic Programming Semantics // PhD Thesis. National University of Ireland: Univ. College Cork, 2001.Hitzler P. Generalized Metrics and Topology in Loic Programming Semantics // PhD Thesis. National University of Ireland: Univ. College Cork, 2001.Matthews S. G. Partial metric topology (Papers on general topology and applications (Flushing, NY, 1992)) // Ann. New York Acad. Sci. 1994. Vol. 728. P. 183–197.Matthews S. G. Partial metric topology (Papers on general topology and applications (Flushing, NY, 1992)) // Ann. New York Acad. Sci. 1994. Vol. 728. P. 183–197.Seda A. K. Quasi-metrics and the semantic of logic programs // Fundamenta Informaticae. 1997. Vol. 9. P. 97–117.Seda A. K. Quasi-metrics and the semantic of logic programs // Fundamenta Informaticae. 1997. Vol. 9. P. 97–117.Wilson W. A. On quasi-metric spaces // American J. of Math. 1931. Vol. 53. P. 575– 681.Wilson W. A. On quasi-metric spaces // American J. of Math. 1931. Vol. 53. P. 575– 681.

The authors declare that there are no conflicts of interest present.