Максимальный поток в сети

Август 5, 2022

Главная
Информатика
Максимальный поток в сети

Содержание

2. Постановка задачи о максимальном потоке Алгоритм Форда-Фалкерсона нахождения максимального потока Содержание
3. Транспортной сетью называют связный граф без циклов, в котором: существует единственная вершина s, из которой дуги
4. Потоком в сети ϕ называется целочисленная функция, заданная на дугах графа, такая, что: для любой дуги
5. Из этого же равенства и из того, что в сети нет контуров, следует, что суммарный поток,
6. Назовем дугу насыщенной, если для нее величина потока равна пропускной способности дуги: ϕij=сij. Путь между вершинами
7. Зададим на сети любой поток и доведем его до полного. Для этого перебираем все пути между
8. Разметка выделяет цепь между источником и стоком сети. Будем двигаться от стока к источнику и восстановим
9. Рассмотрим транспортную сеть, приведенную на рис.. Здесь цифрами отмечены пропускные способности дуг. Далее цифрами в скобках
10. Выполним шаг 1 алгоритма. Зададим начальный поток по дугам по следующему правилу: выделим несколько путей, начинающихся
11. для первого пути s – 1 – 4 – 7 – t минимальное среди дуг пути
12. для второго пути s – 2 – 7 – t минимальное среди дуг пути значение разности
13. для третьего пути s – 2 – 5 – t минимальное среди дуг пути значение разности
14. для четвертого пути s – 3 – 6 – 8 – t минимальное среди дуг пути
15. для пятого пути s – 3 – 5 – t минимальное среди дуг пути значение разности
16. Выполним шаг 2 алгоритма, т.е. проведем последовательную разметку графа (рис.). Пример нахождения максимального потока Помечаем вершину
17. Выполним шаг 3 алгоритма. Восстановим цепь между источником и стоком сети, двигаясь по меткам вершин от
18. Повторяем шаг 2 алгоритма, т.е. проведем последовательную разметку графа (рис.). В результате помечаем сток t. Пример
19. Выполним шаг 3 алгоритма. Восстановим путь между источником и стоком сети. Получим путь s – 1
20. Повторяем шаг 2 алгоритма, т.е. проведем последовательную разметку графа (рис.). После пометки истока s пометить сток
21. Разобьем множество вершин V сети на два подмножества, V1 и V2, при котором в первое подмножество
22. Разрез, величина которого минимальна, называется минимальным разрезом. Для проверки того, является ли поток максимальным, служит Теорема
24. Скачать презентацию

Слайд 2

Постановка задачи о максимальном потоке
Алгоритм Форда-Фалкерсона нахождения максимального потока
Содержание

Слайд 3

Транспортной сетью называют связный граф без циклов, в котором:
существует единственная

вершина s, из которой дуги только выходят, называемая источником (входом) сети;
существует единственная вершина t, в которую дуги только заходят, называемая стоком (выходом) сети;
для каждой дуги (i, j) задан вес неотрицательным целым числом сij, называемым пропускной способностью дуги.

Постановка задачи о максимальном потоке

Слайд 4

Потоком в сети ϕ называется целочисленная функция, заданная на дугах графа,

такая, что:
для любой дуги 0≤ ϕij ≤ сij;
для любой вершины i, кроме источника и стока сети, имеет место равенство
где
Р – множество вершин, связанных с вершиной i по исходящим дугам,
Q – по заходящим дугам.
Последнее равенство означает, что суммарный поток, входящий в вершину, равен суммарному потоку, выходящему из нее.

Постановка задачи о максимальном потоке

Слайд 5

Из этого же равенства и из того, что в сети нет

контуров, следует, что суммарный поток, исходящий из вершины s, равен суммарному потоку, заходящему в вершину t,
т.е.
Эта величина ϕ называется величиной потока.
Задача состоит в том, чтобы для заданной сети определить поток, имеющий максимальную величину.

Постановка задачи о максимальном потоке

Слайд 6

Назовем дугу насыщенной, если для нее величина потока равна пропускной способности

дуги:
ϕij=сij.
Путь между вершинами s и t назовем полным, если он содержит хотя бы одну насыщенную дугу.
Поток назовем полным, если в нем любой путь полный.
Рассмотрим алгоритм решения этой задачи, предложенный Фордом и Фалкерсоном.

Алгоритм нахождения максимального потока

Слайд 7

Зададим на сети любой поток и доведем его до полного.
Для

