Лабораторная работа № 20
ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ
1. ЦЕЛЬ РАБОТЫ
Сформировать у студентов знания, умения и навыки решения задачи о максимальном потоке в MathСad.
2. ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ
1. Изучите теоретическую часть. Выполните задание, соответствующее номеру Вашего варианта, и продемонстрируйте его преподавателю.
2. Оформите отчет по лабораторной работе, который должен содержать:
титульный лист (Рис. 2);
исходные данные варианта;
последовательность действий для решения задачи;
результаты решения задачи.
3. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ
Задача о максимальном потоке – одна из основных проблем в теории вычислительных систем. При ее решении необходимо подсчитать максимальное количество некоторых объектов, которые могут двигаться с одного конца сети в другой. При этом пропускная способность узлов сети ограничена. Задача о максимальном потоке решается при помощи графов. В задаче о максимальном потоке одна из вершин графа назначается истоком – точкой, в которой все объекты начинают свой путь, а другая – стоком – точкой, в которую они все направляются. Пропускная способность каждого ребра ограничена.
4. Образец выполнения
На рис. 9 представлена ориентированная сеть с максимальными пропускными способностями дуг. Найти максимальный поток автомашин (количество машин в час) для системы автодорог, представленной на этом графе.
Рис. 9. Исходные данные задачи
Решение:
5. Варианты заданий
Сеть содержит 10 вершин (рис. 10). Пропускная способность дуг заданы таблицей. Найти максимальный поток между вершинами 1 и 10.
Рис. 10. Данные задачи
|
начало |
конец |
Варианты | |||||||||||
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 | ||
|
длина |
длина |
длина |
длина |
длина |
длина |
длина |
длина |
длина |
длина |
длина |
длина | ||
|
1 |
2 |
4 |
9 |
12 |
10 |
9 |
12 |
9 |
13 |
13 |
9 |
5 |
8 |
|
1 |
3 |
13 |
12 |
9 |
13 |
11 |
12 |
8 |
10 |
1 |
10 |
14 |
11 |
|
1 |
4 |
14 |
4 |
9 |
11 |
3 |
12 |
7 |
5 |
4 |
7 |
15 |
3 |
|
2 |
5 |
7 |
10 |
7 |
11 |
2 |
3 |
7 |
12 |
9 |
5 |
6 |
9 |
|
2 |
7 |
7 |
3 |
3 |
4 |
1 |
4 |
14 |
6 |
4 |
11 |
6 |
2 |
|
3 |
6 |
13 |
4 |
14 |
9 |
13 |
5 |
1 |
1 |
1 |
11 |
14 |
3 |
|
4 |
6 |
6 |
15 |
5 |
7 |
15 |
5 |
13 |
8 |
8 |
12 |
7 |
14 |
|
4 |
7 |
9 |
13 |
12 |
9 |
3 |
2 |
12 |
10 |
4 |
13 |
8 |
12 |
|
5 |
7 |
6 |
8 |
11 |
5 |
14 |
15 |
5 |
3 |
9 |
8 |
8 |
7 |
|
5 |
8 |
2 |
4 |
9 |
13 |
1 |
11 |
4 |
5 |
10 |
15 |
9 |
4 |
|
5 |
10 |
2 |
10 |
2 |
2 |
10 |
8 |
8 |
14 |
8 |
12 |
11 |
9 |
|
6 |
7 |
4 |
15 |
11 |
3 |
6 |
4 |
9 |
6 |
10 |
1 |
8 |
14 |
|
6 |
8 |
9 |
14 |
11 |
15 |
3 |
3 |
3 |
11 |
13 |
9 |
9 |
12 |
|
6 |
9 |
14 |
7 |
5 |
7 |
7 |
5 |
11 |
8 |
10 |
11 |
8 |
6 |
|
7 |
10 |
10 |
9 |
15 |
10 |
6 |
11 |
2 |
8 |
6 |
3 |
11 |
8 |
|
8 |
10 |
15 |
10 |
9 |
8 |
15 |
8 |
15 |
13 |
4 |
2 |
11 |
11 |
|
9 |
10 |
10 |
5 |
7 |
1 |
12 |
11 |
8 |
11 |
13 |
13 |
11 |
4 |