ПОЛИЭДРАЛЬНЫЕ КОНСТРУКЦИИ, СВЯЗАННЫЕ С КВАЗИ-МЕТРИКАМИ

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

1. 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.

2. Deza M. M., Deza E. I. Encyclopedia of Distances / 3-rd edition. Berlin: SpringerVerlag, 2014. 716 p.

3. Deza M. M., Deza E. I. Cones of partial metrics // Contrib. Discrete Math. 2011. № 6(1). P. 26–47.

4. 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.

5. 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.

6. 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.

7. 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.

8. Deza M. M., Laurent M. Geometry of cuts and metrics. Berlin: Springer-Verlag, 1997. 517 c.

9. 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.

10. Fr´echet M. Sur quelques points du calcul fonctionnel // Rend. Circolo mat. Palermo. 1906. Vol. 22. PP. 1–74.

11. Hausdorff F. Grundz¨uge der Mengenlehre. Leipzig, 1914.

12. Hitzler P. Generalized Metrics and Topology in Loic Programming Semantics // PhD Thesis. National University of Ireland: Univ. College Cork, 2001.

13. 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.

14. Seda A. K. Quasi-metrics and the semantic of logic programs // Fundamenta Informaticae. 1997. Vol. 9. P. 97–117.

15. Wilson W. A. On quasi-metric spaces // American J. of Math. 1931. Vol. 53. P. 575– 681.