🗊Презентация Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе

Категория: Математика
Нажмите для полного просмотра!
Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №1Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №2Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №3Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №4Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №5Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №6Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №7Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №8Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №9Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №10Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №11Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №12Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №13Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №14Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №15Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №16Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №17Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №18Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №19Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №20Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №21Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №22Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №23Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №24Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №25Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №26Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №27Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №28Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №29Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе, слайд №30
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Лекция 6. Потоки в сетях. Теорема о максимальном потоке и минимальном разрезе. Доклад-сообщение содержит 30 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Потоки в сетях Теорема о максимальном потоке и минимальном разрезе Лекция 6
Описание слайда:
Потоки в сетях Теорема о максимальном потоке и минимальном разрезе Лекция 6

Слайд 2


Сеть Ориентированный граф G с пропускными способностями дуг u: E(G)→ R+ и две выделенные вершины s (источник) и t (сток). Четверка (G, u, s, t) называется сетью. Главная задача ― транспортировать так много единиц продукта, как возможно, одновременно из s в t. Решение этой задачи назовем максимальным потоком.
Описание слайда:
Сеть Ориентированный граф G с пропускными способностями дуг u: E(G)→ R+ и две выделенные вершины s (источник) и t (сток). Четверка (G, u, s, t) называется сетью. Главная задача ― транспортировать так много единиц продукта, как возможно, одновременно из s в t. Решение этой задачи назовем максимальным потоком.

Слайд 3


Поток Определение 6.1. Дан орграф G с пропускными способностями (вместимостями) u: E(G) → R+, потоком называется функция f : E(G) → R+ с f(e) ≤ u(e) для всех e  E(G). Будем говорить, что f удовлетворяет закону сохранения в вершине v, если Поток, удовлетворяющий закону сохранения в каждой вершине называется циркуляцией.
Описание слайда:
Поток Определение 6.1. Дан орграф G с пропускными способностями (вместимостями) u: E(G) → R+, потоком называется функция f : E(G) → R+ с f(e) ≤ u(e) для всех e  E(G). Будем говорить, что f удовлетворяет закону сохранения в вершине v, если Поток, удовлетворяющий закону сохранения в каждой вершине называется циркуляцией.

Слайд 4


s-t-Поток Дана сеть (G, u, s, t), s-t-потоком называется поток, удовлетворяющий закону сохранения во всех вершинах кроме s и t. Определим величину s-t-потока функцией
Описание слайда:
s-t-Поток Дана сеть (G, u, s, t), s-t-потоком называется поток, удовлетворяющий закону сохранения во всех вершинах кроме s и t. Определим величину s-t-потока функцией

Слайд 5


Задача «Максимальный Поток» Дано: Сеть (G, u, s, t). Найти s-t-поток максимальной величины.
Описание слайда:
Задача «Максимальный Поток» Дано: Сеть (G, u, s, t). Найти s-t-поток максимальной величины.

Слайд 6


s-t-Разрез s-t-разрез в графе ― разрез Xдля некоторогоX V(G) с s  X и t  V(G)\ X. пропускной способностью s-t-разреза называется сумма вместимостей его дуг (ребер). Под минимальным s-t-разрезом в (G,u,s,t) мы понимаем s-t-разрез с минимальной пропускной способностью (относительно u) в G.
Описание слайда:
s-t-Разрез s-t-разрез в графе ― разрез Xдля некоторогоX V(G) с s  X и t  V(G)\ X. пропускной способностью s-t-разреза называется сумма вместимостей его дуг (ребер). Под минимальным s-t-разрезом в (G,u,s,t) мы понимаем s-t-разрез с минимальной пропускной способностью (относительно u) в G.

Слайд 7


s-t-Поток и s-t-разрез Лемма 6.2 Для всех A  V(G) таких, что s  A, t ∉ A, и любого s-t-потока f.
Описание слайда:
s-t-Поток и s-t-разрез Лемма 6.2 Для всех A  V(G) таких, что s  A, t ∉ A, и любого s-t-потока f.

Слайд 8


Доказательство (а)
Описание слайда:
Доказательство (а)

Слайд 9


s-t-Поток и s-t-разрез Лемма 6.2 Для всех A  V(G) таких, что s  A, t ∉ A, и любого s-t-потока f.
Описание слайда:
s-t-Поток и s-t-разрез Лемма 6.2 Для всех A  V(G) таких, что s  A, t ∉ A, и любого s-t-потока f.

