1679
правок
Изменения
м
Нет описания правки
Получили z \leq y \leq j (по определению y) и i < z(по определению z). Получим:
D[i'][j'] + D[i][j] \leq 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]\leq w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[z][j] + D[y][j'] - по неравенству четырехугольника для w\leq w[i][j'] + w[i'][j] + D[i'][y-1] + D[i][z-1] + D[y][j] + D[z][j'] - по индукционному предположению= (w[i][j'] + D[i][z-1] + D[z][j']) + (w[i'][j] + D[i'][y-1] + D[y][j]) //переставить нормально\leq D[i][j'] + D[i'][j] - по определению D. Индукционный шаг завершен, лемма доказана.
}}
