Цель работы. Сформировать у студентов знания, умения и навыки решения задачи о максимальном потоке в mathсad

Сформировать у студентов знания, умения и навыки решения задачи о максимальном потоке в MathСad.

ПОРЯДОК ВЫПОЛНЕНИЯ РАБОТЫ

1. Изучите теоретическую часть. Выполните задание, соответствующее номеру Вашего варианта, и продемонстрируйте его преподавателю.

2. Оформите отчет по лабораторной работе, который должен содержать:

· титульный лист (Рис. 2);

· исходные данные варианта;

· последовательность действий для решения задачи;

· результаты решения задачи.

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Задача о максимальном потоке – одна из основных проблем в теории вычислительных систем. При ее решении необходимо подсчитать максимальное количество некоторых объектов, которые могут двигаться с одного конца сети в другой. При этом пропускная способность узлов сети ограничена. Задача о максимальном потоке решается при помощи графов. В задаче о максимальном потоке одна из вершин графа назначается истоком – точкой, в которой все объекты начинают свой путь, а другая – стоком – точкой, в которую они все направляются. Пропускная способность каждого ребра ограничена.