Flows in Generalized Nets with Related Arcs
https://doi.org/10.18255/1818-1015-2012-2-41-52
Abstract
The problem of finding the maximum flow in nets of a special form is considered. In such nets the arcs are related in such a way that the total flow passing through the related arcs does not exceed the minimum throughput of these arcs. It is shown that the theorem by Ford and Fulkerson, according to which the maximum flux value is equal to the throughput of a minimum cut, is not performed for such networks. The estimations of the maximum flow in a generalized net with bound arcs are proposed. And the algorithm for finding the maximum flow in such nets is developed.
About the Author
V. A. Skorokhodov
Южный федеральный университет
Russian Federation
факультет математики, механики и компьютерных наук, кафедра алгебры и дискретной математики, доцент
Russian Federation
факультет математики, механики и компьютерных наук, кафедра алгебры и дискретной математики, доцент
References
1. Ерусалимский Я.М., Скороходов В.А. Потоки в сетях со связанными дугами // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2003. 8. С. 3–8.
2. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. М.: Вузовская книга, 2001. 279 с.
3. Берж К. Теория графов и ее применения. –М.:Изд–во иностранной литературы, 1962. 319с.
4. Кофман А. Введение в прикладную комбинаторику. –М.: Наука, 1975. 480с.
5. Ерусалимский Я.М., Скороходов В.А. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. 2003. 2. С. 3–5.
6. Ерусалимский Я.М., Скороходов В.А. Прибыль от потоков с обратной связью в орсетях с ограничениями на достижимость // Известия ВУЗов. Северо-Кавказский регион. Естественные науки. Приложение. 2003. 8. С. 9–12.
Review
For citations:
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
Views:
888
Email this article 