205
правок
Изменения
м
→Сохранение кратчайших путей
Пусть <tex>P,\; Q : a \rightsquigarrow b.\; w(P) < w(Q)</tex>. Тогда <tex>\forall \phi: \; w_\phi(P) < w_\phi(Q)</tex>
|proof=
:<tex>P: \;u_0 \rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k </tex>
:<tex>w_\phi(P) = w_\phi(u_1u_2u_0u_1) + w_\phi(u_2u_3u_1u_2) + ... + w_\phi(u_{k-1}u_k) = \phi(u_1u_0) + w(u_1u_2u_0u_1) - \phi(u_2u_1) + ... </tex> <tex>- \phi(u_{k-1}) + \phi(u_{k-1}) + w(u_{k-1}u_k) - \phi(u_k) = </tex> <tex>=\phi(u_1u_0) + w(P) - \phi(u_k)</tex>
:<tex>w_\phi(P) < w_\phi(Q)</tex>
