Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Топ:
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Наиболее распространенные виды рака: Раковая опухоль — это самостоятельное новообразование, которое может возникнуть и от повышенного давления...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Средства для ингаляционного наркоза: Наркоз наступает в результате вдыхания (ингаляции) средств, которое осуществляют или с помощью маски...
Дисциплины:
2018-01-04 | 297 |
5.00
из
|
Заказать работу |
|
|
Рассмотрим здесь другую эвристику, которая сама по себе способна ускорить время работы алгоритма, а в сочетании с эвристикой сжатия путей и вовсе способна достигнуть практически константного времени работы на один запрос в среднем.
Эта эвристика заключается в небольшом изменении работы 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)
Док-во: следует тривиально из определения
Остаточная пропускная способность ребра – Cf(u,v) = c(u,v) – f(u,v). Если == 0 – ничего не можем пустить
|
Сделаем новый граф – остаточная сеть Gf(V, Ef)
Ef = {(u,v) из V*V | Cf(u,v) > 0}. |Ef|<=2|E|, т.к. т.к. существуют обратные ребра
Утв. Пусть G=(V,E) –транспортная сеть, Gf–остаточная. Пусть кроме потока fв G, есть потокf’ на Gf. Тогда 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в Gf
Cf(P) = min(Cf(u,v)|u,vизP) пропускная способность пути
fP(u,v) = …
… Cf(P), если (u,v) лежит в пути P
… - Cf(P), если (v,u) лежит в пути P
… 0, иначе
fP- дополнительный поток в G,| fP| = Cf(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. Gfне содержит увеличивающий путь
3. |f| = C(S,T), для некоторого разреза S,T
Эти утверждения эквивалентны
Док-во:
«1 è2»От противного. Пусть Gfимеет путь увеличивающий, и fp = f’–дополнительный поток. Значит f + f’ –потокв G.
f +f’ = |f| + |f’| - получили поток, больше maxпотока èпротиворечие
«2è3» Пусть Gf – не содержит путей из sв t. Тогда положим S = {v | в Gfесть путь из 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 поток
|
|
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!