Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
История развития пистолетов-пулеметов: Предпосылкой для возникновения пистолетов-пулеметов послужила давняя тенденция тяготения винтовок...
Топ:
Оснащения врачебно-сестринской бригады.
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Влияние предпринимательской среды на эффективное функционирование предприятия: Предпринимательская среда – это совокупность внешних и внутренних факторов, оказывающих влияние на функционирование фирмы...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2018-01-04 | 291 |
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 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!