205
правок
Изменения
м
→Теорема о существовании потенциальной функции
<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>.
