В теории графов «цикл с минимальным средним весом» — это цикл (теория графов)|цикл, средний вес которого (общий вес, разделенный на длину) наименьший среди всех циклов в графе.
== Определения ==
Пусть 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
Минимальный средний весовой цикл ⇐ Васина Википедия
-
Автор темыwiki_en
- Всего сообщений: 94689
- Зарегистрирован: 16.01.2024
-
- Похожие темы
- Ответы
- Просмотры
- Последнее сообщение
Мобильная версия