276
правок
Изменения
Новая страница: «==Алгоритм отмены цикла минимального среднего веса== Приведенный алгоритм принадлежит к...»
==Алгоритм отмены цикла минимального среднего веса==
Приведенный алгоритм принадлежит к классу сильно полиномиальных алгоритмов.
{{Определение
|definition='''Сильно полиномиальными''' в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от <tex>V</tex> {{---}} числа вершин и <tex>E</tex> {{---}} числа ребер графа.}}
===Описание алгоритма===
Рассмотрим некоторый цикл <tex>C</tex>. Обозначим его стоимость за <tex>p(C)</tex>, а его длину (число ребер, входящих в цикл) за <tex>\texttt{len}(C)</tex>.
{{Определение
|definition='''Средним весом цикла''' называется отношение его стоимости к его длине <tex>\mu (C)=\frac{p(C)}{\texttt{len}(C)}</tex>}}
====Сам алгоритм====
Рассмотрим некоторый поток <tex>f</tex>. Находим цикл <tex>C</tex>, обладающий наименьшим средним весом. Если <tex>\mu (C) \geq 0</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости и алгоритм завершается.
Иначе, отменим цикл <tex>C</tex>: <tex>f := f + c_{f}(C)\cdot f_{C}, где <tex>c_{f}(C) {{---}} остаточная пропускная способность цикла <tex>C</tex>.
Вернемся к началу алгоритма.
====Время работы алгоритма====
<tex>O(VE\cdot VE^{2}\log{V})</tex>
===Алгоритм поиска цикла минимального среднего веса===
Приведенный алгоритм принадлежит к классу сильно полиномиальных алгоритмов.
{{Определение
|definition='''Сильно полиномиальными''' в контексте данной задачи называются алгоритмы, чья сложность полиномиально зависит от <tex>V</tex> {{---}} числа вершин и <tex>E</tex> {{---}} числа ребер графа.}}
===Описание алгоритма===
Рассмотрим некоторый цикл <tex>C</tex>. Обозначим его стоимость за <tex>p(C)</tex>, а его длину (число ребер, входящих в цикл) за <tex>\texttt{len}(C)</tex>.
{{Определение
|definition='''Средним весом цикла''' называется отношение его стоимости к его длине <tex>\mu (C)=\frac{p(C)}{\texttt{len}(C)}</tex>}}
====Сам алгоритм====
Рассмотрим некоторый поток <tex>f</tex>. Находим цикл <tex>C</tex>, обладающий наименьшим средним весом. Если <tex>\mu (C) \geq 0</tex>, то <tex>f</tex> {{---}} поток минимальной стоимости и алгоритм завершается.
Иначе, отменим цикл <tex>C</tex>: <tex>f := f + c_{f}(C)\cdot f_{C}, где <tex>c_{f}(C) {{---}} остаточная пропускная способность цикла <tex>C</tex>.
Вернемся к началу алгоритма.
====Время работы алгоритма====
<tex>O(VE\cdot VE^{2}\log{V})</tex>
===Алгоритм поиска цикла минимального среднего веса===
