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

В теории графов цикл минимального среднего веса — это цикл , средний вес которого (общий вес, деленный на длину) является наименьшим среди всех циклов в графе. ^[1] Аналогичная задача — цикл максимального среднего веса . Эти задачи имеют приложения к встроенным системам ^[2] и проектированию логических микросхем. ^[3]

Определения

Пусть G = (V,E) — ориентированный граф , в котором каждое ребро имеет вес (положительный или отрицательный). Вес любого пути или цикла p = (e ₁ ,...,e _k ) равен сумме весов ребер: w(p) = w(e ₁ ) + ... + w(e _k ). Средний вес p равен весу p, деленному на количество ребер в нем: w(p)/len(p). ^{[ необходима цитата ]}

Минимальный средний вес цикла в G — это минимум, по всем направленным циклам p в G, w(p)/len(p). Минимальный средний вес цикла — это любой цикл с минимальным средним весом. ^{[ необходима цитата ]}

Алгоритмы

Лоулер представил алгоритм для вычисления цикла минимального среднего веса, используя O(log |V| ) вызовов алгоритма для решения проблемы отрицательного цикла . ^[4] Существует такой алгоритм, который работает за время O( |V||E| ), поэтому общее время выполнения алгоритма Лоулера составляет O( |E||V| log |V| ).

Алгоритм Карпа

Карп ^[1] представил характеристику минимального среднего веса цикла и представил алгоритм, который работает за время O( |V||E| ). Аналогичный алгоритм можно использовать для нахождения максимального среднего веса цикла.

Пусть G — любой ориентированный граф, а s — фиксированная вершина в G. Для каждого неотрицательного целого числа k и каждой вершины v в G определим H _k (v) как максимальную стоимость пути длины k от s до v; если такого пути не существует, то H _k (v) = минус бесконечность.

Основная лемма гласит, что максимальный средний вес цикла G равен

(*) ${\displaystyle \max _{v\in V}\min _{0\leq k\leq n-1}{\frac {H_{n}(v)-H_{k}(v)}{n-k}}}$

Доказательство . Достаточно доказать лемму для случая, когда максимальный средний вес цикла равен 0. Это происходит потому, что добавление постоянного веса к каждому ребру добавляет одну и ту же константу как к максимальной средней стоимости цикла, так и к выражению в (*).

Предположим, что максимальный средний вес цикла равен 0. Тогда существует цикл со стоимостью ровно 0, но нет циклов с положительной стоимостью.

Сначала докажем, что (*) не больше 0. Поскольку G не имеет циклов с положительной стоимостью, для каждого узла v существует путь с максимальной стоимостью длиной меньше n от s до v. Пусть k _v будет длиной этого пути с максимальной стоимостью. Тогда H _kv (v) >= H _n (v), поэтому выражение внутри min в (*) не больше 0, когда k = k _v . Поскольку k _v <= n-1, минимум в (*) не больше 0. Поскольку это справедливо для каждого узла v, максимум в (*) также не больше 0.

Теперь докажем, что (*) не меньше 0. G имеет цикл с нулевой стоимостью; пусть w — некоторый узел в этом цикле. Пусть P ₀ — путь с максимальной стоимостью от s до w. Для каждого t >= 1 пусть P _t — конкатенация P ₀ с t копиями цикла; поскольку стоимость P _t равна стоимости P ₀ , это также путь с максимальной стоимостью от s до w. Каждый префикс пути с максимальной стоимостью также является путем с максимальной стоимостью от s до его конечной точки. Когда t достаточно велико, P _t имеет префикс длины n; это путь с максимальной стоимостью от s до некоторого узла w'. Тогда H _n (w') >= H _k (w') для всех k, поэтому выражение внутри min в (*) не меньше 0 для всех k, поэтому минимум в (*) не меньше 0. Взятие v=w' в maximum показывает, что максимум в (*) тоже не меньше 0.

Следовательно, когда максимальная средняя стоимость цикла равна 0, (*) равно 0, что достаточно для завершения доказательства.

Можно вычислить H _k с помощью динамического программирования за время O(|E||V|); затем можно найти максимальный средний вес цикла с помощью (*). Сам цикл можно найти следующим образом:

• Найдите максимизирующее v и минимизирующее k в (*).
• Так как результат для этого v и этого k конечен, то и H _n (v) и H _k (v) конечны. Это означает, что существует путь максимального веса длины n от s до v и путь максимального веса длины k от s до v. Следовательно, путь длины n содержит цикл длины nk; это цикл максимального среднего веса.

Новые алгоритмы

Дасдан и Гупта изучают цикл максимального среднего веса и представляют алгоритм, который, как доказано, всегда быстрее алгоритма Карпа. ^[2]

Альбрехт, Корте, Шитке и Виген ^[3] связывают проблему максимального среднего веса цикла с проблемой минимального баланса : найти потенциальную функцию, такую, что «слабины» всех ребер будут оптимально сбалансированы. Обе проблемы могут быть решены параметрическим алгоритмом кратчайшего пути . Они показывают, что параметрический кратчайший путь может быть использован для решения более общих вариантов этих проблем с ограничениями, которые имеют отношение к оптимизации графика часов логической микросхемы.

Смотрите также

• Отрицательный цикл

Ссылки

1. Карп, Ричард М. (1978-01-01). "Характеристика минимального цикла в орграфе". Дискретная математика . 23 (3): 309–311. doi :10.1016/0012-365X(78)90011-0. ISSN  0012-365X.
2. Dasdan, A.; Gupta, RK (1998). "Быстрые алгоритмы максимального и минимального среднего цикла для анализа производительности системы". IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems . 17 (10): 889–899. doi :10.1109/43.728912.
3. Альбрехт, Кристоф; Корте, Бернхард; Шитке, Юрген; Виген, Йенс (2002-11-15). "Цикл максимального среднего веса в орграфе и минимизация времени цикла логической микросхемы". Дискретная прикладная математика . 123 (1): 103–127. doi :10.1016/S0166-218X(01)00339-0. ISSN  0166-218X.
4. v. Golitschek, M. (1982-02-01). «Оптимальные циклы в графах с двойным весом и приближение двумерных функций одномерными». Numerische Mathematik . 39 (1): 65–84. doi :10.1007/BF01399312. ISSN  0945-3245.