Потоки в обобщенных сетях со связанными дугами
https://doi.org/10.18255/1818-1015-2012-2-41-52
Аннотация
Приведены основные формулировки и определения для обобщенных сетей со связанными дугами. Показано, что для таких сетей не выполняется теорема Форда и Фалкерсона о том, что величина максимального потока в сети равна пропускной способности минимального разреза. Получены точные оценки (сверху и снизу) для величины максимального потока в обобщенной сети со связанными дугами. Кроме того, предложен алгоритм нахождения максимального потока для рассматриваемых сетей.
Об авторе
Владимир Александрович Скороходов
Южный федеральный университет
Россия
факультет математики, механики и компьютерных наук, кафедра алгебры и дискретной математики, доцент
Россия
факультет математики, механики и компьютерных наук, кафедра алгебры и дискретной математики, доцент
Список литературы
1. Ерусалимский Я.М., Скороходов В.А. Потоки в сетях со связанными дугами // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2003. 8. С. 3–8.
2. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. М.: Вузовская книга, 2001. 279 с.
3. Берж К. Теория графов и ее применения. –М.:Изд–во иностранной литературы, 1962. 319с.
4. Кофман А. Введение в прикладную комбинаторику. –М.: Наука, 1975. 480с.
5. Ерусалимский Я.М., Скороходов В.А. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 2003. 2. С. 3–5.
6. Ерусалимский Я.М., Скороходов В.А. Прибыль от потоков с обратной связью в орсетях с ограничениями на достижимость // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2003. 8. С. 9–12.
Рецензия
Для цитирования:
Скороходов В.А. Потоки в обобщенных сетях со связанными дугами. Моделирование и анализ информационных систем. 2012;19(2):41-52. https://doi.org/10.18255/1818-1015-2012-2-41-52
For citation:
Skorokhodov V.A. Flows in Generalized Nets with Related Arcs. Modeling and Analysis of Information Systems. 2012;19(2):41-52. (In Russ.) https://doi.org/10.18255/1818-1015-2012-2-41-52
Просмотров:
890
Послать статью по эл. почте 