Preview

Чебышевский сборник

Расширенный поиск

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

https://doi.org/10.22405/2226-8383-2015-16-2-79-92

Полный текст:

Аннотация

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

 

Об авторах

М. М. Деза
Ecole Normale Superieure
Франция


Е. И. Деза
Московский педагогический государственный университет.
Россия


М. Дютур Сикирич

Хорватия


Список литературы

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.


Для цитирования:


Деза М.М., Деза Е.И., Дютур Сикирич М. ПОЛИЭДРАЛЬНЫЕ КОНСТРУКЦИИ, СВЯЗАННЫЕ С КВАЗИ-МЕТРИКАМИ. Чебышевский сборник. 2015;16(2):79-92. https://doi.org/10.22405/2226-8383-2015-16-2-79-92

For citation:


Deza M.M., Deza E.I., Dutour Sikiri´c M. POLYHEDRAL STRUCTURES ASSOCIATED WITH QUASI-METRICS. Chebyshevskii Sbornik. 2015;16(2):79-92. (In Russ.) https://doi.org/10.22405/2226-8383-2015-16-2-79-92

Просмотров: 76


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)