Алгоритмы и структуры данных. Потоковые алгоритмы
Актанорович С.В., Волосевич А.А., Сиротко С.И.Задача нахождения максимального потока в сети довольно часто возникает на практике, а также является подзадачей при решении более крупного класса задач. Многие задачи комбинаторной оптимизации могут быть сформулированы в терминах задачи о максимальном потоке. Методическое пособие составлено в соответствии с рабочей программой курса «Теория графов. Потоковые алгоритмы». В пособие включены базовые определения теории графов и основные результаты теории потоков на взвешенных однородных сетях. В пособии описаны алгоритмы нахождения максимального потока в сети и максимального паросочетания в двудольном графе. В пособии приводится реализация полученных алгоритмов на языке программирования C++. Предполагается, что читатель пособия знаком с основами теории графов, а также владеет базовыми навыками программирования на языке C++. Пособие может быть рекомендовано студентам и магистрантам технических специальностей для изучения основ теории потоков.
Введение
1. Основные понятия теории графов
2. Структуры данных и базовые алгоритмы
3. Максимальный поток в сети
4. Паросочетания в двудольных графах
Литература.