Презентация Потоковые Алгоритмы. Лекция 7 онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Потоковые Алгоритмы. Лекция 7 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 59 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Презентации » Устройства и комплектующие » Потоковые Алгоритмы. Лекция 7
Оцените!
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:59 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:330.50 kB
- Просмотров:70
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№3 слайд
![Первая Теорема Менгера](/documents_6/f6d5925b93eb583e62a13543fc875888/img2.jpg)
Содержание слайда: Первая Теорема Менгера
Theorem 7.1 (Menger [1927] )
Пусть G ― граф (ориентированный или неориентированный), пусть s и t две вершины и k N. Тогда существует k реберно-непересекающихся s-t-путей, тогда и только тогда, когда после удаления любых k – 1 ребер t остается достижима из s.
№4 слайд
![Доказательство для орграфа](/documents_6/f6d5925b93eb583e62a13543fc875888/img3.jpg)
Содержание слайда: Доказательство (для орграфа)
Пусть (G, u, s, t) ― сеть с u ≡1, такая что t достижима после удаления любых k – 1 дуг.
Тогда минимальным s-t-разрез имеет пропускную способность по крайней мере k.
По теореме 6.5 существует целочисленный поток величины по крайней мере k.
По теореме 6.7 этот поток можно разложить в целочисленные потоки на s-t-путях.
Так как u ≡1 получаем по крайней мере k s-t-путей.
№7 слайд
![Вторая Теорема Менгера](/documents_6/f6d5925b93eb583e62a13543fc875888/img6.jpg)
Содержание слайда: Вторая Теорема Менгера
Theorem 7.2 (Menger [1927] )
Пусть G ― граф (ориентированный или неориентированный), пусть s и t две несмежные вершины и k N. Тогда существует k вершинно-непересекающихся s-t-путей, тогда и только тогда, когда после удаления любых k – 1 вершин (отличных от s и t) t остается достижима из s.
№9 слайд
![k-связные графы Граф с более](/documents_6/f6d5925b93eb583e62a13543fc875888/img8.jpg)
Содержание слайда: k-связные графы
Граф с более чем k вершинами и свойством, что он остается связным после удаления любого множества из k−1 вершины называется k-связным.
Граф с не менее чем двумя вершинами называется k-реберно-связным, если он остается связным после удаления любого множества из k−1 ребра.
№10 слайд
![Характеризация k-связных](/documents_6/f6d5925b93eb583e62a13543fc875888/img9.jpg)
Содержание слайда: Характеризация k-связных графов
Следствие 7.3 ( Уитни [1932] )
Граф G с не менее чем двумя вершинами является k-реберно-связным тогда и только тогда, когда для каждой пары s, t V(G) с s ≠ t существует k реберно-непересекающихся s-t-путей.
Граф G с не менее чем k вершинами является k- связным тогда и только тогда, когда для каждой пары s, t V(G) с s ≠ t существует k вершинно-непересекающихся s-t-путей.
№11 слайд
![Доказательство Первое](/documents_6/f6d5925b93eb583e62a13543fc875888/img10.jpg)
Содержание слайда: Доказательство
Первое утверждение прямо следует из теоремы 7.1.
Если граф не является k-связным, то существуют вершины s и t и множество X из k −1 вершины, такие, что в графе нет s-t-пути после удаления множества X.
в графе нет k вершинно-непересекающихся s-t-путей.
Пусть в G есть две вершины s и t для которых нет k вершинно-непересекающихся s-t-путей.
Если s и t не смежны, то теорема 7.2 существует множество X из k −1 вершины, такое, что после его удаления в G нет s-t-пути.
G не является k-связным.
№12 слайд
![Доказательство s и t смежны](/documents_6/f6d5925b93eb583e62a13543fc875888/img11.jpg)
Содержание слайда: Доказательство (s и t смежны)
Пусть s и t соединено множеством F параллельных ребер.
Тогда в G – F нет k – |F| вершинно-непересекающихся s-t-путей. (|F| ≥ 1)
Теорема 7.2 существует множество X из k − |F| – 1 вершины, такое, что после его удаления в G нет s-t-пути.
Существует вершина v, которая не достижима в G – F – X, либо из s, либо из t.
Пусть из t. Добавляя s к X, получаем разделяющее множество вершин мощности не более k – 1.
G не является k-связным.
№13 слайд
![Задача Ориентированные](/documents_6/f6d5925b93eb583e62a13543fc875888/img12.jpg)
Содержание слайда: Задача «Ориентированные реберно-непересекающиеся пути»
Дано: Два орграфа (G, H) на одном множестве вершин.
Найти семейство (Pf)fE(H) реберно-непересекающихся путей в G таких, что для каждого ребра(дуги) f = (t, s) в H, Pf ― s-t-путь.
Такое семейство называется решением (G, H).
№16 слайд
![Лемма Лемма . Пусть f , f ,](/documents_6/f6d5925b93eb583e62a13543fc875888/img15.jpg)
Содержание слайда: Лемма
Лемма 7.5
Пусть f1, f2, ... последовательность потоков, таких что fi+1 получается из fi увеличением потока вдоль Pi, где Pi ― кратчайший fi-увеличивающий путь. Тогда
a) |E(Pk)| ≤ | E(Pk+1)| для всех k.
b) |E(Pk)| + 2 ≤ |E(Pl)| для всех k < l таких, что Pk⋃Pl содержит пару обратных дуг.
№21 слайд
![E Pk E Pk для всех k](/documents_6/f6d5925b93eb583e62a13543fc875888/img20.jpg)
Содержание слайда: |E(Pk)| ≤ | E(Pk+1)| для всех k
Рассмотрим граф G1, который получается из Pk Pk+1 удалением обратных дуг. (Дуги, появляющиеся в обоих путях, берутся дважды).
Так как для любой дуги в E(Gfk)\E(Gfk+1) путь Pk должен содержать обратную ей дугу, то E(G1) E(Gfk).
Пусть H1 состоит из двух копий (t,s). Тогда G1+ H1 Эйлеров.
№23 слайд
![E Pk E Pk для всех k](/documents_6/f6d5925b93eb583e62a13543fc875888/img22.jpg)
Содержание слайда: |E(Pk)| ≤ | E(Pk+1)| для всех k
Рассмотрим граф G1, который получается из Pk Pk+1 удалением обратных дуг. (Дуги, появляющиеся в обоих путях, берутся дважды).
Так как для любой дуги в E(Gfk)\E(Gfk+1) путь Pk должен содержать обратную ей дугу, то E(G1) E(Gfk).
Пусть H1 состоит из двух копий (t,s). Тогда G1+ H1 Эйлеров.
Предложение 7.4 два реберно-непересекающихся пути Q1 и Q2.
E(G1) E(Gfk) Q1 и Q2 увеличивающие пути в Gfk.
№25 слайд
![E Pk E Pl для всех k lt l](/documents_6/f6d5925b93eb583e62a13543fc875888/img24.jpg)
Содержание слайда: |E(Pk)| + 2 ≤ |E(Pl)| для всех k < l таких, что Pk⋃Pl содержит пару обратных дуг
Пусть k < l такие, что для любого i, k < i < l Pi Pl не содержит обратных дуг.
Рассмотрим граф G1, который получается из Pk Pl удалением обратных дуг.
E(G1) E(Gfk)
E(Pk) E(Gfk), E(Pl) E(Gfl)
Любая дуга в E(Gfl)\E(Gfk) должна быть обратной дуге в одном из путей Pk, Pk+1,…, Pl–1.
По выбору k и l только Pk содержит обратные дуги.
2|E(Pk)| ≤ |E(Q1)| + |E(Q2)| ≤ |E(G1)| ≤
≤ |E(Pk)| + |E(Pk+1)| – 2.
№27 слайд
![Доказательство Пусть P , P ,](/documents_6/f6d5925b93eb583e62a13543fc875888/img26.jpg)
Содержание слайда: Доказательство
Пусть P1, P2,… увеличивающие пути, выбранные в алгоритме Эдмонса-Карпа.
По выбору γ на шаге 3 алгоритма, каждый увеличивающий путь содержит по крайней мере одну узкую дугу e: uf (e) = γ.
Пусть Pi1, Pi2 ,… последовательность увеличивающих путей, в которых дуга e узкая.
Тогда между Pij, Pij+1 должен быть увеличивающий путь Pк с обратной дугой к e.
№28 слайд
![Доказательство Лемма . b E](/documents_6/f6d5925b93eb583e62a13543fc875888/img27.jpg)
Содержание слайда: Доказательство
Лемма 7.5 b)
|E(Pij)| + 4 ≤ |E(Pk)| + 2 ≤ |E(Pij+1)| для всех j.
1 ≤ |E(Pij)| ≤ n – 1
не более n/4 увеличивающих путей, в которых дуга e узкая.
Так как любой увеличивающий путь содержит по крайней мере одну дугу из Ğ, как узкую, то не более (n|E(Ğ)|)/4 =(mn)/2 увеличивающих путей.
№32 слайд
![Функция расстояний](/documents_6/f6d5925b93eb583e62a13543fc875888/img31.jpg)
Содержание слайда: Функция расстояний
Определение 7.9
Даны сеть (G, u, s, t) и s-t-предпоток f . Функцией расстояния называется функция : V(G) → Z+ такая, что (t) = 0, (s) = n и (v) ≤ (w) + 1 для всех (v, w) E(Gf).
Дуга e = (v, w) E(Ğ) называется допустимой если
e E(Gf) и (v) = (w) + 1.
№33 слайд
![Идея алгоритма В процессе](/documents_6/f6d5925b93eb583e62a13543fc875888/img32.jpg)
Содержание слайда: Идея алгоритма
В процессе работы алгоритм строит последовательность предпотоков и задает функцию расстояния на них.
Алгоритм стартует с предпотока, который вдоль дуг, выходящих из s, равен их пропускным способностям и 0 вдоль остальных дуг и с функции расстояния (s) = n и (v) = 0 для всех v V(G) \{s}.
Алгоритм останавливается, когда в сети нет активных вершин.
№34 слайд
![Алгоритм Проталкивания](/documents_6/f6d5925b93eb583e62a13543fc875888/img33.jpg)
Содержание слайда: Алгоритм Проталкивания Предпотока
Input: Сеть (G, u, s, t).
Output: максимальный s-t-поток f.
Set (s) = n и (v) = 0 для всех v V(G) \{s}.
Set f(e) := u(e) для каждого e δ+(s). Set f(e) := 0 для каждого e E(G) \δ+(s).
While существуют активные вершины do:
Пусть v ― активная вершина
If нет допустимой дуги e δ+(v)
then Relabel(v)
else Push(e) ( e δ+(v) произвольная допустимая дуга )
Push(e): 1) Set γ:= min{exf (v), uf (e)}, где v ― вершина с e δ+(v).
2) Увеличим f вдоль e на γ.
Relabel(v): Set (v):= min{ (w)+1: e = (v, w) E(Gf)}. ( (v) ↑)
№37 слайд
![Доказательство Предпоток](/documents_6/f6d5925b93eb583e62a13543fc875888/img36.jpg)
Содержание слайда: Доказательство
Предпоток изменяется только в процедуре Push.
Так как γ:= min{exf (v), uf (e)}, то после процедуры Push f остается предпотоком.
Так как (v):= min{ (w) + 1: e = (v, w) E(Gf)}, то остается функцией расстояния после процедуры Relable.
Покажем, что после процедуры Push(e) также остается функцией расстояния относительно нового предпотока.
№38 слайд
![Доказательство Необходимо](/documents_6/f6d5925b93eb583e62a13543fc875888/img37.jpg)
Содержание слайда: Доказательство
Необходимо показать, что (a) ≤ (b) + 1 для всех новых дуг (a, b) в Gf .
Поскольку в процедуре Push(e) поток изменяется только вдоль дуги e = (v, w), то новой в Gf может быть только одна дуга (w, v), обратная к e.
Так как e была допустимой дугой, то (w) = (v) – 1 ≤ (v) + 1.
№43 слайд
![Число вызовов процедуры](/documents_6/f6d5925b93eb583e62a13543fc875888/img42.jpg)
Содержание слайда: Число вызовов процедуры Relabel
Лемма 7.13
a) Для каждого v V(G), (v) строго возрастает при каждом выполнении процедуры Relabel(v), и никогда не убывает.
На любом шаге алгоритма, (v) ≤ 2n – 1 для всех v V(G).
Общее число вызовов процедуры Relabel не превышает 2n2.
№44 слайд
![Процедура Push Процедура Push](/documents_6/f6d5925b93eb583e62a13543fc875888/img43.jpg)
Содержание слайда: Процедура Push
Процедура Push(e) называется проталкиванием, примененным к вершине v. Проталкивание называется насыщающим, если в результате ребро e становится насыщенным, то есть если uf (e) обращается в нуль (ребро исчезает из остаточного графа); в противном случае проталкивание считают ненасыщающим.
№47 слайд
![list v и curr v Для получения](/documents_6/f6d5925b93eb583e62a13543fc875888/img46.jpg)
Содержание слайда: list(v) и curr(v)
Для получения оценки O(n3) на число ненасыщающих проталкиваний мы должны выбрать порядок в котором применяются процедуры Push и Relabel.
Как обычно, предположим, что орграф G задан листом смежности, то есть для каждой вершины v указан список list(v) дуг выходящих из v. При этом указатель curr(v) указывает на один элемент в списке list(v) (вначале на первый элемент в списке).
№48 слайд
![Алгоритм Голдберга-Тарьяна](/documents_6/f6d5925b93eb583e62a13543fc875888/img47.jpg)
Содержание слайда: Алгоритм Голдберга-Тарьяна
Input: Сеть (G, u, s, t).
Output: Максимальный s-t-поток f.
Set (s) = n и (v) = 0 для всех v V(G) \{s}.
Set f(e) := u(e) для каждого e δ+(s). Set f(e) := 0 для каждого e E(G) \δ+(s).
For всех v V(G) do: curr(v):= первый элемент list(v)
Set Q:={v V(G): v ― активная }. If Q = ø then stop.
For всех v Q do: Discharge(v).
Go to 4.
Discharge(v)
Set e:= curr(v).
If e допустимо then Push(e) else do:
If e последнее ребро в list(v) then Relabel(v),
curr(v):= первый элемент list(v), return,
else curr(v):= следующий элемент list(v).
3. If exf (v) > 0 then go to 1.
№51 слайд
![Доказательство Вершина v](/documents_6/f6d5925b93eb583e62a13543fc875888/img50.jpg)
Содержание слайда: Доказательство
Вершина v всегда активна перед выполнением шага 2 процедуры Discharge(v).
Процедура Discharge вызывает процедуру Relabel только, если v активна.
Осталось показать, что в момент вызова Relabel (v) ≤ (w) .
Рассмотрим произвольную дугу e =(v,w) E(Gf).
С момента предыдущего вызова Relabel для вершины v весь список ее дуг был просмотрен. В частности, указатель curr (v) указывал и на дугу e. Поскольку, он ее покинул, то
либо (v) < (w) + 1
либо e E(Gf) и появилась в Gf позднее, когда проталкивался поток по дуге =(w,v) и (w) = (v) + 1 > (v).
№53 слайд
![Доказательство Так как min](/documents_6/f6d5925b93eb583e62a13543fc875888/img52.jpg)
Содержание слайда: Доказательство
Так как γ:= min{exf (v), uf (e)}, то на каждой итерации шага 5 может быть не более одного ненасыщающего проталкивания для каждой вершины.
Покажем, что число итераций шага 5 ≤ 4n2.
Разделим все итерации на итерации с запуском Relabel и без запуска.
Лемма 7.13 с) не более 2n2 итераций с Relabel
№54 слайд
![Число итераций шага без](/documents_6/f6d5925b93eb583e62a13543fc875888/img53.jpg)
Содержание слайда: Число итераций шага 5 без Relabel
Пусть Ψ = max{ (v) : v - активная}
Ψ = 0, если нет активных вершин.
На каждой итерации без Relabel Ψ уменьшается минимум на 1.
Пусть w – активная вершина после шага 5 без Relabel. Так как шаг 5 выполнялся для всех активных на тот момент вершин, то w стала активной в процессе этой итерации шага 5 по причине проталкивания потока по дуге (v,w).
v была активной и (v) = (w) + 1
В начале и в конце алгоритма Ψ = 0 число итераций без Relabel не больше суммарной величины Δ на которое Ψ увеличивается в течение работы алгоритма.
Так как увеличение Ψ соответствует увеличению (v) в результате Relabel, то Δ ≤ 2n2 (по Лемме 7.13 ).
Скачать все slide презентации Потоковые Алгоритмы. Лекция 7 одним архивом:
Похожие презентации
-
Методы улучшения алгоритмов сортировок. Лекция 7
-
Алгоритмы с возвратом. Лекция 20
-
Оценка сложности вычислительных алгоритмов. Лекция 22
-
Алгоритмы сортировки. Лекция 13
-
Основы программирования ФИСТ. Двухмерные массивы. Базовые алгоритмы. Лекция 10
-
Анализ и оценка времени выполнения параллельных алгоритмов. (Лекция 4)
-
Алгоритмы и структуры данных. Иерархические структуры данных. Лекция 3
-
Алгоритмы и структуры данных. Лекция 2
-
Теория алгоритмов. Сортировка массива. (Лекция 17)
-
Анализ алгоритмов. (Лекция 16)