Математическая физика и компьютерное моделирование2587-63252587-690210.15688/mpcm.jvolsu.2023.2.4OtherNP-полнота задачи построения графа с минимальным коэффициентом непрямолинейностиNP-completeness of the problem of constructing a graph with a minimum stretch factorХижняковаЕкатерина ВладимировнаKhizhnyakovaEkaterina V.yakovleva.e.v@volsu.ruhttps://orcid.org/0000-0002-7914-9988Volgograd State University(Volgograd, Russian Federation)Волгоградский государственный университет(г. Волгоград, Российская Федерация)2005202326243512103202326042023https://creativecommons.org/licenses/by-nc/4.0/CC BY-NC 4.0

В настоящей статье рассмотрена задача построения плоского связного взвешенного графа на заданном наборе точек с минимальным коэффициентом непрямолинейности. За вес ребра берется евклидово расстояние между концами. Доказывается, что такая задача является NP-полной. Так как эта задача является NP-полной, предложен эвристический алгоритм решения рассматриваемой задачи. Данный алгоритм всегда строит триангуляцию, так как только в этом классе графов возможно решение поставленной задачи. Проведен ряд экспериментов по статистическому исследованию коэффициента непрямолинейности триангуляции, построенной в результате работы приведенного алгоритма на случайно сгенерированных точках.

In this paper, we consider the problem of constructing a planar connected weighted graph on a given set of points in such a way that the sum of the shortest paths between all pairs of vertices is the minimum possible. In other words, the problem of constructing a graph with a minimum stretch factor. The euclidean distance between the ends is taken as the weight of the edge. It is proved that such a problem is NP-complete. This problem arises when planning transport networks, since it is the stretch factor of the graph of the transport network that directly indicates the level of overrun of transport, which should be as small as possible in order to minimize the resources spent. But since this problem is NP-complete, a heuristic algorithm for solving the problem under consideration is proposed, which is based on sorting some simple paths and has a recursive character. This algorithm always builds a triangulation, since only in this class of graphs is it possible to solve the problem. A number of experiments have been carried out on the statistical study of the stretch factor of the triangulation constructed as a result of the operation of the above algorithm on randomly generated points. Experiments show that the losses are about 1.5–7.8% , and for real cities this parameter is about 30%.

