maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2015-4-533-545mais-271Research ArticleОригинальные статьиArticlesЗадача о наибольшем кратном потоке в делимой сети и ее частные случаиThe Problem of Finding the Maximal Multiple Flow in the Divisible Network and its Special CasesСмирновА. В.SmirnovA. V.

канд. физ.-мат. наук., доцент кафедры теоретической информатики

ул. Советская, 14, г. Ярославль, 150000 Россия

PhD

Sovetskaya str., 14, Yaroslavl, 150000, Russia

alexander_sm@mail.ruЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation201520082015224533545Copyright © Смирнов А.В., 20152015Смирнов А.В.Smirnov A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/271

В статье рассматривается задача о наибольшем кратном потоке в сети произвольной натуральной кратности k. Определяется три типа дуг в сети: обычная дуга, кратная дуга, мультидуга. Каждая кратная и мультидуга представляет собой объединение k связанных дуг, согласованных между собой. Задаются правила построения сети. Вводится понятие делимой сети и ряд связанных определений. Отмечается важная особенность делимых сетей – возможность разделить их на k частей, согласованных на связанных дугах кратных и мультидуг, таким образом, что каждая часть является обычной транспортной сетью. Основным результатом статьи является выделение следующих подклассов задачи о наибольшем кратном потоке в делимой сети.1. Делимая сеть с ограничениями на мультидуги. Если в k−1 части делимой сети имеется только одна вершина, являющаяся концом мультидуги, то задача о наибольшем потоке полиномиально разрешима.2. Делимая сеть со слабыми ограничениями на мультидуги. Если в s частях делимой сети (1 ≤ s < k − 1) имеется только одна вершина, являющаяся концом мультидуги, а в остальных частях таких вершин несколько, то размерность задачи о наибольшем кратном потоке может быть понижена до k − s.3. Делимая сеть параллельной структуры. Пусть компонента делимой сети, состоящая из всех кратных дуг, может быть разделена на субкомпоненты, содержащие ровно по одной вершиненачалу мультидуги. Пусть при этом каждая пара субкомпонент пересекается только в источнике сети x0. Если k = 2, то задача о максимальном кратном потоке разрешима за полиномиальное время. Если k ≥ 3, то задача NP-полна. Для каждого из полиномиальных подклассов получены алгоритмы. Также сформулирован алгоритм понижения размерности задачи для делимой сети со слабыми ограничениями на мультидуги.

In the article the problem of finding the maximal multiple flow in the network of any natural multiplicity k is studied. There are arcs of three types: ordinary arcs, multiple arcs and multi-arcs. Each multiple and multi-arc is a union of k linked arcs, which are adjusted with each other. The network constructing rules are described. The definitions of a divisible network and some associated subjects are stated. The important property of the divisible network is that every divisible network can be partitioned into k parts, which are adjusted on the linked arcs of each multiple and multi-arc. Each part is the ordinary transportation network. The main results of the article are the following subclasses of the problem of finding the maximal multiple flow in the divisible network. 1. The divisible networks with the multi-arc constraints. Assume that only one vertex is the ending vertex for a multi-arc in k −1 network parts. In this case the problem can be solved in a polynomial time. 2. The divisible networks with the weak multi-arc constraints. Assume that only one vertex is the ending vertex for a multi-arc in s network parts (1 ≤ s < k − 1) and other parts have at least two such vertices. In that case the multiplicity of the multiple flow problem can be decreased to k − s. 3. The divisible network of the parallel structure. Assume that the divisible network component, which consists of all multiple arcs, can be partitioned into subcomponents, each of them containing exactly one vertex-beginning of a multi-arc. Suppose that intersection of each pair of subcomponents is the only vertex-network source x0. If k = 2, the maximal flow problem can be solved in a polynomial time. If k ≥ 3, the problem is NP-complete. The algorithms for each polynomial subclass are suggested. Also, the multiplicity decreasing algorithm for the divisible network with weak multi-arc constraints is formulated.

