Обмен ближайшими соседями и относительные расстояния: различия между версиями

В случае переноса поддеревьев с линейной стоимостью кажется логичным, чтобы за перемещение поддерева взималась «плата» в соответствии с пройденным им расстоянием, однако стоит дать более формальное определение. Рассмотрим (некорневые) деревья, в которых каждому ребру <math>e \;</math> приписан вес <math>w(e) \ge 0 \;</math>. Для того чтобы одно дерево можно было преобразовать в другое, необходимо, чтобы полный вес всех ребер был равен единице. Теперь перенос поддеревьев можно определить следующим образом. Выберите поддерево S дерева T в заданной вершине u, выберите ребро <math>e \notin S \;</math>. Расщепите ребро <math>e \;</math> на два ребра <math>e_1 \;</math> и <math>e_2 \;</math> с весами <math>w(e_1) \;</math> и <math>w(e_2) \;</math>, <math>w(e_1), w(e_2) \ge 0,w(e_1) + w(e_2) = w(e)</math>, и переместите S в общую конечную точку <math>e_1 \;</math> и <math>e_2 \;</math>. После этого выполните слияние двух оставшихся ребер e' и e' ', смежных с u, в одно ребро с весом w(e') + w(e' '). Стоимость этого переноса поддеревьев представляет собой сумму весов всех ребер, через которые перемещается S. Пример переноса приведен на рис. 1. Веса ребер исходного дерева нормализованы, чтобы их общая сумма была равна 1. Поддерево S переносится таким образом, что ребро <math>e_4 \;</math> разбивается на <math>e_6 \;</math> и <math>e_7 \;</math>, при этом <math>w(e_6), w(e_7) \ge 0 \;</math> и <math>w(e_6) + w(e_7) = w(e_4) \;</math> наконец, два ребра <math>e_1 \;</math> и <math>e_2 \;</math> сливаются вместе, образуя ребро <math>e_5 \;</math>, такое, что <math>w(e_5) = w(e_1) + w(e_2) \;</math>. Стоимость переноса S составит <math>w(e_2) + w(e_3) + w(e_6) \;</math>.