205
правок
Изменения
→Изменение веса
}}
=== Изменение веса Теорема о существовании потенциальной функции ==={{Теорема|statement= В графе <tex>G</tex> нет отрицательных циклов тогда и только тогда, когда существует потенциальная функция <tex> \phi:\; \forall u,v\; w_\phi(uv) >= 0 </tex>|proof=<tex>\Leftarrow) </tex><tex>w(C) = \phi(u_1) + w(c) - \phi(u_1) = w_\phi(C) >= 0</tex> <tex>\Rightarrow) </tex> Добавим вершину <tex>s</tex> в граф, соединим её со всеми вершинами графа <tex>G</tex> ребрами весом <tex>w = 0</tex>.<tex>\phi(u) = \delta(s,\;u)</tex> <tex>w_\phi(uv) = \phi(u) + w(uv) - \phi(v) = \delta(s,\;u) + w(uv) - \delta(s,\;v)</tex>. <tex>\delta(s,\;u) + w(uv) = </tex> {какой-то путь <tex>s \rightsquigarrow v</tex>}. <tex>\delta(s,\;v) =</tex> {минимальный путь <tex>s \rightsquigarrow v</tex>}. Следовательно, <tex>w_\phi(uv) >= 0</tex>}}
=== Псевдокод ===
