35
правок
Изменения
→Код (окончательный)
#* Значение <tex> d_{uv} </tex> не изменилось. Тогда неравенство выполняется автоматически по индукционному предположению.
# <tex> d_{uv} \le d_{uv}^{(i)} </tex>. Аналогично рассмотрим два случая:
#* Значение <tex> d_{uv}^{(i)} </tex> изменилось. Тогда <tex> d_{uv}^{(i)} \ge d_{ui}^{(i-1)} + d_{iv}^{(i-1)} \ge d_{ui}^{(i)} + d_{iv}^{(i)} \ge d_{ui} + d_{uv} \ge d_{uv} </tex>, по индукционному предположению и тому факту, что <tex> d_{uv}^{(i)} </tex> невозрастает не возрастает с ростом <tex> i </tex>.
#* В ином случае всё очевидно: <tex> d_{uv}^{(i)} = d_{uv}^{(i - 1)} \ge d_{uv} </tex>, и неравенство тривиально.
