1679
правок
Изменения
м
Для доказательства этого сперва докажем несколько леммВ случае i = j неравенство, очевидно, выполняется. Рассматриваем случай i < j и только случай R[i][j] \le R[i][j+1](вторая часть доказывается аналогично):
Нет описания правки
<tex> \forall i \le j : R[i][j] \le R[i][j+1] \le R[i+1][j+1] </tex>
| proof=
Так как R[i][j] - макимальный индекс, в котором достигается минимум, достаточно показать, что:
: <tex> \forall i < k \le k' \le j: [D_{k'}[i][j] < D_k[i][j]] \Rightarrow [D_{k'}[i][j+1] < D_k[i][j+1]] </tex>
Докажем более сильное неравенство:
: <tex> \forall i < k \le k' \le j: D_k[i][j] - D_{k'}[i][j] \Rightarrow D_k[i][j+1] - D_{k'}[i][j+1] </tex>
: <tex> D_k[i][j] + D_{k'}[i][j+1] \Rightarrow D_k[i][j+1] + D_{k'}[i][j] </tex>
, что по определению равно
: <tex> D[k][j] + D[k'][j+1] \Rightarrow D[k][j+1] + D[k'][j] </tex> - получили неравенство четырехугольника для <tex> k \le k' \le j \le j+1 </tex>
}}
