205
правок
Изменения
м
→Теорема о существовании потенциальной функции
В графе <tex>G</tex> нет отрицательных циклов тогда и только тогда, когда существует потенциальная функция <tex> \phi:\; \forall u,v\; w_\phi(uv) >= 0 </tex>
|proof=
<tex>\Leftarrow) </tex> <tex>C</tex> - цикл в графе <tex>G</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>
}}
