1679
правок
Изменения
м
}}
{{Определение
| definition=
Функция a является '''монотонной(monotone)''', если
: <tex>\forall i \le i' < j \le j' : a[i][j'] \le a[i'][j] </tex>
При База индукции: при <tex> i = i' </tex> или <tex> j = j' </tex>, очевидно, неравенство выполняется.
Нет описания правки
Функция a удовлетворяет '''неравенству четырехугольника(quadrangle inequation)''', если
: <tex>\forall i \le i' \le j \le j' : a[i][j] + a[i'][j'] \le a[i'][j] + a[i][j']</tex>
}}
{{Лемма
| statement=
Если w удовлетворяет неравенству четырехугольника и монотонна, то D также удовлетворяет неравенству четырехугольника, то есть:
<tex>\forall i \le i' \le j \le j' : D[i][j] + D[i'][j'] \le D[i'][j] + D[i][j'] </tex>
| proof=
Рассмотрим два случая:
## <tex> k \le j </tex>
##: <tex> D[i][j] + D[j][j'] \le w[i][j] + D[i][k-1] + D[k][j] + D[j][j'] </tex> - по определению <tex> D[i][j] </tex>
##: <tex> \le w[i][j'] + D[i][k-1] + D[k][j] + D[j][j'] </tex> - по монотонности так как <tex> w[i][j'] >= w[i][j] </tex>
##: <tex> \le w[i][j'] + D[i][k-1] + D[k][j'] </tex> - по индукционному предположению для D
##: <tex> \le D[i][j'] </tex> - по определению <tex> D[i][j'] </tex>
Монотонность точки разреза
| statement=
Если w удовлетворяет неравенству четырехугольника и монотонна, то:
<tex> \forall i \le j : R[i][j] \le R[i][j+1] \le R[i+1][j+1] </tex>
| proof=
В случае <tex> i = j </tex> неравенство, очевидно, выполняется. Рассматриваем случай <tex> i < j </tex> и только случай <tex> R[i][j] \le R[i][j+1]</tex>(вторая часть доказывается аналогично):
Так как <tex> R[i][j] </tex> - максимальный индекс, в котором достигается минимум, достаточно показать, что:: <tex> \forall i < k \le k' \le j: [D_{k'}[i][j] \le D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] \le D_k[i][j+1]] </tex>- фактически, это означает что если на отрезке <tex> i..j </tex> разрез оптимальнее по <tex> k' </tex>, чем по <tex> k </tex>, то он также будет оптимальнее и на отрезке <tex> i..j+1 </tex>.
Докажем более сильное неравенство:
: <tex> \forall i < k \le k' \le j: D_k[i][j] - D_{k'}[i][j] \le D_k[i][j+1] - D_{k'}[i][j+1] </tex>
: <tex> (w[i][j] + D[i][k-1] + D[h][j]) + (w[i][j+1] + D[i][k'-1] + D[k][j+1]) \le (w[i][j+1] + D[i][k-1] + D[k][j+1]) + (w[i][j] + D[i][k'-1] + D[k'][j]) </tex> - по определению D
: <tex> D[k][j] + D[k'][j+1] \Rightarrow le D[k][j+1] + D[k'][j] </tex> - получили неравенство четырехугольника для <tex> k \le k' \le j \le j+1 </tex>, что является верным из предыдущей леммы. Теорема доказана.
}}
