Наивная реализация

Мы уже можем написать первую реализацию системы непересекающихся множеств. Она будет довольно неэффективной, но затем мы улучшим её с помощью двух приёмов, получив в итоге почти константное время работы.

Итак, вся информация о множествах элементов хранится у нас с помощью массива  .

Чтобы создать новый элемент (операция  ), мы просто создаём дерево с корнем в вершине  , отмечая, что её предок — это она сама.

Чтобы объединить два множества (операция  ), мы сначала найдём лидеров множества, в котором находится  , и множества, в котором находится  . Если лидеры совпали, то ничего не делаем — это значит, что множества и так уже были объединены. В противном случае можно просто указать, что предок вершины   равен   (или наоборот) — тем самым присоединив одно дерево к другому.

Наконец, реализация операции поиска лидера ( ) проста: мы поднимаемся по предкам от вершины  , пока не дойдём до корня, т.е. пока ссылка на предка не ведёт в себя. Эту операцию удобнее реализовать рекурсивно (особенно это будет удобно позже, в связи с добавляемыми оптимизациями).

Эвристика сжатия пути

Эта эвристика предназначена для ускорения работы  .

Она заключается в том, что когда после вызова   мы найдём искомого лидера   множества, то запомним, что у вершины   и всех пройденных по пути вершин — именно этот лидер  . Проще всего это сделать, перенаправив их   на эту вершину  .

Таким образом, у массива предков   смысл несколько меняется: теперь это сжатый массив предков, т.е. для каждой вершины там может храниться не непосредственный предок, а предок предка, предок предка предка, и т.д.

С другой стороны, понятно, что нельзя сделать, чтобы эти указатели   всегда указывали на лидера: иначе при выполнении операции   пришлось бы обновлять лидеров у   элементов.

Таким образом, к массиву   следует подходить именно как к массиву предков, возможно, частично сжатому.

Эвристика объединения по рангу

Рассмотрим здесь другую эвристику, которая сама по себе способна ускорить время работы алгоритма, а в сочетании с эвристикой сжатия путей и вовсе способна достигнуть практически константного времени работы на один запрос в среднем.

Эта эвристика заключается в небольшом изменении работы Union: если в наивной реализации то, какое дерево будет присоединено к какому, определяется случайно, то теперь мы будем это делать на основе рангов.

Есть два варианта ранговой эвристики: в одном варианте рангом дерева называется количество вершин в нём, в другом — глубина дерева (точнее, верхняя граница на глубину дерева, поскольку при совместном применении эвристики сжатия путей реальная глубина дерева может уменьшаться).

В обоих вариантах суть эвристики одна и та же: при выполнении  Union будем присоединять дерево с меньшим рангом к дереву с большим рангом.

Это затем, чтобы быстрее находить лидера

Потоки, Форда-Фалкерсона.

В теории оптимизации и теории графов, задача о максимальном потоке заключается в нахождении такого потока потранспортной сети, что сумма потоков из истока, или, что то же самое, сумма потоков в сток максимальна.

S – исток, T - сток

Поток - функция f: V*V -> R такая, что

1. f(u,v) <= c(u,v), где C – ограничения на ребрах

2. f(u,v) = - f(v,u)

3. для любой вершины U, кроме потока и истока – (сумма по всем V из f(U,V)) = 0

Величина потока - |f| = сумма по всем V из f(S,V)

Задача: нужно максимизировать |f|

