danДоклады Национальной академии наук БеларусиDoklady of the National Academy of Sciences of Belarus1561-83232524-2431The Republican Unitary Enterprise Publishing House "Belaruskaya Navuka"dan-324Research ArticleМАТЕМАТИКАMATHEMATICSНЕПЕРЕСЕКАЮЩИЕСЯ КОНФИГУРАЦИИ В ДОПОЛНЕНИЯХ ГЕОМЕТРИЧЕСКИХ ГРАФОВ И ДИЗЪЮНКТНАЯ СОВМЕСТИМОСТЬNON-CROSSING CONFIGURATIONS IN COMPLEMENTS OF GEOMETRIC GRAPHS AND DISJOINT COMPATIBILITYБЕНЕДИКТОВИЧВ. И.BENEDIKTOVICHV. I.vbened@im.bas-net.byИнститут математики НАН БеларусиInstitute of Mathematics of the National Academy of Sciences of Belarus201628102016604816Copyright © БЕНЕДИКТОВИЧ В.И., 20162016БЕНЕДИКТОВИЧ В.И.BENEDIKTOVICH V.I.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://doklady.belnauka.by/jour/article/view/324

В работе для произвольного непересекающегося совершенного паросочетания за время O(n4 log n) строится дизъюнктно совместимое остовное дерево максимальной степени вершин не больше 4. Получен критерий существования непересекающегося совершенного паросочетания в дополнении звезды порядка меньше 2n в K2n. Доказано существование непересекающегося совершенного паросочетания в дополнении дерева порядка (n + 1) в K2n с числом внутренних вершин, не превышающим (n – 1).

In this article, for any non-crossing perfect matching a disjoint compatible spanning tree with a maximum vertex degree no more than 4 is constructed with the complexity O(n4 log n) The criterion of existence of a non-crossing perfect matching in the complement of a star of the order less than 2n in K2n has been obtained. It has been proved that there exists a noncrossing perfect matching in the complement of a tree of the order (n + 1) in K2n with the number of inner vertices no more than (n – 1).

геометрический граф(дизъюнктно) совместимые графыдвойственный мультиграфнепересекающееся совершенное паросочетаниеgeometric graph(disjoint) compatible graphsdual multigraphnon-crossing perfect matchingReferencesIshaque, M. Disjoint compatible geometric matchings / M. Ishaque, D. L. Souvaine, C. D. Tóth // Proceedingsof the 27th Symposium on Computational Geometry (Paris, 2011). – New York, 2011. – P. 125–134.Ishaque, M. Disjoint compatible geometric matchings / M. Ishaque, D. L. Souvaine, C. D. Tóth // Proceedingsof the 27th Symposium on Computational Geometry (Paris, 2011). – New York, 2011. – P. 125–134.Bose, P. Growing a tree from its branches / P. Bose, G. T. Toussaint, // J. Algorithm. – 1995. – Vol. 19, N 1. – P. 86–103.Bose, P. Growing a tree from its branches / P. Bose, G. T. Toussaint, // J. Algorithm. – 1995. – Vol. 19, N 1. – P. 86–103.Bose, P. Every set of disjoint segments admits a binary tree / P. Bose, M. E. Houle, G. T. Toussaint // Discr. Comput. Geom. – 2001. – Vol. 26, N 3. – P. 387–410.Bose, P. Every set of disjoint segments admits a binary tree / P. Bose, M. E. Houle, G. T. Toussaint // Discr. Comput. Geom. – 2001. – Vol. 26, N 3. – P. 387–410.Hoffmann, M. Pointed binary encompassing trees: simple and optimal / M. Hoffmann, C. D. Toth // Comput. Geom. Theor. Appl. – 2010. – Vol. 43, N 1. – P. 35–41.Hoffmann, M. Pointed binary encompassing trees: simple and optimal / M. Hoffmann, C. D. Toth // Comput. Geom. Theor. Appl. – 2010. – Vol. 43, N 1. – P. 35–41.Souvaine, D. L. A vertex- face assignment for plane graphs / D. L. Souvaine, C. D. Tóth, // Comp. Geom. Theor. Appl. – 2009. – Vol. 42, N 5. – P. 388–394.Souvaine, D. L. A vertex- face assignment for plane graphs / D. L. Souvaine, C. D. Tóth, // Comp. Geom. Theor. Appl. – 2009. – Vol. 42, N 5. – P. 388–394.Rappaport, D. Computing simple circuits from a set of line segments is NP-complete / D. Rappaport // SIAM J. Comput. – 1989. – Vol. 18, N 6. – P. 1128–1139.Rappaport, D. Computing simple circuits from a set of line segments is NP-complete / D. Rappaport // SIAM J. Comput. – 1989. – Vol. 18, N 6. – P. 1128–1139.Compatible geometric matchings / O. Aichholzer [et al.] // Comp. Geom. Theor. Appl. – 2009. – Vol. 42. – P. 617–626.Compatible geometric matchings / O. Aichholzer [et al.] // Comp. Geom. Theor. Appl. – 2009. – Vol. 42. – P. 617–626.Convex partitions with 2-edge connected dual graphs / M. Al-Jubeh [et al.] // J. Combin. Opt. – 2011. – Vol. 22, N 3. – P. 409–425.Convex partitions with 2-edge connected dual graphs / M. Al-Jubeh [et al.] // J. Combin. Opt. – 2011. – Vol. 22, N 3. – P. 409–425.Edge-removal and non-crossing configurations in geometric graphs / O. Aichholzer [et al.] // Discr. Math. Theor. Comput. Sci. – 2010. – Vol. 12, N 1. – P. 75–86.Edge-removal and non-crossing configurations in geometric graphs / O. Aichholzer [et al.] // Discr. Math. Theor. Comput. Sci. – 2010. – Vol. 12, N 1. – P. 75–86.

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