этого перебираем все пути между источником и стоком сети
и если некоторый путь неполон, то, увеличивая поток по нему, доводим его до полного.
Проведем последовательную разметку графа:
вершину s пометим символом 0;
если вершина i отмечена, то непомеченные вершины j,
связанные с ней по исходящим дугам, пометим как [+i; λij], если дуга (i, j) не насыщена,
и связанные по заходящим дугам как [–i; λij], если поток в дуге (i, j) не равен нулю,
где λij – разность между пропускной способностью дуги (i, j) и значением потока ϕij.
Если в результате разметки будет помечен сток сети, то переходим к пункту 3, иначе – конец алгоритма.

Алгоритм Форда-Фалкерсона

Слайд 8

Разметка выделяет цепь между источником и стоком сети.
Будем двигаться от

стока к источнику и восстановим цепь, двигаясь по меткам и одновременно отыскивая λ – минимальное среди значений λij.
Изменим поток в дугах восстановленной цепи по правилу:
если направление движения от источника к стоку совпадает с направлением дуги, то значение потока увеличим на λ,
если противоположен, то уменьшим на λ.
После этого переходим к пункту 2.

Алгоритм Форда-Фалкерсона

Слайд 9

Рассмотрим транспортную сеть, приведенную на рис..
Здесь цифрами отмечены пропускные способности

дуг.
Далее цифрами в скобках будем отмечать величину потока по дугам.
В квадратных скобках будем указывать метки вершин на шаге 2.

Пример нахождения максимального потока

Слайд 10

Выполним шаг 1 алгоритма.
Зададим начальный поток по дугам по следующему

правилу:
выделим несколько путей, начинающихся в s:
s – 1 – 4 – 7 – t,
s – 2 – 7 – t,
s – 2 – 5 – t,
s – 3 – 6 – 8 – t,
s – 3 – 5 – t;
последовательно для каждого из путей увеличим поток на величину, равную минимальному среди дуг пути значению разности между пропускной способностью дуги и величиной назначенного ранее потока;

Пример нахождения максимального потока

Слайд 11

для первого пути s – 1 – 4 – 7 –

t
минимальное среди дуг пути значение разности между пропускной способностью дуги и 0 – величиной назначенного ранее потока по дугам – равно 2;
поэтому поток по всем дугам пути назначаем равным 2 (рис.);
путь s – 1 – 4 – 7 – t – полный;

Пример нахождения максимального потока

Слайд 12

для второго пути s – 2 – 7 – t
минимальное

среди дуг пути значение разности между пропускной способностью дуги и величиной 2 назначенного ранее потока по дуге (7, t) равно 5;
поэтому поток по всем дугам пути увеличиваем на 2 (рис.);
путь s – 2 – 7 – t – полный;

Пример нахождения максимального потока

Слайд 13

для третьего пути s – 2 – 5 – t
минимальное

среди дуг пути значение разности между пропускной способностью дуги и величиной 5 назначенного ранее потока по дуге (s, 2) равно 1;
поэтому поток по всем дугам пути увеличиваем на 1 (рис.);
путь s – 2 – 5 – t – полный;

Пример нахождения максимального потока

Слайд 14

для четвертого пути s – 3 – 6 – 8 –

t
минимальное среди дуг пути значение разности между пропускной способностью дуги и 0 – величиной назначенного ранее потока по дугам – равно 1;
поэтому поток по всем дугам пути увеличиваем на 1 (рис.);
путь s – 3 – 6 – 8 – t – полный;

Пример нахождения максимального потока

Слайд 15

для пятого пути s – 3 – 5 – t
минимальное

среди дуг пути значение разности между пропускной способностью дуги и величиной назначенного ранее потока по дуге (5, t) равно 4;
поэтому поток по всем дугам пути увеличиваем на 4 (рис.);
путь s – 3 – 5 – t – полный;

Пример нахождения максимального потока

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

Слайд 16

Выполним шаг 2 алгоритма,
т.е. проведем последовательную разметку графа (рис.).
Пример

нахождения максимального потока

Помечаем вершину s.
Из нее можно пометить только вершину 1 по ненасыщенной дуге.
Далее по ненасыщенной дуге из 1 помечаем вершину 5,
а из 5 – сток t.

Слайд 17

Выполним шаг 3 алгоритма.
Восстановим цепь между источником и стоком сети,

двигаясь по меткам вершин от стока к источнику и отыскивая дугу с минимальным значением метки λij – разностью между ее пропускной способностью и значением потока.
Это будет дуга (5, t) и получим λ=1.
Изменим поток в дугах восстановленной цепи:
s – 1 – 5 – t (рис.).

Пример нахождения максимального потока

Слайд 18

Повторяем шаг 2 алгоритма,
т.е. проведем последовательную разметку графа (рис.).
В

результате помечаем сток t.

Пример нахождения максимального потока

