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

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