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> В частности, л.м.с.п. в последовательности вершин будет оставаться л.м.с.п., пока комбинируются другие л.м.с.п.
Заметим, что <tex>w_{i}</tex> может находиться в любой стороне от <tex>a</tex>. Если вершина <tex>w_{i}</tex> лежит справа от <tex>a</tex>, то она не вершина алфавита. Пусть <tex>d</tex> — вершина, которая становится совместимой с <tex>a</tex> после слияния <tex>(b, c)</tex> (она может быть как алфавитной так и слитой). Тогда <tex>d</tex> должна быть совместима с <tex>c</tex> в исходной последовательности и в силу локальной минимальности пары <tex>(b, c)</tex> имеем <tex>w_{b} \le w_{d}</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>, и наоборот.
