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