NP-полнота задачи построения графа с минимальным коэффициентом непрямолинейности
Автор: Хижнякова Е.В.
Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu
Рубрика: Моделирование, информатика и управление
Статья в выпуске: 2 т.26, 2023 года.
Бесплатный доступ
В настоящей статье рассмотрена задача построения плоского связного взвешенного графа на заданном наборе точек с минимальным коэффициентом непрямолинейности. За вес ребра берется евклидово расстояние между концами. Доказывается, что такая задача является NP-полной. Так как эта задача является NP-полной, предложен эвристический алгоритм решения рассматриваемой задачи. Данный алгоритм всегда строит триангуляцию, так как только в этом классе графов возможно решение поставленной задачи. Проведен ряд экспериментов по статистическому исследованию коэффициента непрямолинейности триангуляции, построенной в результате работы приведенного алгоритма на случайно сгенерированных точках.
Np-полнота, коэффициент непрямолинейности, граф, триангуляция, эвристический алгоритм
Короткий адрес: https://sciup.org/149143814
IDR: 149143814 | DOI: 10.15688/mpcm.jvolsu.2023.2.4
Список литературы 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
