Сборники трудов ИСП РАН


Самотрансформация деревьев с ограниченной степенью вершин с целью минимизации или максимизации индекса Винера

Бурдонов И.Б. (ИСП РАН, Москва, Россия)

Аннотация

Рассматривается распределённая сеть, граф связи которой является неориентированным деревом. Предполагается, что сеть может сама менять свою топологию. Для этого предлагается предельно локальная атомарная трансформация – добавление ребра, соединяющего разные концы двух смежных ребер, и одновременное удаление одного из этих ребер. Такая трансформация выполняется по «команде» от вершины дерева, а именно, общей вершины двух смежных ребер. Показывается, что из любого дерева можно получить любое другое дерево с помощью только атомарных трансформаций. Если рассматриваются деревья с ограничением d (d  3) на степени вершин, то трансформация не нарушает этого ограничения. В качестве примера цели такой трансформации рассматриваются задачи максимизации и минимизации индекса Винера дерева с ограниченной степенью вершин без изменения множества его вершин. Предлагаются соответствующие распределённые алгоритмы и доказываются линейные оценки их сложности.

Ключевые слова

Аннотация. Рассматривается распределённая сеть, граф связи которой является неориентированным деревом. Предполагается, что сеть может сама менять свою топологию. Для этого предлагается предельно локальная атомарная трансформация – добавление ребра, соедин

Издание

Труды Института системного программирования РАН, том 31, вып. 4, 2019, стр. 189-210.

ISSN 2220-6426 (Online), ISSN 2079-8156 (Print).

DOI: 10.15514/ISPRAS-2019-31(4)-13

Для цитирования

Бурдонов И.Б. Самотрансформация деревьев с ограниченной степенью вершин с целью минимизации или максимизации индекса Винера. Труды Института системного программирования РАН, том 31, вып. 4, 2019, стр. 189-210. DOI: 10.15514/ISPRAS-2019-31(4)-13.

Полный текст статьи в формате pdf Вернуться к содержанию тома