Построение потоков максимальной мощности. Алгоритм Форда-Фалкерсона

 

1. Теоретическая часть:

2. Что называется сетью?

3. Определение «сток» и «исток» на сети.

4. Поток на сети.

5. Мощность потока на сети.

6. Пропускная способность дуг.

7. Разрез на сети.

8. Пропускная способность разреза.

9. Теорема Форда-Фалкерсона.

10. Прямая и обратная дуга.

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

12. Алгоритм построения потока с двойным ограничением потока по дугам.

13. Алгоритм построения потока в сети с несколькими источниками-стоками.

14. Алгоритм построения потока в сети с неориентированными ребрами.

15. Алгоритм построения потоков в сети с пропускными способностями узлов.

 

Практическая часть:

В соответствии с вариантом для данной сети:

- определить максимальный поток на сети;

- построить разрез на сети;

- определить пропускную способность разреза

 

Вариант №1

Вариант №2

Вариант №3

Вариант №4

Вариант №5

Вариант №6

Вариант №7

Вариант №8

Вариант №9

Вариант №10

Вариант №11

Вариант №12

Вариант №13

Вариант №14

Вариант №15

Вариант №16

Вариант №17

Вариант №18

Вариант №19

Вариант №20

Вариант №21

Вариант №22

 

Вариант №23

Вариант №24

Вариант №25

Вариант №26

Вариант №27

Вариант №28

Вариант №29

Вариант №30