1679
правок
Изменения
м
Нет описания правки
Получили <tex> 0 \leq 0 </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> i = i' </tex> или <tex> j = 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> - по монотонности w
##: <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>
## <tex> k \ge j </tex> - аналогичный предыдущему случай.
# <tex> i' < j </tex>
#: <tex> i < i' < j < j' </tex>
#: Пусть <tex> y = R[i'][j] </tex> и <tex> z = R[i][j'] </tex>. Получили два различных симметричных случая:
## <tex> z \le y </tex>
##: Получили <tex> z \le y \le j </tex> (по определению y) и <tex> i < z</tex>(по определению z). Получим:
##: <tex> D[i'][j'] + D[i][j] \le D_y[i'][j'] + D_z[i][j] = w[i'][j'] + D[i'][y-1] + D[y][j'] + w[i][j] + D[i][z-1] + D[z][j] </tex>
##: <tex> \le w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] </tex> - по неравенству четырехугольника для <tex> w </tex>
##: <tex> \le w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] </tex> - по индукционному предположению##: <tex> = (w[i][j'] + для D[i][z-1] + D[z][j']) + (w[i'][j] + D[i'][y-1] + D[y][j]) </tex> //переставить нормально
##: <tex> \le D[i][j'] + D[i'][j] </tex> - по определению D.
## <tex> z \ge y </tex> доказывается аналогично
Монотонность точки разреза
| statement=
Если w удовлетворяет неравенству четырехугольника и монотонна, то: <tex> \forall i \le j : R[i][j - 1] \le R[i][j+1] \le R[i + 1][j+1] </tex>
| proof=
Для доказательства этого сперва докажем несколько лемм:
}}