Слайд 10


Обратные дуги и остаточные пропускные способности Определение 6.3 Для орграфа G определим Ğ:=(V(G), E(G)U{ĕ: e E(G)}), где для каждого e = (v,w) E(G) определим ĕ как новое ребро из w в v. Назовем ĕ обратной дугой к e и, наоборот. Заметим, что если e = (v,w), e′ = (w,v), то ĕ и e′ два параллельных ребра в Ğ. Дан орграф G с вместимостями u: E(G) → R+ и поток f, определим остаточные пропускные способности uf : E(Ğ) → R+ как uf (e):= u(e) − f (e) и uf (ĕ) := f (e) для всех e E(G). Остаточным графом Gf называется граф (V(G), {e E(Ğ): uf (e) > 0}).
Описание слайда:
Обратные дуги и остаточные пропускные способности Определение 6.3 Для орграфа G определим Ğ:=(V(G), E(G)U{ĕ: e E(G)}), где для каждого e = (v,w) E(G) определим ĕ как новое ребро из w в v. Назовем ĕ обратной дугой к e и, наоборот. Заметим, что если e = (v,w), e′ = (w,v), то ĕ и e′ два параллельных ребра в Ğ. Дан орграф G с вместимостями u: E(G) → R+ и поток f, определим остаточные пропускные способности uf : E(Ğ) → R+ как uf (e):= u(e) − f (e) и uf (ĕ) := f (e) для всех e E(G). Остаточным графом Gf называется граф (V(G), {e E(Ğ): uf (e) > 0}).

Слайд 11


Остаточный граф
Описание слайда:
Остаточный граф

Слайд 12


Увеличивающий Путь Даны поток f и путь (или цикл) P в Gf , увеличение f вдоль P на γ означает следующее для каждой e  E(P): если e  E(G), то увеличим f(e) на γ , если e = ĕ0, e0  E(G), то уменьшим f(e0) на γ. Дана сеть (G, u, s, t) и s-t-поток f, f–увеличивающим путем называется s-t-путь в остаточном графе Gf.
Описание слайда:
Увеличивающий Путь Даны поток f и путь (или цикл) P в Gf , увеличение f вдоль P на γ означает следующее для каждой e  E(P): если e  E(G), то увеличим f(e) на γ , если e = ĕ0, e0  E(G), то уменьшим f(e0) на γ. Дана сеть (G, u, s, t) и s-t-поток f, f–увеличивающим путем называется s-t-путь в остаточном графе Gf.

Слайд 13


Увеличивающий Путь
Описание слайда:
Увеличивающий Путь

Слайд 14


Алгоритм Форда-Фалкерсона Input: Сеть (G, u, s, t). Output: s-t-поток f максимальной величины. Положим f(e) = 0 для всех e E(G). Найти f-увеличивающий путь P. If такого пути нет then stop. Вычислить Увеличить f вдоль P на γ и go to 2.
Описание слайда:
Алгоритм Форда-Фалкерсона Input: Сеть (G, u, s, t). Output: s-t-поток f максимальной величины. Положим f(e) = 0 для всех e E(G). Найти f-увеличивающий путь P. If такого пути нет then stop. Вычислить Увеличить f вдоль P на γ и go to 2.

Слайд 15


Замечание Найти увеличивающий путь легко (любой s-t-путь в Gf). Если выбирать произвольный увеличивающий путь в Gf , то Существует пример с иррациональными вместимостями дуг, когда алгоритм никогда не остановится. Существует пример с целыми вместимостями дуг, на котором алгоритм производит экспоненциальное от размера входа число увеличений.
Описание слайда:
Замечание Найти увеличивающий путь легко (любой s-t-путь в Gf). Если выбирать произвольный увеличивающий путь в Gf , то Существует пример с иррациональными вместимостями дуг, когда алгоритм никогда не остановится. Существует пример с целыми вместимостями дуг, на котором алгоритм производит экспоненциальное от размера входа число увеличений.

Слайд 16


