Алгоритм для поиска мин. разреза?

Question

[floppa322]

Всегда казалось, что чтобы найти минимальный разрез достаточно просто запустить по остаточной сети любой обход и все достижимые вершины взять в S, а остальные в T. Собственно, что и предлагают мужики с CSSE:

The minimum cut is a partition of the nodes into two groups.

Once you find the max flow, the minimum cut can be found by creating the residual graph, and when traversing this residual network from the source to all reachable nodes, these nodes define one part of the partition. Call this partition A
. The rest of the nodes (the unreachable ones) can be called B
. The size of the minimum cut is the sum of the weights of the edges in the original network which flow from a node in A
to a node in B
.

Ну и контрпример:

Фиолетовые рёбра - насыщенные рёбра из остаточной сети, чёрные - остальные. Очевидно, что разрез = 1, однако этот алгоритм нашёл бы разрез = 2 (обозначил пунктиром вершиныиз S).

Видимо алгоритм для разреза чуть сложнее, чем тот с CSSE: нужно запусттить в ост. сети обход из s, затем по обратным рёбрам запустить обход из t, а вершины, куда не дошли оба обхода удалить, тогда будет: V \ V (недостижимые в обоих обходах) = V', S = достижимые из s, T = V' \ S

Вопрос довольно тупой, просто всегда казалось, что достаточно запустить 2 обхода

Answer 1

[Wataru]

У вас ошибка в понимании остаточной сети. Раз фиолетовые ребра насыщены, то на самом деле в остаточной сети есть обратные им ребра. И вершина v отлично найдется обходом из s.

Без этих обратных ребер алгоритм поиска потока не работает, ведь у него не будет возможности "отменять" потоки.
Например в графе:

________    
  a-b-c
 /  |   \
s   |     t
\   v   /
  d-e-f

Если сначала найдется поток по пути s-a-b-e-f-t, то дальше единственный способ его дополнить - это взять путь s-d-e-b-c-t, и надо будет "отменить" поток по перекрестному ребру b-e.

Comments

[floppa322]

Да, точно, забыл про обратные рёбра, спасибо