Потоки в сетях

Сентябрь 13, 2022

Главная
Математика
Потоки в сетях

Содержание

2. Одной из наиболее важных задач теории графов является задача определения максимального потока, протекающего от некоторой вершины
3. Потоком в сети G = (Х,U) от входа s к выходу t называется неотрицательная функция U,
4. Условие (10.4) является уравнением сохранения потока, согласно которому поток, втекающий в вершину, равен потоку, вытекающему из
5. Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Величина максимального потока из s в
6. Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Минимальный разрез( ) — это разрез
7. Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Рис. 10.32 Разрез , состоящий из
8. Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе) Разрезом орграфа G2 (рис. 10.33) является
9. Пример 10.2. Задача о максимальном потоке Построить максимальный поток для ориентированной сети с источником S и
10. Пример 10.2. Задача о максимальном потоке Решение Составляем матрицу пропускных способностей дуг C = {cik} для
11. Пример 10.2. Задача о максимальном потоке 2. Выбираем произвольно один из путей от вершины S к
12. Пример 10.2. Задача о максимальном потоке (10.8) (10.8) 3. Выбираем следующий путь из S в t,
13. Пример 10.2. Задача о максимальном потоке (10.9) 4. Выбираем новый путь из S в t, т.е.
14. Пример 10.2. Задача о максимальном потоке Р3 = {s, x1, x3, x4, t} и определяем его
15. Пример 10.2. Задача о максимальном потоке (10.11) 6. Укажем путь Р5 = {s, x2, t} и
16. Пример 10.2. Задача о максимальном потоке (10.12) В столбце t имеются только нули. Следовательно, простроить новый
17. Пример 10.2. Задача о максимальном потоке Построим итоговую матрицу: С6 = С - С5. (10.13) На
18. Пример 10.2. Задача о максимальном потоке Рис. 10.35 Построенный граф G удовлетворяют условию потока, т.е. соблюдается
19. Пример 10.2. Задача о максимальном потоке 3. Увеличение потока вдоль построенного пути на максимально возможную величину,
20. Пример 10.2. Задача о максимальном потоке Уменьшающей дугой называется дуга, направление которой противоположное направлению потока, а
21. Пример 10.2. Задача о максимальном потоке Рассмотрим пример 10.2. Определить максимальный поток для сети (рис. 10.34).
22. Пример 10.2. Задача о максимальном потоке Решение. Начальное значение потока полагаем равным нулю Vo = 0.
23. Пример 10.2. Задача о максимальном потоке Рис. 10.36
24. Пример 10.2. Задача о максимальном потоке Р2 = {s, х4, t}, φ2 = min (4; 13-5)
26. Скачать презентацию

Слайд 2

Одной из наиболее важных задач теории графов является задача определения максимального

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

Слайд 3

Потоком в сети G = (Х,U) от входа s к выходу

t называется неотрицательная функция U, определенная на множестве дуг сети со следующими свойствами:
(10.4)
(10.5)

(10.4)

Слайд 4

Условие (10.4) является уравнением сохранения потока, согласно которому поток, втекающий в

вершину, равен потоку, вытекающему из нее, за исключением вершин s и t (источник и сток).
Ограничение (10.5) указывает, что пропускные способности дуг ограничены для каждой дуги графа G.
Задача состоит в нахождении такого множества потоков по дугам, чтобы
(10.6)
при ограничениях (10.4) и (10.5).

Слайд 5

Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе)
Величина максимального

потока из s в t равна значению минимального разреза отделяющего источник s от стока t.
Разрез отделяет s от t, если
,а . Величиной такого разреза называется сумма пропускных способностей всех дуг из G, начальные вершины которых лежат в Хо, а конечные — в , т.е.
(10.7)

Слайд 6

Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе)
Минимальный разрез(

) — это разрез с наименьшим значением суммы пропускных способностей дуг.
Если вершины неографа G = (X,U) разделены на два множества Хо и , где и является дополнением Хо относительно X, то множество ребер графа G, одни концевые вершины которых лежат в Хо, а другие — в Хо,
определяют разрез этого неографа G.
Обозначают разрезы в графах R = (Х0, ).

Слайд 7

Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе)
Рис. 10.32
Разрез