NP-полнотакоэффициент непрямолинейностиграфтриангуляцияэвристический алгоритмNP-completeness stretch factorgraphtriangulationheuristic algorithmАлгоритмы: построение и анализ / Х. К. Томас, И. Л. Чарльз, Л. P. Рональд, К. Штайн. — М. : Издательский дом «Вильямс», 2013. — 1296 c.Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. — М. : Мир, 1982. — 416 c.Свами, М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. — М. : Мир, 1984. — 454 c.Хижнякова, Е. В. Построение неориентированного графа с низким коэффициентом непрямолинейности / Е. В. Хижнякова // Материалы XIII Международной научно-технической конференции «Информатика, управляющие системы, математическое и компьютерное моделирование» (ИУСМКМ-2022). — Донецк : Изд-во ДОННТУ, 2022. — C. 255–258.Яковлева, Е. В. Исследование коэффициента растяжения планарного графа транспортной сети численными методами / Е. В. Яковлева, В. А. Клячин // XXIII Региональная конференция молодых исследователей Волгоградской области. — Волгоград : Изд-во ВолГУ, 2019. — C. 24–26.Almost all Delaunay Triangulations Have Stretch Factor Greater Than π/2 / P. Bose, L. Devroye, M. Loffler, J. Snoeyink, V. Verma // Computational Geometry: Theory and Applications. — 2011. — Vol. 44. — P. 121–127. — DOI: https://doi.org/10.1016/j.comgeo.2010.09.009Chew, L. P. There Are Planar Graphs Almost as the Complete Graph as Good / L. P. Chew // Journal of Computer and System Sciences. — 1989. — Vol. 39. — P. 205–219. — DOI: https://doi.org/10.1016/0022-0000(89)90044-5Johnson, D. S. The Complexity of the Network Design Problem / D. S. Johnson, J. K. Lenstra, A. H. G. Rinnooy Kan // Networks. — 1978. — Vol. 8. — P. 279–285. — DOI: https://doi.org/10.1002/net.3230080402Klyachin, V. A. Mathematical Methods for the Analysis and Optimization of the Geometry of Transport Networks Based on Generalized Delaunay Triangulations / V. A. Klyachin, E. V. Yakovleva // “Smart Technologies” for Society, State and Economy (Lecture Notes in Networks and Systems). — 2021. — Vol. 155. — P. 1596–1604. — DOI: https://doi.org/10.2991/cssdre-18.2018.94On the Stretch Factor of Convex Delaunay Graphs / P. Bose, P. Carmi, S. Collette, M. Smid // Algorithms and Computation. Lecture Notes in Computer. — 2008. — Vol. 5369. — P. 656–667. — DOI: https://doi.org/10.1007/978-3-540-92182-0_58Seidel, R. On the Number of Triangulations of Planar Point Sets / R. Seidel // Combinatorica. — 1998. — Vol. 18. — P. 297–299. — DOI: https://doi.org/10.1007/978-3540-70904-6_1Tomas Kh.K., Charles I.L., Ronald L.P., Clifford K. Algoritmy: postroenie i analiz [Introduction to Algorithms]. Moscow, “Vilyams” Publ., 2013. 1296 p.Garey M., Johnson D. Vychislitelnye mashiny i trudnoreshaemye zadachi [Computers and Intractability: A Guide to the Theory of NP-Completeness]. Moscow, Mir Publ., 1982. 416 p.Swamy M., Thulasiraman K. Grafy, seti i algoritmy [Graphs, Networks, and Algorithms]. Moscow, Mir Publ., 1984. 454 p.Khizhnyakova E.V. Postroenie neorientirovannogo grafa s nizkim koeffitsientom nepryamolineynosti [Construction of an Undirected Graph with a Low Stretch Factor]. Materialy XIII Mezhdunarodnoy nauchno-tekhnicheskoy konferentsii «Informatika, upravlyayushchie sistemy, matematicheskoe i kompyuternoe modelirovanie» (IUSMKM-2022). Donetsk, Izd-vo DNTU, 2022, pp. 255-258.Yakovleva E.V., Klyachin V.A. Issledovanie koeffitsienta rastyazheniya planarnogo grafa transportnoy seti chislennymi metodami [Investigation of the Stretch Factor of a Planar Graph of a Transport Network by Numerical Methods]. XXIII Regionalnaya konferentsiya molodykh issledovateley Volgogradskoy oblasti. Volgograd, Izd-vo VolSU, 2019, pp. 24-26.Bose P., Devroye L., Loffler M., Snoeyink J., Verma V. Almost All Delaunay Triangulations Have Stretch Factor Greater Than π/2. Computational Geometry: Theory and Applications, 2011, vol. 44, pp. 121-127. DOI: https://doi.org/10.1016/j.comgeo.2010.09.009Chew L.P. There Are Planar Graphs Almost as the Complete Graph as Good. Journal of Computer and System Sciences, 1989, vol. 39, pp. 205-219. DOI: https://doi.org/10.1016/00220000(89)90044-5Johnson D.S., Lenstra J.K., Rinnooy Kan A.H.G. The Complexity of the Network Design Problem. Networks, 1978, vol. 8, pp. 279-285. DOI: https://doi.org/10.1002/net.3230080402Klyachin V.A., Yakovleva E.V. Mathematical Methods for the Analysis and Optimization of the Geometry of Transport Networks Based on Generalized Delaunay Triangulations. “Smart Technologies” for Society, State and Economy (Lecture Notes in Networks and Systems), 2021, vol. 155, pp. 1596-1604. DOI: https://doi.org/10.2991/cssdre18.2018.94Bose P., Carmi P., Collette S., Smid M. On the Stretch Factor of Convex Delaunay Graphs. Algorithms and Computation. Lecture Notes in Computer, 2008, vol. 5369, pp. 656-667. DOI: https://doi.org/10.1007/978-3-540-92182-0_58Seidel R. On the Number of Triangulations of Planar Point Sets. Combinatorica, 1998, vol. 18, pp. 297-299. DOI: https://doi.org/10.1007/978-3-540-70904-6_1