|
УДК 519.1
Х.Н. Абдулрахман1, Я.М. Ерусалимский2
О реализуемости потоков в классических сетях потоками в ресурсных сетях
1 ФГБОУ ВО «Ростовский государственный университет путей сообщения»; Россия, 344038, г. Ростов-на-Дону, пл. Ростовского стрелкового полка народного ополчения, 2; haidar_74@mail.ru 2 ФГАОУ ВО «Южный федеральный университет»; Россия 344006 г. Ростов-на-Дону, ул. Большая Садовая, 105/42; ymerusalimskiy@sfedu.ru
В статье рассматривается задача построения ресурсной сети, поток в которой совпадает с заданным потоком в исходной классической сети (т. е. сети, содержащей источник и сток).
Доказано, что эта задача имеет решение (теорема 1). Получено необходимое условие на количество ресурса, распределенного в вершинах ресурсной сети (теорема 2). Введено понятие локального подобия ресурсных сетей. Это позволило доказать теорему 3, из которой следует, что решение задачи построения ресурсной сети, реализующей поток в классической сети, не определено однозначно.
Приведено большое количество примеров, иллюстрирующих полученные результаты.
Ключевые слова: сеть, ресурсная сеть, поток в сети, пропускная способность, максимальный поток, начальное состояние.
UDK 519.1
H.N. Abdulrahman1, I.M. Erusalimskiy2
On the Realizability of Flows in Classical Networks by Flows in Resource Networks
1 Rostov State Transport University (RSTU); Russia, Rostovskogo Strelkovogo Polka Narodnogo Opolcheniya Sq. 2, Rostov-on-Don, 344038; haidar_74@mail.ru 2 Southern Federal University; Russia, Bolshaya Sadovaya st. 105/42, Rostov-on-Don, 344006; ymerusalimskiy@sfedu.ru
The article deals with the problem of constructing a resource network in which the flow coincides with a given flow in the original classical network (i.e., a network containing a source and a drain).
It is proved that this problem has a solution (Theorem 1). The necessary condition for the amount of resource distributed at the vertices of the resource network is obtained (Theorem 2). The concept of local similarity of resource networks is introduced. This has made it possible to demonstrate the theorem 3, suggesting that the problem of constructing a resource network implementing a flow in a classical network is not uniquely determined.
The article contains many examples illustrating the results obtained.
|