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: \;\rightarrow u_1 \rightarrow u_2 \rightarrow ... \rightarrow u_k </tex>
:<tex>w_\phi(P) = w_\phi(u_1u_2) + w_\phi(u_2u_3) + ... + w_\phi(u_{k-1}u_k) = \phi(u_1) + w(u_1u_2) - \phi(u_2) + ... - \phi(u_{k-1})+\phi(u_{k-1}) + w(u_{k-1}u_k) - \phi(u_k) = \phi(u_1) + w(P) - \phi(u_k)</tex>
:<tex>w_\phi(P) < w_\phi(Q)</tex>
:<tex>w_\phi(P) = \phi(a) + w(P) - \phi(b)</tex>
:<tex>w_\phi(Q) = \phi(a) + w(Q) - \phi(b)</tex>
:Отсюда, <tex>w(P) < w(Q)</tex>
}}
