Б. Ф. Мельников, Е. Ф. Сайфуллина
ПРИМЕНЕНИЕ МУЛЬТИЭВРИСТИЧЕСКОГО ПОДХОДА
ДЛЯ СЛУЧАЙНОЙ ГЕНЕРАЦИИ ГРАФА С ЗАДАННЫМ
ВЕКТОРОМ СТЕПЕНЕЙ
Аннотация. <...> Это обусловливает актуальность исследования алгоритмов генерации графов с
заданным вектором степеней. <...> Целью исследования является рассмотрение существующих методов и разработка собственного алгоритма, позволяющего
сгенерировать граф на основе заданного вектора степеней. <...> Приводится определение графической последовательности; формулируются известные критерии проверки, является ли данная последовательность графической. <...> Приводится разработанный авторами алгоритм, представляющий собой реализацию одного из критериев проверки на основе мультиэвристического подхода (незавершенного метода ветвей и границ). <...> Вводится понятие вектора степеней второго порядка и приводится модификация разработанного алгоритма на случай генерации графов с заданным вектором степеней второго
порядка. <...> Эта модификация также выполнена на основе незавершенного метода ветвей и границ. <...> Таким образом, предлагается новый подход к случайной
генерации графов как к задаче дискретной оптимизации. <...> В ходе вычислительных экспериментов на основе некоторых функций распределения были сгенерированы последовательности заданного размера (предполагаемое число вершин графа). <...> В случае если сгенерированная последовательность является графической, на ее основе может быть сгенерирован граф. <...> Затем на основе вектора степеней второго порядка полученного графа был сгенерирован еще один
граф. <...> Приводятся результаты измерения среднего времени выполнения программы (в миллисекундах) в случае разных функций распределения и разных
размерностей графа. <...> Приведенные разные варианты генерации случайных графов могут быть полезны во многих приложениях, прежде всего в
сетевых моделях; среди последних наиболее важными являются математические модели Интернета и социальных сетей, а также модели <...>