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