Слайд 19

Выполним шаг 3 алгоритма.
Восстановим путь между источником и стоком сети.

Получим путь
s – 1 – 5 – 8 – t.
Для него определим λ=1.
Изменим поток в дугах восстановленной цепи (рис.).

Пример нахождения максимального потока

Слайд 20

Повторяем шаг 2 алгоритма,
т.е. проведем последовательную разметку графа (рис.).
После

пометки истока s пометить сток t по ненасыщенным дугам не удается.

Пример нахождения максимального потока

Т.о., повторная разметка графа невозможна, значит, полученный поток максимален.
Получили следующий максимальный поток величины ϕ=15 единиц:
ϕs1=4, ϕs2=6, ϕs3=5, ϕ14=ϕ15=ϕ47=ϕ8t=2, ϕ25=ϕ36=ϕ68=ϕ58=1, ϕ7t=7, ϕ35=4

Слайд 21

Разобьем множество вершин V сети на два подмножества, V1 и V2,

при котором
в первое подмножество включен источник сети,
во второе – ее сток.
Множество дуг, начинающихся в V1 и заканчивающихся в V2, называется разрезом сети, а сумма пропускных способностей этих дуг называется величиной разреза.

Минимальный разрез сети

Разрез величиной 27

Слайд 22

Разрез, величина которого минимальна, называется минимальным разрезом.
Для проверки того, является ли

поток максимальным, служит Теорема Форда-Фалкерсона:
Максимальный поток в сети равен величине ее минимального разреза.
Теорема позволяет проверить, является ли поток максимальным.
Если находится разрез, в котором все дуги насыщены, то величина потока будет максимальной.

Минимальный разрез сети

Максимальный поток в сети

Содержание

Постановка задачи о максимальном потокеАлгоритм Форда-Фалкерсона нахождения максимального потока Содержание

Транспортной сетью называют связный граф без циклов, в котором: существует единственная

Потоком в сети ϕ называется целочисленная функция, заданная на дугах графа,

Из этого же равенства и из того, что в сети нет

Назовем дугу насыщенной, если для нее величина потока равна пропускной способности

Зададим на сети любой поток и доведем его до полного. Для

Разметка выделяет цепь между источником и стоком сети. Будем двигаться от

Рассмотрим транспортную сеть, приведенную на рис.. Здесь цифрами отмечены пропускные способности

Выполним шаг 1 алгоритма. Зададим начальный поток по дугам по следующему

для первого пути s – 1 – 4 – 7 –

для второго пути s – 2 – 7 – t минимальное

для третьего пути s – 2 – 5 – t минимальное

для четвертого пути s – 3 – 6 – 8 –

для пятого пути s – 3 – 5 – t минимальное

Выполним шаг 2 алгоритма, т.е. проведем последовательную разметку графа (рис.). Пример

Выполним шаг 3 алгоритма. Восстановим цепь между источником и стоком сети,

Повторяем шаг 2 алгоритма, т.е. проведем последовательную разметку графа (рис.). В

Выполним шаг 3 алгоритма. Восстановим путь между источником и стоком сети.

Повторяем шаг 2 алгоритма, т.е. проведем последовательную разметку графа (рис.). После

Разобьем множество вершин V сети на два подмножества, V1 и V2,

Разрез, величина которого минимальна, называется минимальным разрезом.Для проверки того, является ли

Похожие презентации

Постановка задачи о максимальном потоке
Алгоритм Форда-Фалкерсона нахождения максимального потока
Содержание

Транспортной сетью называют связный граф без циклов, в котором:
существует единственная

Зададим на сети любой поток и доведем его до полного.
Для

Разметка выделяет цепь между источником и стоком сети.
Будем двигаться от

Рассмотрим транспортную сеть, приведенную на рис..
Здесь цифрами отмечены пропускные способности

Выполним шаг 1 алгоритма.
Зададим начальный поток по дугам по следующему

для второго пути s – 2 – 7 – t
минимальное

для третьего пути s – 2 – 5 – t
минимальное

для пятого пути s – 3 – 5 – t
минимальное

Выполним шаг 2 алгоритма,
т.е. проведем последовательную разметку графа (рис.).
Пример

Выполним шаг 3 алгоритма.
Восстановим цепь между источником и стоком сети,

Повторяем шаг 2 алгоритма,
т.е. проведем последовательную разметку графа (рис.).
В

Выполним шаг 3 алгоритма.
Восстановим путь между источником и стоком сети.

Повторяем шаг 2 алгоритма,
т.е. проведем последовательную разметку графа (рис.).
После

Разрез, величина которого минимальна, называется минимальным разрезом.
Для проверки того, является ли