35
правок
Изменения
→Теорема о существовании потенциальной функции
<tex>\Leftarrow </tex>: <tex>C</tex> - цикл в графе <tex>G</tex>
:<tex>w(C) = w_\varphi(u_1C) + w- \sum\limits_{uv \in C} (C\varphi(u) - \varphi(u_1v)) = w_\varphi(C) \ge 0</tex>
<tex>\Rightarrow </tex>: Добавим вершину <tex>s</tex> в граф, соединим её со всеми вершинами графа <tex>G</tex> ребрами весом <tex>w = 0</tex>.
