276
правок
Изменения
→Продвинутый алгоритм
===Продвинутый алгоритм===
Добавим к нашему графу вершину <tex>s</tex> и ребра из нее во все остальные вершины.
Тогда длина оптимального цикла <tex>\mu^{*}</tex> минимального среднего веса вычисляется как <tex>\min\limits_{u} {\max\limits_{k} {\frac{d[n][u]-d[k][u]}{n-k}}}</tex>.
Достаточно будет доказать это правило для <tex>\mu^{*}=0</tex>, так как для других <tex>\mu^{*}</tex> можно просто отнять эту величину от всех ребер и получить снова случай с <tex>\mu^{*}=0</tex>.