Если X,Y – подмножества V, то f(X,Y) = (сумма по всем x из X(сумма по всем y из Y(f(x,y)))

Лемма.

1. X – подмножество V, f(X,X) = 0

2. f(X,Y) = -f(Y,X)

3. X не пересекается с Y, f(X+Y,Z) = f(X,Z) + f(Y,Z)

Док-во: следует тривиально из определения

Остаточная пропускная способность ребра – C_f(u,v) = c(u,v) – f(u,v). Если == 0 – ничего не можем пустить

Сделаем новый граф – остаточная сеть G_f(V, E_f)

E_f = {(u,v) из V*V | C_f(u,v) > 0}. |E_f|<=2|E|, т.к. т.к. существуют обратные ребра

Утв. Пусть G=(V,E) – транспортная сеть, G_f – остаточная. Пусть кроме потока f в G, есть поток f’ на G_f. Тогда f + f'’- тоже поток на G и |f + f’| = |f| + |f’|

Док-во:

1. (f + f’)(u,v) = f(u,v) + f’(u,v) = -f(v,u) – f’(v,u) = -(f+f’)(v,u)

2. (f + f’)(u,v) = f(u,v) + f’(u,v) <= f(u,v) + (c(u,v) – f(u,v)) = c(u,v)

3. Сумма по v (f + f’)(u,v) = (сумма по v f(u,v)) + (сумма по v f’(u,v)) = 0 + 0 = 0

Значит f+f’ – поток в G

|f + f’| = |f| + |f’| вытекает из первого равенства в 3-ем. ЧТД

Путь P – увеличивающий, если это простой путь s->t в G_f

C_f(P) = min(C_f(u,v)|u,v из P) пропускная способность пути

f_P(u,v) = …

… C_f(P), если (u,v) лежит в пути P

… - C_f(P), если (v,u) лежит в пути P

… 0, иначе

f_P- дополнительный поток в G, | f_P | = C_f(P) > 0

Если S,T – разрез, то f(S,T) – его поток (сумма потоков по ребрам, пересекающим разрех)

min Cut – такой разрез сети, в котором его пропускная способность через этот разрез минимальна

Теорема Форда-Фалкерсона. Величина максимального потока равна пропускной способности минимального разреза.

Доказательство: сумма потоков из s равна потоку через любой разрез, в том числе минимальный, следовательно, не превышает пропускной способности минимального разреза. Следовательно, максимальный поток не больше пропускной способности минимального разреза. Осталось доказать, что он и не меньше её. Пускай поток максимален. Тогда в остаточной сети сток не достижим из источника. Пусть A - множество вершин, достижимых из источника в остаточной сети, B - недостижимых. Тогда, поскольку , , то (A,B) является разрезом. Кроме того, в остаточной сети не существует ребра (a,b) с положительной пропускной способностью, такого что , , иначе бы b было достижимо из s. Следовательно, в исходной сети поток по любому такому ребру равен его пропускной способности, и, значит, поток через разрез (A,B) равен его пропускной способности. Но поток через любой разрез равен суммарному потоку из источника, который в данном случае равен максимальному потоку. С другой стороны, пропускная способность любого разреза не меньше пропускной способности минимального разреза. Комбинируя эти три утверждения, получаем, что максимальный поток не меньше пропускной способности минимального разреза. Теорема доказана.

Значит, для любого разреза величина потока не может превышать minCut

Утв. G=(V,E). f – поток

1. f – max поток в G

2. G_f не содержит увеличивающий путь

3. |f| = C(S,T), для некоторого разреза S,T

Эти утверждения эквивалентны

Док-во:

«1 2» От противного. Пусть G_f имеет путь увеличивающий, и f_p = f’– дополнительный поток. Значит f + f’ – поток в G.

f +f’ = |f| + |f’| - получили поток, больше max потока  противоречие

«2 3» Пусть G_f – не содержит путей из s в t. Тогда положим S = {v | в G_f есть путь из S в v}

T = V – S

Для любых u из S и v из T – f(u,v) = c(u,v) – т.к. пустить путь нельзя, ведь v – недостижимо из s. |f| = f(S,T) = c(S,T)

«3  1» |f| <= c(S,T), для любого потока и разреза. А у нас |f| = f(S,T) = c(S,T) – значит он max поток

Форд-Фалкерсон (Ford-Falkerson)

Решает задачу нахождения максимального потока транспортной сети. Алгоритм:

1. Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.

2. В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.

3. Пускаем через найденный путь (он называется увеличивающим путём или увеличивающей цепью) максимально возможный поток:

1. На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью .

2. Для каждого ребра на найденном пути увеличиваем поток на , а в противоположном ему — уменьшаем на .

3. Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.

1. Возвращаемся на шаг 2

Алгоритм (формально): Вход: Граф  с пропускной способностью , источник  и сток Выход: Максимальный поток  из  в для всех ребер

2. Пока есть путь  из  в  в , такой что  для всех ребер :

1. Найти

2. Для каждого ребра

Сложность: O(E*f), т.к. поток увеличивется максимум на 1

Алгоритм Эдмонса-Карпа- то же самое но поиск пути – BFS (кратчайший) – O(VE^2)