Сетевой поток: добавление нового края

Question

В последнее время в одном из вычислений меня попросили разработать алгоритм, for a network having V vertices and E edges, if by adding an edge (it's capacity should be 1) results in increase the maximum flow. то есть мы должны разработать такой алгоритм, чтобы найти такие ребра.

Алгоритм должен быть быстрее, чем O(|E|* h(|V||E|)), где h(|V||E|) - время, необходимое для вычисления максимального потока.

Заранее спасибо.Дайте мне знать, если неясно.

Answer 1

(исправленная версия того, что сказал Филипп.) Рассчитайте максимальный поток.Извлечь некапитативный направленный граф, состоящий из дуг с положительной остаточной емкостью.Добавление определенной дуги увеличивает максимальный поток в том и только в том случае, если существуют пути от источника к хвосту и от головы к раковине, т. Е. Введение дуги создает увеличивающийся путь.

В вашем примере{s->a, a->b, a->c, a->d, b->t, c->t, d->t}, максимальный поток равен s-3>a, a-1>b, a-1>c, a-1>d, b-1>t, c-1>t, d-1>t, а остаточный график имеет каждую обратную дугу {a->s, b->a, c->a, d->a, t->b, t->c, t->d}.Вершины, достижимые от s, равны {s}, а вершины, достижимые от t, равны {t}, поэтому единственная отдельная дуга, которая может увеличить максимальный поток, составляет s->t.

Answer 2

Другое решение может быть следующим:

Шаг 1. Найдите минимальный разрез, содержащий минимальное количество вершин (назовите его вершины Vmin).

Шаг 2. Найдите минимальный разрез, содержащий максимальное количество вершин (назовите его вершины Vmax).

Step3. Найдите все ребра, которые связывают Vmin и V \ Vmax, но не являются частью E.

Почему это работает? (I) Добавление нового ультрафиолетового края хорошо, если оно содержится в каждом минимальном разрезе (если быть точным: если оно связывает различные компоненты минимального разреза) и (II) «группа» минимальных разрезов близка к объединению и пересечение.

Сложность:

Для шага 1,2 я нашел следующий хороший алгоритм: Как найти минимальное сечение на графике с использованием алгоритма максимального потока? . Это может быть применено, чтобы найти минимальный разрез с минимальными и максимальными вершинами. Кажется, это работает в h (| E || V |) + O (| V | ^ 3), где O (| V | ^ 3) приходит из BFS, когда вы проверяете, закончена ли BFS (то есть, больше нет новых остаточный смежный существует).

Для шага 3, где O (| Vmin | * | V \ Vmax |), то есть O (| V | ^ 2).

Следовательно Step1,2,3 = h (| E || V |) + O (| V | ^ 3)

Обратите внимание, что это всего лишь быстрый набросок:)

Answer 3

Я думаю, что решение может быть:

1. Алгоритм максимального потока при первом запуске.Теперь у нас есть остаточный граф G.
2. Затем мы находим все ребра (u, v) такие, что в остаточном графе G мы можем найти путь от s до u и путь от v до t.

Сложность в худшем случае составляет O (| V | ^ 2 (| V | + | E |) + h (| V || E |)).

Answer 4

Согласно теореме Max-Flow-Min-Cut-1 [1], максимальный поток в сети равен сумме всех весов ребер в минимальном срезе. Следовательно, решение может выглядеть так:

• найти минимальный срез с общим весом кромки X, используя, например, алгоритм Эдмондса-Карпа, специализация алгоритма Форда-Фулкерсона. Согласно [1], это в O(h|V||E|).
• добавить ребро, которое соединяет узлы, которые принадлежат отдельным разделам разреза (S, S'), т.е. добавить ребро (u,v), где u в S и v в S'.
• повторять до тех пор, пока не останется больше порезов с общим весом кромки X.