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

распределенная сеть, трансформация графов, индекс Винера

Бурдонов Игорь Борисович,  ,  orcid.org/0000-0001-9539-7853,  ИСП РАН