Пример c бесконечным числом итераций (все линии представляют ребра, то есть поток может идти в оба направления)
Описание слайда:
Пример c бесконечным числом итераций (все линии представляют ребра, то есть поток может идти в оба направления)

Слайд 17


Упражнение 6.1 Показать, что для сети из предыдущего примера алгоритм Форда-Фалкерсона может работать бесконечно долго.
Описание слайда:
Упражнение 6.1 Показать, что для сети из предыдущего примера алгоритм Форда-Фалкерсона может работать бесконечно долго.

Слайд 18


Целочисленный пример c экспоненциальным числом итераций
Описание слайда:
Целочисленный пример c экспоненциальным числом итераций

Слайд 19


Характеризация максимального потока Теорема 6.4 s-t-Поток f является максимальным тогда и только тогда, когда в Gf не существует f-увеличивающего пути.
Описание слайда:
Характеризация максимального потока Теорема 6.4 s-t-Поток f является максимальным тогда и только тогда, когда в Gf не существует f-увеличивающего пути.

Слайд 20


Доказательство Пусть в Gf не существует f-увеличивающего пути.  t не достижимо в Gf из s. Пусть R множество вершин, достижимых из s в Gf. По определению Gf имеем f(e) = u(e) для всех e  +(R), и f(e) = 0 для всех e  –(R). Лемма 6.2 a)  Лемма 6.2 b)  f ― максимальный поток.
Описание слайда:
Доказательство Пусть в Gf не существует f-увеличивающего пути.  t не достижимо в Gf из s. Пусть R множество вершин, достижимых из s в Gf. По определению Gf имеем f(e) = u(e) для всех e  +(R), и f(e) = 0 для всех e  –(R). Лемма 6.2 a)  Лемма 6.2 b)  f ― максимальный поток.

Слайд 21


Замечание В частности, из доказательства следует, что каждому максимальному потоку соответствует s-t-разрез, пропускная способность которого равна величине потока. Вместе с леммой 6.2 b) это влечет центральный результат теории потоков в сети.
Описание слайда:
Замечание В частности, из доказательства следует, что каждому максимальному потоку соответствует s-t-разрез, пропускная способность которого равна величине потока. Вместе с леммой 6.2 b) это влечет центральный результат теории потоков в сети.

Слайд 22


Максимальный поток и минимальный разрез Теорема 6.5 (Форд, Фалкерсон [1956], Элиас, Файнштайн, Шэннон [1956] ) Величина максимального s-t-потока равна пропускной способности минимального s-t-разреза.
Описание слайда:
Максимальный поток и минимальный разрез Теорема 6.5 (Форд, Фалкерсон [1956], Элиас, Файнштайн, Шэннон [1956] ) Величина максимального s-t-потока равна пропускной способности минимального s-t-разреза.

Слайд 23


Теорема о целочисленном потоке Следствие 6.6 Если пропускные способности дуг в сети целые числа, то существует целочисленный максимальный поток.
Описание слайда:
Теорема о целочисленном потоке Следствие 6.6 Если пропускные способности дуг в сети целые числа, то существует целочисленный максимальный поток.

Слайд 24


Упражнение 6.2 Поcтроить пример сети, в которой вместимости дуг целые числа, и существует нецелочисленный максимальный поток.
Описание слайда:
Упражнение 6.2 Поcтроить пример сети, в которой вместимости дуг целые числа, и существует нецелочисленный максимальный поток.

Слайд 25


Теорема о Декомпозиции Потока Теорема 6.7 (Фалкерсон [1962] ) Пусть (G, u, s, t) ― сеть и f ― s-t-поток в G. Тогда существует семейство P s-t-путей и семейство C циклов в G с весами w: P UC → R+ таких, что f(e) = ΣPP UC: e E(P)w(P) для всех e E(G), ΣPP w(P) = value( f ), и |P | + |C | ≤ | E(G)|. Более того, если f ― целочисленный поток, то w может быть выбрано целочисленным.
Описание слайда:
Теорема о Декомпозиции Потока Теорема 6.7 (Фалкерсон [1962] ) Пусть (G, u, s, t) ― сеть и f ― s-t-поток в G. Тогда существует семейство P s-t-путей и семейство C циклов в G с весами w: P UC → R+ таких, что f(e) = ΣPP UC: e E(P)w(P) для всех e E(G), ΣPP w(P) = value( f ), и |P | + |C | ≤ | E(G)|. Более того, если f ― целочисленный поток, то w может быть выбрано целочисленным.

