- Потоки в сетях. Глава 8
Содержание
- 3. 8.1. Постановка задачи
- 4. Транспортная сеть Транспортной сетью – transportation network называется связный ориентированный униграф без петель, удовлетворяющий следующим условиям:
- 5. s t a b c d 6 2 6 10 3 10 2 5 2 2
- 6. Поток – ограничение по пропускной способности дуг, – условие сохранения (непрерывности) потока.
- 7. Разрез Разрезом (cut) связного графа называется такое под-множество дуг, что удаление их делает граф несвязным.
- 8. s t a b c d 6 2 6 10 3 10 2 5 2 2
- 10. 8.2. Теорема Форда - Фалкерсона
- 13. Теорема Форда – Фалкерсона (о максимальном потоке и минимальном разрезе).
- 17. 8.3. Алгоритм Форда - Фалкерсона
- 18. Delbert Ray Fulkerson (August 14, 1924 – January 10, 1976) was an American mathematician who co-developed
- 19. Идея алгоритма Поиск увеличивающих цепей производится с помощью расстановки меток, которые указывают на каких дугах и
- 20. Каждая вершина может находиться в одном из трех состояний: помечена и просмотрена, т. е. вершина имеет
- 21. Подготовительный этап s t a b c d 6 2 6 10 3 10 2 5
- 22. Разметка вершин
- 23. Увеличение потока После изменения потока все метки стираются , алгоритм возвращается на этап разметки вершин.
- 24. s t a b c d 6,0 2,0 6,0 10,0 3,0 10,0 2,0 5,0 2,0 2,0
- 25. s t a b c d 6,2 2,2 6,2 10,0 3,0 10,0 2,0 5,0 2,0 2,0
- 26. s t a b c d 6,4 2,2 6,2 10,2 3,0 10,0 2,0 5,0 2,2 2,0
- 27. s t a b c d 6,4 2,2 6,4 10,2 3,0 10,2 2,0 5,0 2,2 2,2
- 28. s t a b c d 6,4 2,2 6,4 10,5 3,3 10,5 2,0 5,0 2,2 2,2
- 29. s t a b c d 6,4 2,2 6,4 10,5 3,3 10,5 2,0 5,0 2,2 2,2
- 33. Скачать презентацию
8.1. Постановка задачи
8.1. Постановка задачи
Транспортная сеть
Транспортной сетью – transportation network называется связный ориентированный униграф без
Транспортная сеть
Транспортной сетью – transportation network называется связный ориентированный униграф без
s
t
a
b
c
d
6
2
6
10
3
10
2
5
2
2
Пример транспортной сети
s
t
a
b
c
d
6
2
6
10
3
10
2
5
2
2
Пример транспортной сети
Поток
– ограничение по пропускной способности дуг,
– условие сохранения (непрерывности) потока.
Поток
– ограничение по пропускной способности дуг,
– условие сохранения (непрерывности) потока.
Разрез
Разрезом (cut) связного графа называется такое под-множество дуг, что удаление их
Разрез
Разрезом (cut) связного графа называется такое под-множество дуг, что удаление их
s
t
a
b
c
d
6
2
6
10
3
10
2
5
2
2
Пример
s
t
a
b
c
d
6
2
6
10
3
10
2
5
2
2
Пример
8.2. Теорема Форда - Фалкерсона
8.2. Теорема Форда - Фалкерсона
Теорема Форда – Фалкерсона (о максимальном потоке и минимальном разрезе).
Теорема Форда – Фалкерсона (о максимальном потоке и минимальном разрезе).
8.3. Алгоритм Форда - Фалкерсона
8.3. Алгоритм Форда - Фалкерсона
Delbert Ray Fulkerson (August 14, 1924 – January 10, 1976)
was
Delbert Ray Fulkerson (August 14, 1924 – January 10, 1976)
was
Идея алгоритма
Поиск увеличивающих цепей производится с помощью расстановки меток, которые указывают
Идея алгоритма
Поиск увеличивающих цепей производится с помощью расстановки меток, которые указывают
Каждая вершина может находиться в одном из трех состояний:
помечена и просмотрена,
Каждая вершина может находиться в одном из трех состояний:
помечена и просмотрена,
Подготовительный этап
s
t
a
b
c
d
6
2
6
10
3
10
2
5
2
2
Подготовительный этап
s
t
a
b
c
d
6
2
6
10
3
10
2
5
2
2
Разметка вершин
Разметка вершин
Увеличение потока
После изменения потока все метки стираются , алгоритм возвращается на
Увеличение потока
После изменения потока все метки стираются , алгоритм возвращается на
s
t
a
b
c
d
6,0
2,0
6,0
10,0
3,0
10,0
2,0
5,0
2,0
2,0
Итерация 1
+2
+2
+2
s
t
a
b
c
d
6,0
2,0
6,0
10,0
3,0
10,0
2,0
5,0
2,0
2,0
Итерация 1
+2
+2
+2
s
t
a
b
c
d
6,2
2,2
6,2
10,0
3,0
10,0
2,0
5,0
2,0
2,0
Итерация 2
+2
+2
+2
s
t
a
b
c
d
6,2
2,2
6,2
10,0
3,0
10,0
2,0
5,0
2,0
2,0
Итерация 2
+2
+2
+2
s
t
a
b
c
d
6,4
2,2
6,2
10,2
3,0
10,0
2,0
5,0
2,2
2,0
Итерация 3
+2
+2
+2
s
t
a
b
c
d
6,4
2,2
6,2
10,2
3,0
10,0
2,0
5,0
2,2
2,0
Итерация 3
+2
+2
+2
s
t
a
b
c
d
6,4
2,2
6,4
10,2
3,0
10,2
2,0
5,0
2,2
2,2
Итерация 4
+3
+3
+3
s
t
a
b
c
d
6,4
2,2
6,4
10,2
3,0
10,2
2,0
5,0
2,2
2,2
Итерация 4
+3
+3
+3
s
t
a
b
c
d
6,4
2,2
6,4
10,5
3,3
10,5
2,0
5,0
2,2
2,2
Итерация 5
s
t
a
b
c
d
6,4
2,2
6,4
10,5
3,3
10,5
2,0
5,0
2,2
2,2
Итерация 5
s
t
a
b
c
d
6,4
2,2
6,4
10,5
3,3
10,5
2,0
5,0
2,2
2,2
s
t
a
b
c
d
6,4
2,2
6,4
10,5
3,3
10,5
2,0
5,0
2,2
2,2
Определение квадратного уравнения. Неполные квадратные уравнения. 8 класс
Логарифмическая функция
Занимательная математика. Конструктивная геометрия
История тригонометрии
Подготовила: Груздева Елена Викторовна, учитель математики МОУ СОШ №1 г. Шебекино
Футбол. Дидактическая игра по математике, 2 класс
Свойства квадратных корней
Законы сложения
Геометрия. 8 класс
Урок математики. Прибавить и вычесть числа 1, 2, 3
Вычислительная механика. Формирование глобальных векторов и матриц МКЭ
Көпбұрыштың ортогональ проекциясының ауданы
Однозначные и двузначные числа
Математическая игра « Цифра семь известна всем»
Линейная алгебра
2 класс. Математический диктант №3. Выполнила Кирилова С.Г. учитель начальных классов Школы «Ученики Пифагора». г.Лимассол р. Ки
Решение задач на составление уравнений
Урок математики во 2 «А» классе МОУ «СОШ № 4» 26.01. 2011. Учитель: Данилова Светлана Михайловна
Графики функций
Умножение и деление на 10
Математика в кинематографии
Объём шара и площадь сферы. Математический диктант
Выборочное наблюдение. Практическое занятие
Деление и дроби
Деление окружности (круга) на 2,4,8 частей
Проекционное черчение и основные виды чертежа
Основы практической биомедицинской статистики
Математические фокусы. Виды фокусов