Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах

Сентябрь 7, 2022

Главная
Алгебра
Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах

Содержание

2. СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ На взвешенном ориентированном графе G(X,U) требуется определить кратчайший путь из
3. ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ Поиск кратчайшего пути из s-й вершины в t-ю
4. МЕТОД ПОТЕНЦИАЛОВ Шаг 1. Вершине присваивается потенциал P(s)=0. Шаг 2. Всем вершинам множества Х\ присвоить потенциал,
5. ПРИМЕР 1 Поиск длины кратчайшего пути из 1-й вершины в 4-ю. 1 2 3 4 5
6. ДОСТОИНСТВА И НЕДОСТАТКИ Достоинства: Метод потенциалов гарантирует определение кратчайших путей из выбранной вершины во все остальные.
7. РЕШИТЬ САМОСТОЯТЕЛЬНО Определить кратчайшие пути из 1-й вершины во все остальные. 1 3 7 8 10
8. МАКСИМАЛЬНЫЕ ПОТОКИ НА ГРАФАХ Содержательная постановка задачи: требуется определить максимальный однородный поток на графе G(X,U) из
9. Формальная постановка задачи о максимальном однородном потоке Обозначения: f(i,j) – поток по дуге , r(i,j) –
10. САМОСТОЯТЕЛЬНО Дайте иную формальную постановку задачи о максимальном потоке, в которой: эмиссионная способность источника ограничена; поглощающая
11. ЧАСТО ИСПОЛЬЗУЕМЫЙ АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ПОТОКА Шаг 1. Полученный граф G(X,U’) заменяется на G’(X,U’) такой, что:
12. АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ПОТОКА (ПРОДОЛЖЕНИЕ) Шаг 5. На графе G(X,U) вес всех дуг, принадлежавших пути L,
13. ПРИМЕР 2 a) Граф G(X,U). b) Граф G’(X,U’), S=4. a) b) S=5. c) L=∞. 1 S
14. САМОСТОЯТЕЛЬНО Сформулируйте достоинства приведенного выше алгоритма. Сформулируйте недостатки приведенного выше алгоритма.
15. Пример 3 1 4 3 2 6 5 1 1 1 1 2 1 1 1
16. САМОСТОЯТЕЛЬНО 1. Сформулировать достоинства и недостатки алгоритма поиска максимального потока. 2. Определить максимальный поток из источника
17. МИНИМАЛЬНЫЕ РАЗРЕЗЫ НА ГРАФАХ Определения: 1. Разрезом на ориентированном графе G(X, U) называется подмножество дуг, удаление
18. Обозначения и определения Z(i,j) – булева переменная, равная единице, если дуга (i,j) принадлежит минимальному разрезу и
19. Формальная постановка задачи о минимальном разрезе
20. Поиск минимального разреза перебором Граф G(X,U) 1 4 3 2 2 7 5 9 3
21. ТЕОРЕМА ФОРДА-ФАЛКЕРСОНА Величина минимального разреза на взвешенном ориентированном графе равна величине максимального потока.
23. Скачать презентацию

Слайд 2

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ
На взвешенном ориентированном графе G(X,U)

требуется определить кратчайший путь из i-й вершины в j-ю.

2 7

5 3

Граф G(X,U) Кратчайший путь из 1-й вершины в 3-ю

Слайд 3

ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ
Поиск кратчайшего пути из s-й вершины

в t-ю

Слайд 4

МЕТОД ПОТЕНЦИАЛОВ
Шаг 1. Вершине присваивается потенциал P(s)=0.
Шаг 2. Всем вершинам множества

Х\ присвоить
потенциал, равный ∞.
Шаг 3. Каждой q-й вершине множества Х\
присваивается потенциал P(q):
Шаг 4. Если потенциал хотя бы одной вершины
изменился, то перейти к шагу 3, в противном
случае – к шагу 5.
Шаг 5. Конец алгоритма. Потенциал t-й вершины равен
кратчайшему пути в нее из вершины .

Слайд 5

ПРИМЕР 1
Поиск длины кратчайшего пути из 1-й вершины в 4-ю.
1

2 5

9 3

4 6

1
2

∞
∞

∞

2 5

1
2

11
2

1
2

4 6

9 3

∞
4

1
0

11
2

7
4

1
0

2 5

2 6

3 5

8
2

7
4

4 6

9 3

1
2

а) б) в) г)
Порядок расстановки потенциалов на каждой итерации – по часовой стрелке.

Слайд 6

ДОСТОИНСТВА И НЕДОСТАТКИ
Достоинства:
Метод потенциалов гарантирует определение кратчайших путей из выбранной вершины

во все остальные.
Исключается необходимость перебора всех путей.
Высокое быстродействие.
Легкая программная реализация.
Универсальность: метод применим к ориентированным и неориентированным графам.
Недостатки:
Вес каждой дуги должен быть положительным.

Слайд 7

РЕШИТЬ САМОСТОЯТЕЛЬНО
Определить кратчайшие пути из 1-й вершины во все остальные.
1

3
7
8
10
6

8
2
9
11
7
4

12
1

Слайд 8

МАКСИМАЛЬНЫЕ ПОТОКИ НА ГРАФАХ
Содержательная постановка задачи: требуется определить максимальный однородный поток

на графе G(X,U) из вершины s в вершину t, если поток по каждой дуге графа (i,j) не может превышать ее пропускной способности r(i,j)

Слайд 9

Формальная постановка задачи о максимальном однородном потоке
Обозначения: f(i,j) – поток по

дуге ,
r(i,j) – пропускная способность дуги ;
- вершина – источник;
- вершина – сток.

Задача линейного программирования

Слайд 10