Слайд 26


Доказательство Построим P , C и w индукцией по числу дуг с ненулевым потоком. Пусть e=(v0,w0) дуга с f(e) > 0. Если w0 ≠ t, то должна быть дуга (w0,w1) c ненулевым потоком. Положим i = 1. Если w0  {t,v0,w0,…, wi–1}, то STOP. Иначе i = i +1 и продолжаем. Если процесс завершится в t, то проделаем тоже самое в обратном направлении, стартуя с v0.
Описание слайда:
Доказательство Построим P , C и w индукцией по числу дуг с ненулевым потоком. Пусть e=(v0,w0) дуга с f(e) > 0. Если w0 ≠ t, то должна быть дуга (w0,w1) c ненулевым потоком. Положим i = 1. Если w0  {t,v0,w0,…, wi–1}, то STOP. Иначе i = i +1 и продолжаем. Если процесс завершится в t, то проделаем тоже самое в обратном направлении, стартуя с v0.

Слайд 27


Иллюстрация доказательства
Описание слайда:
Иллюстрация доказательства

Слайд 28


Доказательство Пусть P будет цикл или путь, найденный в результате описанной процедуры. w(P) = mine E(P) f(e) Положим f '(e) = f(e) – w(P) для eE(P) и f '(e) = f(e) для eE(P). По крайней мере, одна дуга обнулилась и добавился ровно один путь или цикл. Величина потока вдоль дуг из P уменьшилась на величину w(P). Если P цикл, то величина s-t-потока не изменилась. Если P путь, то величина s-t-потока уменьшилась на w(P).
Описание слайда:
Доказательство Пусть P будет цикл или путь, найденный в результате описанной процедуры. w(P) = mine E(P) f(e) Положим f '(e) = f(e) – w(P) для eE(P) и f '(e) = f(e) для eE(P). По крайней мере, одна дуга обнулилась и добавился ровно один путь или цикл. Величина потока вдоль дуг из P уменьшилась на величину w(P). Если P цикл, то величина s-t-потока не изменилась. Если P путь, то величина s-t-потока уменьшилась на w(P).

Слайд 29


Теорема о Декомпозиции Потока Теорема 6.7 (Фалкерсон [1962] ) Пусть (G, u, s, t) ― сеть и f ― s-t-поток в G. Тогда существует семейство P s-t-путей и семейство C циклов в G с весами w: P UC → R+ таких, что f(e) = ΣPP UC: e E(P)w(P) для всех e E(G), ΣPP w(P) = value( f ), и |P | + |C | ≤ | E(G)|. Более того, если f ― целочисленный поток, то w может быть выбрано целочисленным.
Описание слайда:
Теорема о Декомпозиции Потока Теорема 6.7 (Фалкерсон [1962] ) Пусть (G, u, s, t) ― сеть и f ― s-t-поток в G. Тогда существует семейство P s-t-путей и семейство C циклов в G с весами w: P UC → R+ таких, что f(e) = ΣPP UC: e E(P)w(P) для всех e E(G), ΣPP w(P) = value( f ), и |P | + |C | ≤ | E(G)|. Более того, если f ― целочисленный поток, то w может быть выбрано целочисленным.

Слайд 30


Упражнение 6.2 Доказать следующую теорему Теорема (Хоффман 1960) Задан орграф G и нижние и верхние оценки на пропускные способности дуг l, u: E(G) → R+ c l(e) ≤ u(e) для всех e  E(G). В орграфе G существует циркуляция f с l(e) ≤ f(e) ≤ u(e) для всех e  E(G) тогда и только тогда, когда
Описание слайда:
Упражнение 6.2 Доказать следующую теорему Теорема (Хоффман 1960) Задан орграф G и нижние и верхние оценки на пропускные способности дуг l, u: E(G) → R+ c l(e) ≤ u(e) для всех e  E(G). В орграфе G существует циркуляция f с l(e) ≤ f(e) ≤ u(e) для всех e  E(G) тогда и только тогда, когда

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию