imslavko's blog

By imslavko, 7 years ago, In Russian,

Здавствуйте! Все знают, что |MinCut| = |MaxFlow| в сети. Кто знаком с темой может прокрутить вниз, там вопрос.

[newbie mode] Как найти какие именно ребра являются разрезом? Тут вроде тоже все понятно, разделим множество вершин на два множества: S — множество достижимых вершин из истока по ненасыщенным ребрам и T = V / S. Ребра, которые соединяют вершины из разных множеств и будут одним из ответов.

Как найти вершинный разрез? Учили так: разделим каждую вершину v на 2 вершины: v1 для входящих и v2 для выходящих. Сделаем так же ребро v1 -  > v2 с пропускной способностью 1. Далее найдем макс.поток и размер потока будет равен минимальному вершинному разрезу. Но как теперь найти ответ?

В задаче на USACO trainings (telecow, 5.4.5) проходит такое решение для |V| ≤ 100, |E| ≤ 600:

Будем по очереди удалять ребро между v1 и v2 для каждой вершины и будем заного находить поток. Если поток уменьшился на единицу, то эта вершина входит в раздрез.

Мне не очень понравилось это решение, ведь делая это алгоритмом Диници, это будет работать не мало: O((|V||E|)2), где кол-во вершин увеличивается в 2 раза, а кол-во ребер примерно в 4 раза(обратные ребра и по 2 ребра на каждое, так как ребра не ориентированны), получается где-то 100 * 2 * 600 * 4 в квадрате итераций? Сначала я испугался такой цифры, но вспомнив, что ребра с пропускной способностью в единицу делают ее еще быстрее, то выходит помножиное на |V| вызовов, то выходит около 6 * 106, что приемлемо. [/newbie mode]

Но как находить вершинный разрез, когда вершин и ребер еще больше? Есть ли более оптимальное решение?

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it