Головная страница ИПМ Библиотеки, издания  •  Поиск публикаций  English 
Публикация

Материал конференции: "Научный сервис в сети Интернет: труды XXI Всероссийской научной конференции (23-28 сентября 2019 г., г. Новороссийск)"
Авторы: Бурдонов И.Б.
Распределенный алгоритм самотрансформации топологии распределенной сети с целью минимизации индекса Винера
Аннотация:
Рассматривается распределенная сеть, топология которой описывается неориентированным деревом без кратных ребер и петель. Сеть может сама менять свою топологию, используя специальные «команды», подаваемые ее узлами. В работе предложена предельно локальная атомарная трансформация: добавление ребра, соединяющего разные концы двух смежных ребер, и одновременное удаление одного из этих ребер. Такая трансформация выполняется по «команде» от общей вершины двух смежных ребер. Показывается, что из любого дерева можно получить любое другое дерево с помощью только атомарных трансформаций. Если степени вершин дерева ограничены числом d (d ≥ 3), то трансформация не нарушает этого ограничения. В качестве примера цели такой трансформации рассматриваются задачи максимизации и минимизации индекса Винера дерева с ограниченной степенью вершин без изменения множества его вершин. Индекс Винера – это сумма попарных расстояний между вершинами графа. Максимальный индекс Винера имеет линейное дерево (дерево с двумя листовыми вершинами). Для корневого дерева с минимальным индексом Винера определяется его вид и способ вычисления числа вершин в ветвях соседей корня. Предлагаются два распределенных алгоритма: трансформация дерева в линейное дерево и трансформация линейного дерева в дерево с минимальным индексом Винера. Доказывается, что оба алгоритма имеют сложность не выше 2n - 2, где n число вершин дерева.
Ключевые слова:
распределенная сеть, трансформация графов, индекс Винера
Язык публикации: русский,  страниц: 11 (с. 166-176)
Полный текст на русском языке: Сведения об авторах:
  • Бурдонов Игорь Борисович,  orcid.org/0000-0001-9539-7853,  ИСП РАН