кратные сетикратные потокиделимые сетиNP-полнотаполиномиальный алгоритмmultiple networksmultiple flowsdivisible networksNP-completenesspolynomial algorithmReferencesРублев В.С., Смирнов А.В., “Потоки в кратных сетях”, Ярославский педагогический вестник, 3:2 (2011), 60–68; [Rublev V. S., Smirnov A. V., “Flows in Multiple Networks”, Yaroslavsky Pedagogichesky Vestnik, 3:2 (2011), 60–68, (in Russian).]Рублев В.С., Смирнов А.В., “Потоки в кратных сетях”, Ярославский педагогический вестник, 3:2 (2011), 60–68; [Rublev V. S., Smirnov A. V., “Flows in Multiple Networks”, Yaroslavsky Pedagogichesky Vestnik, 3:2 (2011), 60–68, (in Russian).]Ford L. R., Fulkerson D. R., Flows in Networks, Princeton University Press, 1962.Ford L. R., Fulkerson D. R., Flows in Networks, Princeton University Press, 1962.Papadimitriou Ch. H., Steigliz K., Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1982.Papadimitriou Ch. H., Steigliz K., Combinatorial Optimization: Algorithms and Complexity, Prentice Hall, 1982.Рублев В.С., Смирнов А.В., “Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения”, Моделирование и анализ информационных систем, 17:2 (2010), 72–98; [Roublev V. S., Smirnov A. V., “The Problem of Integer-Valued Balancing of a Three-Dimensional Matrix and Algorithms of Its Solution”, Modeling and Analysis of Information Systems, 17:2 (2010), 72–98, (in Russian).]Рублев В.С., Смирнов А.В., “Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения”, Моделирование и анализ информационных систем, 17:2 (2010), 72–98; [Roublev V. S., Smirnov A. V., “The Problem of Integer-Valued Balancing of a Three-Dimensional Matrix and Algorithms of Its Solution”, Modeling and Analysis of Information Systems, 17:2 (2010), 72–98, (in Russian).]Смирнов А.В., “Некоторые классы разрешимости задачи целочисленного сбалансирования трехмерной матрицы с ограничениями второго рода”, Моделирование и анализ информационных систем, 20:2 (2013), 54–69; [Smirnov A. V., “Some Solvability Classes for The Problem of Integer Balancing of a Three-dimensional Matrix with Constraints of Second Type”, Modeling and Analysis of Information Systems, 20:2 (2013), 54–69, (in Russian).]Смирнов А.В., “Некоторые классы разрешимости задачи целочисленного сбалансирования трехмерной матрицы с ограничениями второго рода”, Моделирование и анализ информационных систем, 20:2 (2013), 54–69; [Smirnov A. V., “Some Solvability Classes for The Problem of Integer Balancing of a Three-dimensional Matrix with Constraints of Second Type”, Modeling and Analysis of Information Systems, 20:2 (2013), 54–69, (in Russian).]Smirnov A. V., “Some Solvability Classes for the Problem of Integer Balancing of a Three-Dimensional Matrix with Constraints of the Second Type”, Automatic Control and Computer Sciences, 48:7 (2014), 543–553.Smirnov A. V., “Some Solvability Classes for the Problem of Integer Balancing of a Three-Dimensional Matrix with Constraints of the Second Type”, Automatic Control and Computer Sciences, 48:7 (2014), 543–553.Корбут А.А., Финкельштейн Ю.Ю., Дискретное программирование, Наука, 1969; [Korbut A. A., Finkelstein J. J., Diskretnoe programmirovanie, Nauka, 1969, (in Russian).]Корбут А.А., Финкельштейн Ю.Ю., Дискретное программирование, Наука, 1969; [Korbut A. A., Finkelstein J. J., Diskretnoe programmirovanie, Nauka, 1969, (in Russian).]Раскин Л.Г., Кириченко И.О., Многоиндексные задачи линейного программирования, Радио и связь, 1982; [Raskin L. G., Kirichenko I. O., Mnogoindeksnye zadachi lineynogo programmirovaniya, Radio i svyaz, 1982, (in Russian).]Раскин Л.Г., Кириченко И.О., Многоиндексные задачи линейного программирования, Радио и связь, 1982; [Raskin L. G., Kirichenko I. O., Mnogoindeksnye zadachi lineynogo programmirovaniya, Radio i svyaz, 1982, (in Russian).]Spieksma F. C. R., “Multi index assignment problems: complexity, approximation, applications”, Nonlinear Assignment Problems. Algorithms and Applications, eds. P. M. Pardalos, L. S. Pitsoulis, Kluwer Academic Publishers, 2000, 1–11.Spieksma F. C. R., “Multi index assignment problems: complexity, approximation, applications”, Nonlinear Assignment Problems. Algorithms and Applications, eds. P. M. Pardalos, L. S. Pitsoulis, Kluwer Academic Publishers, 2000, 1–11.Афраймович Л.Г., “Трехиндексные задачи линейного программирования с вложенной структурой”, Автоматика и телемеханика, 2011, № 8, 109–120; English transl.: Afraimovich L. G., “Three-index linear programs with nested structure”, Automation and Remote Control, 72:8 (2011), 1679–1689.Афраймович Л.Г., “Трехиндексные задачи линейного программирования с вложенной структурой”, Автоматика и телемеханика, 2011, № 8, 109–120; English transl.: Afraimovich L. G., “Three-index linear programs with nested structure”, Automation and Remote Control, 72:8 (2011), 1679–1689.Кондаков А.С., Рублев В.С., “Задача сбалансирования матрицы плана”, Доклады Одесского семинара по дискретной математике, Астропринт, 2005, 24–26; [Kondakov A. S., Roublev V. S., “Zadacha sbalansirovaniya matritsy plana”, Doklady Odesskogo seminara po diskretnoy matematike, Astroprint, 2005, 24–26, (in Russian).]Кондаков А.С., Рублев В.С., “Задача сбалансирования матрицы плана”, Доклады Одесского семинара по дискретной математике, Астропринт, 2005, 24–26; [Kondakov A. S., Roublev V. S., “Zadacha sbalansirovaniya matritsy plana”, Doklady Odesskogo seminara po diskretnoy matematike, Astroprint, 2005, 24–26, (in Russian).]Коршунова Н.М., Рублев В.С., “Задача целочисленного сбалансирования матрицы”, Современные проблемы математики и информатики, ЯрГУ, 2000, 145–150; [Korshunova N. M., Roublev V. S., “Zadacha tselochislennogo sbalansirovaniya matritsy”, Sovremennye problemy matematiki i informatiki, Yaroslavl State University, 2000, 145– 150, (in Russian).]Коршунова Н.М., Рублев В.С., “Задача целочисленного сбалансирования матрицы”, Современные проблемы математики и информатики, ЯрГУ, 2000, 145–150; [Korshunova N. M., Roublev V. S., “Zadacha tselochislennogo sbalansirovaniya matritsy”, Sovremennye problemy matematiki i informatiki, Yaroslavl State University, 2000, 145– 150, (in Russian).]Смирнов А.В., “Задача целочисленного сбалансирования трехмерной матрицы и сетевая модель”, Моделирование и анализ информационных систем, 16:3 (2009), 70–76; [Smirnov A. V., “The Problem of Integer-valued Balancing of a Three-dimensional MatrixСмирнов А.В., “Задача целочисленного сбалансирования трехмерной матрицы и сетевая модель”, Моделирование и анализ информационных систем, 16:3 (2009), 70–76; [Smirnov A. V., “The Problem of Integer-valued Balancing of a Three-dimensional Matrixand Network Model”, Modeling and Analysis of Information Systems, 16:3 (2009), 70–76, (in Russian).]and Network Model”, Modeling and Analysis of Information Systems, 16:3 (2009), 70–76, (in Russian).]Афраймович Л.Г., Прилуцкий М.Х., “Многоиндексные задачи распределения ресурсов в иерархических системах”, Автоматика и телемеханика, 2006, №6, 194–205; English transl.: Afraimovich L. G., Prilutskii M. Kh., “Multiindex resource distributions for hierarchical systems”, Automation and Remote Control, 67:6 (2006), 1007–1016.Афраймович Л.Г., Прилуцкий М.Х., “Многоиндексные задачи распределения ресурсов в иерархических системах”, Автоматика и телемеханика, 2006, №6, 194–205; English transl.: Afraimovich L. G., Prilutskii M. Kh., “Multiindex resource distributions for hierarchical systems”, Automation and Remote Control, 67:6 (2006), 1007–1016.Афраймович Л.Г., Прилуцкий М.Х., “Многопродуктовые потоки в древовидных сетях”, Известия РАН. Теория и системы управления, 2008, №2, 57–63; English transl.: Afraimovich L. G., Prilutskii M. Kh., “Multicommodity flows in tree-like networks”, Journal of Computer and Systems Sciences International, 47:2 (2008), 214–220.Афраймович Л.Г., Прилуцкий М.Х., “Многопродуктовые потоки в древовидных сетях”, Известия РАН. Теория и системы управления, 2008, №2, 57–63; English transl.: Afraimovich L. G., Prilutskii M. Kh., “Multicommodity flows in tree-like networks”, Journal of Computer and Systems Sciences International, 47:2 (2008), 214–220.Hoffman A. J., Kruskal J. B., “Integral Boundary Points of Convex Polyhedra”, Linear Inequalities and Related Systems, eds. H. W. Kuhn, A. W. Tucker, Princeton University Press, 1972, 223–246.Hoffman A. J., Kruskal J. B., “Integral Boundary Points of Convex Polyhedra”, Linear Inequalities and Related Systems, eds. H. W. Kuhn, A. W. Tucker, Princeton University Press, 1972, 223–246.Рублев В.С., Смирнов А.В., “NP-полнота задачи целочисленного сбалансирования трехмерной матрицы”, Доклады Академии Наук, 435:3 (2010), 314–316; English transl.: Roublev V. S., Smirnov A. V., “NP-Completeness of the Integer Balancing Problem for a Three-Dimensional Matrix”, Doklady Mathematics, 82:3 (2010), 912–914.Рублев В.С., Смирнов А.В., “NP-полнота задачи целочисленного сбалансирования трехмерной матрицы”, Доклады Академии Наук, 435:3 (2010), 314–316; English transl.: Roublev V. S., Smirnov A. V., “NP-Completeness of the Integer Balancing Problem for a Three-Dimensional Matrix”, Doklady Mathematics, 82:3 (2010), 912–914.Смирнов А.В., “Некоторые полиномиальные подклассы задачи о наибольшем кратном потоке в делимой сети”, Дискретные модели в теории управляющих систем: IX Международная конференция: труды, МАКС Пресс, 2015, 229–231; [Smirnov A.V., “Nekotorye polinomialnye podklassy zadachi o naibolshem kratnom potoke v delimoy seti”, Discrete Models in Control Systems Theory: IX International Conference: Proceedings, MAKS Press, 2015, 229–231, (in Russian).]Смирнов А.В., “Некоторые полиномиальные подклассы задачи о наибольшем кратном потоке в делимой сети”, Дискретные модели в теории управляющих систем: IX Международная конференция: труды, МАКС Пресс, 2015, 229–231; [Smirnov A.V., “Nekotorye polinomialnye podklassy zadachi o naibolshem kratnom potoke v delimoy seti”, Discrete Models in Control Systems Theory: IX International Conference: Proceedings, MAKS Press, 2015, 229–231, (in Russian).]Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP- Completeness, W. H. Freeman, 1979.Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP- Completeness, W. H. Freeman, 1979.Karp R., “Reducibility among combinatorial problems”, Complexity of Computer Computations, eds. R. E. Miller, J. W. Thatcher, Plenum, 1972, 85–103.Karp R., “Reducibility among combinatorial problems”, Complexity of Computer Computations, eds. R. E. Miller, J. W. Thatcher, Plenum, 1972, 85–103.

The authors declare that there are no conflicts of interest present.