Минимальный средний весовой цикл ⇐ Васина Википедия

[wiki_en]

В теории графов «цикл с минимальным средним весом» — это цикл (теория графов)|цикл, средний вес которого (общий вес, разделенный на длину) наименьший среди всех циклов в графе.
== Определения ==
Пусть G = (V,E) — ориентированный граф, в котором каждое ребро имеет вес (положительный или отрицательный). '''Вес''' любого пути или цикла p = (e1,...,ek) представляет собой сумму весов ребер: w(p) = w(e1) + ... + w(ek). «Средний вес» p — это вес p, разделенный на количество ребер в нем: w(p)/len(p).

«Минимальный средний вес цикла» в G — это минимальное значение w(p)/len(p) среди всех направленных циклов p в G. «Цикл с минимальным средним весом» — это любой цикл с минимальным средним весом.

== Алгоритмы ==
Лоулер
Карп представил характеристику минимального среднего веса цикла и представил алгоритм, работающий за время O(''|V||E|'').

== См. также ==
* Отрицательный цикл

Объекты теории графов

Подробнее: https://en.wikipedia.org/wiki/Minimum_mean_weight_cycle