, состоящий из дуг орграфа определяется как объединение

Слайд 8

Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе)
Разрезом орграфа

G2 (рис. 10.33) является множество дуг U1 = (х5, х1), U2 = (x1, x4), U4 = (х3, х7) и U5 = (х2, х7), удаление которых разделяет множества вершин Хо = {х1,х2,х3} и ={х4,х5,х6,х7} (рис. 10.33).
Рис. 10.33
Этот разрез образован множествами:

Слайд 9

Пример 10.2. Задача о максимальном потоке
Построить максимальный поток для ориентированной сети с

источником S и стоком t (рис. 10.34). Пропускные способности дуг указаны на дугах сети:
Рис. 10.34

Слайд 10

Пример 10.2. Задача о максимальном потоке
Решение
Составляем матрицу пропускных способностей дуг

C = {cik} для графа G; нулевые значения пропускных способностей дуг в табл. 10.7 не записываем:
(10.7)

Слайд 11

Пример 10.2. Задача о максимальном потоке
2. Выбираем произвольно один из

путей от вершины S к вершине t графа G (рис. 10.34).
Пусть Р1 = {s, x1, x4, t} —первоначальный путь: Определяем пропускную способность выбранного пути
Q1=min{10,5.13} = 5.
В табл. 10.7 отмечаем чертой сверху значения пропускных способностей дуг, соответствующих указанному пути Р1.
Вычитаем значение Q1 = 5 из отмеченных элементов (10, 5, 13).
Нули, получаемые в результате вычислений, записываем в соответствующую строку или столбец.

Слайд 12

Пример 10.2. Задача о максимальном потоке
(10.8)
(10.8)
3. Выбираем следующий путь из

S в t, т.е. Р2 = {s, x4, t} и определяем его пропускную способность:
Q2 = min{4;8} = 4.
В табл. 10.8 отмечаем значения пропускных способностей чертой над числами 4 и 8. Вычитаем значение Q2 = 4 из указанных элементов. Получаем новую табл. 10.9:

Слайд 13

Пример 10.2. Задача о максимальном потоке
(10.9)
4. Выбираем новый путь из

S в t, т.е.
(10.10)

Слайд 14

Пример 10.2. Задача о максимальном потоке
Р3 = {s, x1, x3,

x4, t} и определяем его минимальную пропускную способность:
Q3=min{5,9,7,4} = 4.
Вычитаем значение Q3 = 4 из элементов, отмеченных в табл. 10.9. Получаем табл. 10.10 в виде:
5. Выбираем путь Р4 = {s,x3, t} и определяем его пропускную способность:
Q4=min{14,2} = 2.
Вычитая Q4 = 2 из значений пропускаемых способностей (14,2), получаем табл. 10.11:

Слайд 15

Пример 10.2. Задача о максимальном потоке
(10.11)
6. Укажем путь Р5 =

{s, x2, t} и определим его пропускную способность:
Q5 = min{3;3} =3.
Вычитая Q5 из элементов пропускных способностей дуг рассматриваемого пути получаем таб. 10.11 в виде 10.12:

Слайд 16

Пример 10.2. Задача о максимальном потоке
(10.12)
В столбце t имеются только

нули.
Следовательно, простроить новый путь невозможно.
Вычитая из элементов табл. 10.1) значения пропускных способностей дуг, указанных в табл. 10.12, получаем таблицу со значениями Cjk, определяющими максимального возможный поток.
Его величина равна
П = Ql + Q2 + Q3 + Q4 + Q5;
П = 5 + 4 + 4 + 2 + 3 = 18.

Слайд 17

Пример 10.2. Задача о максимальном потоке
Построим итоговую матрицу:
С6 = С

- С5. (10.13)
На основании итоговой матрицы строим максимальный поток сети:

Слайд 18

Пример 10.2. Задача о максимальном потоке
Рис. 10.35
Построенный граф G удовлетворяют

условию потока, т.е. соблюдается равновесие вершин (величина входящего и выходящего потоков равны). Величина минимального разреза дуг равна R = 18.
Рассмотрим другой способ решения задачи, используя алгоритм построения максимального потока в сети методом увеличения потока вдоль пути, который состоит в следующем:
Выбор начального потока. Обычно выбирают нулевое начальное значение потока.
Построение увеличивающего пути от источника s к стоку t

