Курсовая работа на тему: Задача о максимальном потоке. Структура исходных данных задачи и результатов

Введение

Количество вещества, проходящего по дуге от i до j, будем называть потоком по дуге (i, j) и обозначать через Xij(0≤Xij≤dij). Если учесть, что все вещество, вошедшее в промежуточный пункт сети, должно полностью выйти из него, получаем ΣiXij=ΣkXjk, j=1,..n;

Из естественного требования равенства потоков на входе и на выходе имеем ΣiX0j=ΣiXjn=Z.

Величину Z называем величиной потока в сети и ставим задачу максимизации Z указанных выше условиях. Решение задачи можно осуществлять методами линейного программирования, но едва ли эта возможность осуществима для сколь-нибудь реальной сети. Остановимся на некоторых фундаментальных понятиях. Разобьем множество пунктов (вершин) сети на два подмножества U и V. Совокупность дуг, ведущих непосредственно из вершин множества U в вершины множества V называют разрезом сети, а число А(U, V)=Σdij называют пропускной способностью этого разреза. Очевидно, что поток в сети не превышает величины пропускной способности любого ее разреза и равен пропускной способности минимального разреза. Таким образом, поиск максимального потока сводится к поиску пропускной способности минимального разреза.

Оглавление

- Структура исходных данных задачи и результатов

- Алгоритм нахождения максимального потока в сети

- Описание пользовательского интерфейса программы

- Тестирование