Хижнякова Е.В. NP-полнота задачи построения графа с минимальным коэффициентом непрямолинейности

Рейтинг:   / 0
ПлохоОтлично 
Подробности
Просмотров: 250

https://doi.org/10.15688/mpcm.jvolsu.2023.1.3

Екатерина Владимировна Хижнякова
Старший преподаватель кафедры компьютерных наук и экспериментальной математики,
Волгоградский государственный университет
Этот адрес электронной почты защищен от спам-ботов. У вас должен быть включен JavaScript для просмотра.
https://orcid.org/0000-0002-7914-9988
просп. Университетский, 100, 400062 г. Волгоград, Российская Федерация

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

Ключевые слова: NP-полнота, коэффициент непрямолинейности, граф, триангуляция, эвристический алгоритм.

Лицензия Creative Commons
Произведение «NP-полнота задачи построения графа с минимальным коэффициентом непрямолинейности», созданное автором по имени Хижнякова Е.В. публикуется на условиях лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.

Цитата: Математическая физика и компьютерное моделирование. Том 26 № 2 2023, с. 43-51

Вложения:
Скачать этот файл (2_2023-44-52.pdf) 2_2023-44-52.pdf
URL: https://mp.jvolsu.com/index.php/ru/component/attachments/download/1093		159 Скачивания