73
правки
Изменения
м
→Сложность алгоритма: орфография
|about=1
|statement=
Пусть <tex>a</tex> — любая вершина в последовательности, состоящей из вершин алфавита и вершин образованных в результате комбинации, <tex>w_{i}</tex> — вес наименьшего узла наименьшей вершины <tex>i</tex>, совместимого с <tex>a</tex>. Если в результате комбинирования некоторой л.м.с.п. какой-нибудь новый узел <tex>d</tex> становится совместимым c <tex>a</tex>, то <tex>w_{i}<w_{d}</tex> В частности, л.м.с.п. в последовательности узлов вершин будет оставаться л.м.с.п., пока комбинируются другие л.м.с.п.
Из этой леммы следует, что дерево, получаемое комбинированием л.м.с.п., не зависит от того, в каком порядке они комбинируются.
|proof=
Рассмотрим произвольный узел вершина <tex>a</tex> и предположим, что вес наименьшего узланаименьшей вершины, совместимого с <tex>a</tex>, равен <tex>w_{i}</tex>.
Пусть комбинируется л.м.с.п. <tex>(b, c)</tex>, причем <tex>a</tex> ближе к <tex>b</tex>. Тогда между <tex>a</tex> и <tex>b</tex> нет вершин алфавита и хотя бы одна из <tex>b</tex>, <tex>c</tex> должна быть вершиной алфавита, иначе при слиянии <tex>(b, c)</tex> не появилось бы новых вершин (кроме <tex>bc</tex>), совместимых с <tex>a</tex>.
Но <tex>w_{i}<w_{b}</tex>, так как <tex>b</tex> совместим с <tex>a</tex> в исходной последовательности, а <tex>w_{i}</tex> является наименьшим совместимым с <tex>a</tex> весом. Поэтому <tex>w_{i} \le w_{b} \le w_{d}</tex>.
Мы доказали, что вес наименьшего узланаименьшей вершины, совместимого совместимой с любым узломлюбой вершиной, не может уменьшиться. Отсюда следует, что любая л.м.с.п. <tex>(x, y)</tex> останется л.м.с.п. после слияния другой л.м.с.п., потому что <tex>x</tex> останется наименьшим узломнаименьшей вершиной, совместимым совместимой с <tex>y</tex>, и наоборот.
}}
