Том 22, номер 3, 2015 г., Стр. 55–74

УДК 519.1 
Скороходов В. А., Чеботарёва А. С. 
Задача о максимальном потоке в сети с особыми условиями распределения потока

Аннотация:
Рассмотрена задача нахождения максимального потока в сетях с условиями жёсткого и нежёсткого распределения потока. Показано, что для каждого условия распределения решение рассматриваемой задачи существует и единственно. Разработаны алгоритмы нахождения максимального потока для каждого условия распределения потока, а также получены верхняя и нижняя оценки для величины максимального потока в сетях с условием жёсткого распределения.
Ил. 3, табл. 4, библиогр. 11.

Ключевые слова: сеть, граф, алгоритм на графах, максимальный поток в сети, распределение потока.

DOI: 10.17377/daio.2015.22.455

Скороходов Владимир Александрович ¹
Чеботарёва Анастасия Сергеевна ¹
1. Южный федеральный университет
ул. Мильчакова, 8а, 344090 Ростов-на-Дону, Россия
e-mail: pdvaskor@yandex.ru, chebot1988@yandex.ru

Статья поступила 16 июня 2014 г.
Исправленный вариант — 25 марта 2015 г.

Литература

[1] Ерзин А. И., Тахонов И. И. Задача поиска сбалансированного потока // Сиб. журн. индустр. математики. 2006. Т. 9, № 4. С. 50–63.

[2] Ерусалимский Я. М., Водолазов Н. Н. Нестационарный поток в сети // Вестн. ДГТУ. 2009. Т. 9, № 3. С. 402–409.

[3] Ерусалимский Я. М., Скороходов В. А., Кузьминова М. В., Петросян А. Г. Графы с нестандартной достижимостью: задачи, приложения. Ростов-на-Дону: Южный федеральный ун-т, 2009. 195 с.

[4] Кузнецов О. П., Жилякова Л. Ю. Двусторонние ресурсные сети: новая потоковая модель // Докл. АН. 2010. Т. 433, № 5. С. 609–612.

[5] Курош А. Г. Курс высшей алгебры. М: Наука, 1975. 431 c.

[6] Скороходов В. А. Потоки в сетях с меняющейся длительностью прохождения // Изв. вузов. Северо-Кавказ. регион. Естеств. науки. 2011. № 1. С. 21–26.

[7] Скороходов В. А. Потоки в обобщенных сетях со связанными дугами // Моделирование и анализ информ. систем. 2012. Т. 19, № 2. С. 41–52.

[8] Форд Л. Р., Фалкерсон Д. Р. Потоки в сетях. М: Мир, 1966. 276 c.

[9] Ahuja R. K., Magnanti T. L., Orlin J. B. Network flows: theory, algorithms, and applications. Upper Saddle River, NJ: Prentice-Hall Inc., 1993. 864 p.

[10] Fonoberova M. On determining the minimum cost flows in dynamic networks // Bul. Acad. Stiinte Repub. Moldova., Mat. 2006. No. 1. P. 51–56.

[11] Goldberg A. V., Rao S. Beyond the flow decomposition barrier // J. ACM. 1998. Vol. 45, No. 5. P. 783–797.