Слайд 19

Пример 10.2. Задача о максимальном потоке
3. Увеличение потока вдоль построенного

пути на максимально возможную величину, полагая увеличение потока по увеличивающей дуге и уменьшение его по уменьшающей дуге.
Увеличивающей дугой называется дуга, направление которой совпадает с направлением потока и величина потока по этой дуге меньше ее пропускной способности, т.е.

Слайд 20

Пример 10.2. Задача о максимальном потоке
Уменьшающей дугой называется дуга, направление

которой противоположное направлению потока, а величина потока отлична от нуля:
Уменьшающие и увеличивающие дуги называют допустимыми.
Увеличивающим путем называется элементарный путь, все дуги которого являются допустимыми.
Рассмотрим пример 10.2.
Определить максимальный поток для сети (рис. 10.34).

Слайд 21

Пример 10.2. Задача о максимальном потоке
Рассмотрим пример 10.2.
Определить максимальный

поток для сети (рис. 10.34).
Рис. 10.34

Слайд 22

Пример 10.2. Задача о максимальном потоке
Решение.
Начальное значение потока полагаем равным

нулю Vo = 0.
Построим увеличивающие пути от S к стоку t:
Pl = {s, x1, x4, t}, φ1 = min (10; 5; 13) = 5.
Запишем значение φ1 = 5 в скобках на соответствующих дугах рассматриваемого пути. Для пути (рис. 10.36)

Слайд 23

Пример 10.2. Задача о максимальном потоке
Рис. 10.36

Слайд 24

Пример 10.2. Задача о максимальном потоке
Р2 = {s, х4, t},

φ2 = min (4; 13-5) = 4.
Отметим на дугах пути Р2 величину φ2 = 4. Для пути
Р3 = {s,x1, x3, x4, t}, φ3 = min (10-5; 9; 7; 13-9) = 4.
Запишем величину φ3 = 4 на дугах пути Р3. Аналогично запишем пути Рi на дугах которых отметим соответствующие величины φi:
Р4 = {s, х3, t}, φ4 = min (14; 2) = 2;
P5 = {s, x2, t}, φ5 = min (6; 3) = 3.

Потоки в сетях

Содержание

Одной из наиболее важных задач теории графов является задача определения максимального

Потоком в сети G = (Х,U) от входа s к выходу

Условие (10.4) является уравнением сохранения потока, согласно которому поток, втекающий в

Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе)Величина максимального

Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе)Минимальный разрез(

Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе)Рис. 10.32Разрез

Теорема Форда - Фалкерсона (о максимальном потоке и минимальном разрезе)Разрезом орграфа

Пример 10.2. Задача о максимальном потокеПостроить максимальный поток для ориентированной сети с

Пример 10.2. Задача о максимальном потоке РешениеСоставляем матрицу пропускных способностей дуг

Пример 10.2. Задача о максимальном потоке 2. Выбираем произвольно один из

Пример 10.2. Задача о максимальном потоке (10.8)(10.8)3. Выбираем следующий путь из

Пример 10.2. Задача о максимальном потоке (10.9)4. Выбираем новый путь из

Пример 10.2. Задача о максимальном потоке Р3 = {s, x1, x3,

Пример 10.2. Задача о максимальном потоке (10.11)6. Укажем путь Р5 =

Пример 10.2. Задача о максимальном потоке (10.12)В столбце t имеются только

Пример 10.2. Задача о максимальном потоке Построим итоговую матрицу:С6 = С

Пример 10.2. Задача о максимальном потоке Рис. 10.35Построенный граф G удовлетворяют

Пример 10.2. Задача о максимальном потоке 3. Увеличение потока вдоль построенного

Пример 10.2. Задача о максимальном потоке Уменьшающей дугой называется дуга, направление

Пример 10.2. Задача о максимальном потоке Рассмотрим пример 10.2. Определить максимальный

Пример 10.2. Задача о максимальном потоке Решение.Начальное значение потока полагаем равным

Пример 10.2. Задача о максимальном потоке Рис. 10.36

Пример 10.2. Задача о максимальном потоке Р2 = {s, х4, t},

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