63
правки
Изменения
Нет описания правки
<tex>|LCS(X, Y)| + |SCS(X, Y)| = n + m</tex>, где <tex>|LCS(X, Y)|</tex> - длина [[Задача о наибольшей общей подпоследовательности| наибольшей общей подпоследовательности]], <tex>|SCS(X, Y)|</tex> - длина наименьшей общей суперпоследовательности, <tex>n</tex> и <tex>m</tex> - длины последовательностей <tex> X </tex> и <tex> Y </tex> соответсвенно.
|proof= Пусть <tex> X = \left \langle x_1, x_2, \dots, x_n \right \rangle </tex>, <tex> Y = \left \langle y_1, y_2, \dots, x_m \right \rangle </tex>. Обозначим за <tex> S </tex> их SCS и будем ее строить. Так как <tex>XS</tex> являетcя подпоследовательностью суперпоследовательностью <tex> S X </tex>, то можно представить <tex>S</tex> так:
<tex> S = \dots x_1 \dots x_2 \dots x_i \dots x_n \dots </tex>
Мы должны поставить на место некоторых пропусков поставить элементы <tex>Y</tex>, так чтобы суммарная длина <tex> S </tex> была минимальна, и <tex> Y S </tex> был подпоследовательностью суперпоследовательностью <tex>SX</tex>. Заметим, что если найдется Рассмотрим любую общую подпоследовательность <tex>YX</tex> такая, что является подпоследовательностью и <tex> X Y</tex>.Заметим, то все элементы этой подпоследовательности что она уже находятся в <tex>S</tex>, а значит их все её элементы не нужно вставлятьдобавлять. Поэтому мы добавим не меньше чем <tex> m - |LCS(X, Y)| элементов </tex>. Длину <tex> SCS(X, Y) </tex> нужно минимизировать, значит имеет место равенство:
<tex>|SCS(X,Y)| = n + (m - |LCS(X, Y)|)</tex>.
Поэтому: <tex>|LCS(X, Y)| + |SCS(X, Y)| = n + m</tex>