САМОСТОЯТЕЛЬНО
Дайте иную формальную постановку задачи о максимальном потоке, в которой:
эмиссионная

способность источника ограничена;
поглощающая способность стока ограничена;
на графе имеется несколько источников и стоков.

Слайд 11

ЧАСТО ИСПОЛЬЗУЕМЫЙ АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ПОТОКА
Шаг 1. Полученный граф G(X,U’)

заменяется на G’(X,U’) такой, что:
Шаг 2. Методом потенциалов ищется кратчайший путь L из
Шаг 3. Если длина такого пути равна ∞, то перейти к шагу 9, в противном случае – к шагу 4.
Шаг 4. На графе G(X,U) выбирается дуга (p,q), принадлежащая L, для которой справедливо:

Слайд 12

АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ПОТОКА (ПРОДОЛЖЕНИЕ)
Шаг 5. На графе G(X,U) вес

всех дуг, принадлежавших пути L, изменяется следующим образом:
Шаг 6. Образовавшиеся дуги с нулевым весом
на G(X,U) отбрасываются.
Шаг 7. Вес r(p,q) добавить к ранее накопленной сумме S.
Шаг 8. Перейти к шагу 1.
Шаг 9. Конец алгоритма. Суммарный вес дуг, найденных на шаге 4 каждой итерации, равен максимальному потоку из источника в сток.

Слайд 13

ПРИМЕР 2
a) Граф G(X,U). b) Граф G’(X,U’), S=4. a) b) S=5.

c) L=∞.

1 2

1 4 1 0,25 1 1

2 4 0,5 0,25 2 0,5

1 1

1
1

Слайд 14

САМОСТОЯТЕЛЬНО
Сформулируйте достоинства приведенного выше алгоритма.
Сформулируйте недостатки приведенного выше алгоритма.

Слайд 15

Пример 3
1
4
3
2
6
5
1
1
1 1 2 1
1 1
1

Максимальный поток F из 1-й вершины в 6-ю равен двум, но вышеприведенный алгоритм покажет F = 1 (на графе этот поток выделен красным цветом).

Слайд 16

САМОСТОЯТЕЛЬНО
1. Сформулировать достоинства и недостатки алгоритма поиска максимального потока.
2. Определить максимальный

поток из источника в сток на графе G(X,U):

1 2 3 8

4 5

6 7
2
3
5

4
3
5
8
6
1

7
3
9

Слайд 17

МИНИМАЛЬНЫЕ РАЗРЕЗЫ НА ГРАФАХ
Определения:
1. Разрезом на ориентированном графе G(X, U)

называется подмножество дуг, удаление которых разрывает все пути из источника в сток.
2. Минимальным разрезом на взвешенном ориентированном графе G(X, U) называется разрез, суммарный вес дуг которого минимален.
Варианты разрезов вверху выделены красным цветом

Слайд 18

Обозначения и определения
Z(i,j) – булева переменная, равная единице, если дуга (i,j)

принадлежит минимальному разрезу и равная нулю в противном случае.
- множество дуг, принадлежащих d-у пути, ведущему из вершины-источника в вершину-сток .

Слайд 19

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

Слайд 20

Поиск минимального разреза перебором
Граф G(X,U)
1
4
3
2
2 7
5
9 3

Слайд 21

ТЕОРЕМА ФОРДА-ФАЛКЕРСОНА
Величина минимального разреза на взвешенном ориентированном графе равна величине максимального

потока.

Кратчайшие пути, максимальные потоки и минимальные разрезы на орграфах

Содержание

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИ На взвешенном ориентированном графе G(X,U)

ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ О КРАТЧАЙШЕМ ПУТИПоиск кратчайшего пути из s-й вершины

МЕТОД ПОТЕНЦИАЛОВШаг 1. Вершине присваивается потенциал P(s)=0.Шаг 2. Всем вершинам множества

ПРИМЕР 1Поиск длины кратчайшего пути из 1-й вершины в 4-ю. 1

ДОСТОИНСТВА И НЕДОСТАТКИДостоинства:Метод потенциалов гарантирует определение кратчайших путей из выбранной вершины

РЕШИТЬ САМОСТОЯТЕЛЬНО Определить кратчайшие пути из 1-й вершины во все остальные.1

МАКСИМАЛЬНЫЕ ПОТОКИ НА ГРАФАХСодержательная постановка задачи: требуется определить максимальный однородный поток

Формальная постановка задачи о максимальном однородном потокеОбозначения: f(i,j) – поток по

САМОСТОЯТЕЛЬНОДайте иную формальную постановку задачи о максимальном потоке, в которой: эмиссионная

ЧАСТО ИСПОЛЬЗУЕМЫЙ АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ПОТОКА Шаг 1. Полученный граф G(X,U’)

АЛГОРИТМ ПОИСКА МАКСИМАЛЬНОГО ПОТОКА (ПРОДОЛЖЕНИЕ) Шаг 5. На графе G(X,U) вес

ПРИМЕР 2a) Граф G(X,U). b) Граф G’(X,U’), S=4. a) b) S=5.

САМОСТОЯТЕЛЬНОСформулируйте достоинства приведенного выше алгоритма.Сформулируйте недостатки приведенного выше алгоритма.

Пример 3143265 1 1 1 1 2 1 1 1 1

САМОСТОЯТЕЛЬНО1. Сформулировать достоинства и недостатки алгоритма поиска максимального потока.2. Определить максимальный

МИНИМАЛЬНЫЕ РАЗРЕЗЫ НА ГРАФАХОпределения: 1. Разрезом на ориентированном графе G(X, U)

Обозначения и определенияZ(i,j) – булева переменная, равная единице, если дуга (i,j)