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

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

Эта эвристика заключается в небольшом изменении работы 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) = (сумма по vf(u,v)) + (сумма по vf’(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) –его поток (сумма потоков по ребрам, пересекающим разрех)

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

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

Доказательство: сумма потоков из 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)