NP-полнота задачи построения графа с минимальным коэффициентом непрямолинейности
Автор: Хижнякова Е.В.
Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu
Рубрика: Моделирование, информатика и управление
Статья в выпуске: 2 т.26, 2023 года.
Бесплатный доступ
В настоящей статье рассмотрена задача построения плоского связного взвешенного графа на заданном наборе точек с минимальным коэффициентом непрямолинейности. За вес ребра берется евклидово расстояние между концами. Доказывается, что такая задача является NP-полной. Так как эта задача является NP-полной, предложен эвристический алгоритм решения рассматриваемой задачи. Данный алгоритм всегда строит триангуляцию, так как только в этом классе графов возможно решение поставленной задачи. Проведен ряд экспериментов по статистическому исследованию коэффициента непрямолинейности триангуляции, построенной в результате работы приведенного алгоритма на случайно сгенерированных точках.
Np-полнота, коэффициент непрямолинейности, граф, триангуляция, эвристический алгоритм
Короткий адрес: https://sciup.org/149143814
IDR: 149143814 | УДК: 519.16 | DOI: 10.15688/mpcm.jvolsu.2023.2.4
NP-completeness of the problem of constructing a graph with a minimum stretch factor
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-полнота задачи построения графа с минимальным коэффициентом непрямолинейности
- Алгоритмы: построение и анализ / Х. К. Томас, И. Л. Чарльз, Л. P. Рональд, К. Штайн. — М.: Издательский дом «Вильямс», 2013. — 1296 с.
- Гэри, М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон. — М.: Мир, 1982. — 416 с.
- Свами, М. Графы, сети и алгоритмы / М. Свами, К. Тхуласираман. — М.: Мир, 1984. — 454 с.
- Хижнякова, Е. В. Построение неориентированного графа с низким коэффициентом непрямолинейности / Е. В. Хижнякова // Материалы XIII Международной научно-технической конференции «Информатика, управляющие системы, математическое и компьютерное моделирование» (ИУСМКМ-2022). — Донецк: Изд-во ДОННТУ, 2022. — C. 255-258.
- Яковлева, Е. В. Исследование коэффициента растяжения планарного графа транспортной сети численными методами / Е. В. Яковлева, В. А. Клячин // XXIII Региональная конференция молодых исследователей Волгоградской области. — Волгоград: Изд-во ВолГУ, 2019. — C. 24-26.
- Almost all Delaunay Triangulations Have Stretch Factor Greater Than n/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.009
- Chew, 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-5
- Johnson, 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.3230080402
- Klyachin, 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.94
- On 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_58
- Seidel, 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-3-540-70904-6_1
