Изменения

Перейти к: навигация, поиск

Алгоритм Джонсона

1 байт убрано, 23:27, 19 ноября 2010
м
Теорема о существовании потенциальной функции
<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>.
205
правок

Навигация