Задача нахождения непересекающихся и несовпадающих циклов на сети
Рассмотрена задача нахождения непересекающихся и несовподающих циклов на сети с двумя весами дуг. Показано, что она может быть сформулирована как задача нахождения непересекаюшихся совершенных паросочетаний на двудольном графе. Когда веса дуг равные, данная задача эквивалентна задаче нахождения пото...
Збережено в:
| Опубліковано в: : | Теорія оптимальних рішень |
|---|---|
| Дата: | 2003 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2003
|
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/84868 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Задача нахождения непересекающихся и несовпадающих циклов на сети / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 155-161. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859829116196356096 |
|---|---|
| author | Шарифов, Ф.А. |
| author_facet | Шарифов, Ф.А. |
| citation_txt | Задача нахождения непересекающихся и несовпадающих циклов на сети / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 155-161. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Теорія оптимальних рішень |
| description | Рассмотрена задача нахождения непересекающихся и несовподающих циклов на сети с двумя весами дуг. Показано, что она может быть сформулирована как задача нахождения непересекаюшихся совершенных паросочетаний на двудольном графе. Когда веса дуг равные, данная задача эквивалентна задаче нахождения потока минимальной стоимости на сети представленой двудольным графом. Для последней задачи разработаны ряд строгих полиномиальных алгоритмов. В общем случае рассмотренная задача не имеет целочисленное решение. В работе приводятся основные этапы полиномиального алгоритма для решения задачи в общем случае.
Разглянуто задачу знаходження циклів на мережі, що не перетинаються і не співпадають. Показано, що ця задача еквівалентна задачі знаходження двох паросполучень на двудольному графі. В окремих випадках розглянута задача є задачею знаходження потоку мінімальної вартості. Наведено, що ці властивості є основними для разробки поліноміального алгоритму вирішення задачі.
We study a minimum cost node and arc-disjoint cycles problem on a directed graph. It is shown that the problem is equivalent to the minimum cost disjoint matchings problem on complete bipartite graph. In particular case, for which weights of arcs are special, then the considered problem is reduced to minimum cost flow problem. Some interesting properties of LP-relaxation problem are proved and it is noted that namely these properties are on bases for polynomial algorithm to solve the problem.
|
| first_indexed | 2025-12-07T15:31:06Z |
| format | Article |
| fulltext |
Теорія оптимальних рішень. 2003, № 2 155
ÒÅÎвß
ÎÏÒÈÌÀËÜÍÈÕ
вØÅÍÜ
Рассмотрена задача нахождения
непересекающихся и несовподаю-
щих циклов на сети с двумя веса-
ми дуг. Показано, что она может
быть сформулирована как задача
нахождения непересекаюшихся
совершенных паросочетаний на
двудольном графе. Когда веса дуг
равные, данная задача эквива-
лентна задаче нахождения пото-
ка минимальной стоимости на
сети представленой двудольным
графом. Для последней задачи
разработаны ряд строгих поли-
номиальных алгоритмов. В общем
случае рассмотренная задача не
имеет целочисленное решение. В
работе приводятся основные
этапы полиномиального алгорит-
ма для решения задачи в общем
случае.
© Ф.А. Шарифов, 2003
ÓÄÊ.519.8
Ô.À. ØÀÐÈÔÎÂ
ÇÀÄÀ×A ÍÀÕÎÆÄÅÍÈß
ÍÅÏÅÐÅÑÅÊÀÞÙÈÕÑß È
ÍÅÑÎÂÏÀÄÀÞÙÈÕ ÖÈÊËÎÂ
ÍÀ ÑÅÒÈ
Выбор n работников для выполнения n ви-
дов работ ежедневно осуществляется опти-
мальным образом путем решения задачи на-
значения, и после чего требуется организо-
вать новое предприятие, тем самым опреде-
лить число и состав его подразделений. При
выполнении работ на длительный срок часто
случается, что внутри одного подразделения
один работник временно заменяет другого и
такая замена сопряжена с некоторыми затра-
тами. Для эффективного функционирования
предприятия, время от времени, требуется
проверить качество выполняемых работ при
условии, что любой работник не может вы-
полнять и проверять качество одной той же
работы одновременно. Проверка качества
выполняемой работы, работником не выпол-
няющим эту работу, также связана с некото-
рыми затратами. В этих условиях требуется
найти число и состав подразделений для вы-
полнения и проверки качества выполняемых
работ таким образом, чтобы минимизировать
суммарные затраты. Эта задача может быть
сформулирована на сети следующим обра-
зом.
Пусть задан ориентированный граф
),( EVG = вершины которого соответствуют
работникам ( nV =|| ) и каждой дуге ),( ji из
E приписаны два неотрицательных веса ijp
и ijq , где ijp , ijq –заданные затраты на замену
работника i с работником j и на проверку
качества выполняемой работы работником i
со стороны работника j , соответственно.
Ф.А. ШАРИФОВ
Теорія оптимальних рішень. 2003, № 2 156
Чередующаяся последовательность различных вершин и дуг nn vevev ,,...,,, 110 , в
которой все дуги ie = ),( 1 ii vv − , ориентированы от вершины 1−iv к вершине iv ,
называется путем на графе G . Под циклом на графе G будем понимать любой
путь, в которой вершины 0v и nv совпадают. Из определения цикла получается,
что путь 00111100 ),,(,),,(, vvvevvvev == тоже является циклом. Графы
)(),( qGpG означают копии графа G с весами их дуг ijp , ijq , соответственно.
Допустим, что C – некоторый цикл на графе )( pG или )(qG . Вес цикла C оп-
ределяется как сумма весов его дуг на графе )( pG или )(qG , соответственно.
Копией цикла C называется такой же цикл на графе G .
Копии циклов на графе )( pG , ))(( qG будем называть непересекающимися,
если они не имеют общих вершин. Циклы pC и qC на графах )( pG и )(qG бу-
дем называть несовпадающими, если их копии на графе G не имеют общих дуг.
Выше упомянутая задача для создания нового предприятия может быть
сформулирована как задача нахождения непересекающихся и несовпадающих
циклов (ЗННЦ) на сети G с двумя весами дуг следующим образом.
Найти непересекающиеся циклы на графах )( pG и )(qG при условии, что,
копии любого цикла на графе )( pG и копии любого цикла на графе )(qG не-
совпадают на графе G , все вершины графа G являются вершинами нересе-
каюшихся циклов на графах )( pG и )(qG таким образом, что сумма весов цик-
лов на графах )( pG и )(qG минимальная.
Задачи нахождения различных циклов на множестве ребер графа исследова-
ны во многих работах. Мы отметим только 3 из них, которые более близкие
ЗННЦ. В работе [1] рассмотрена задача синтеза 2– связных сетей, в которой на
длины циклов есть ограничение сверху. Для решения этой задачи применяется
метод отсечения. Для сужения области допустимых решений задачи, получен-
ной путем релаксации исходной, используются неравенства, которые описывают
грани рассмотренной задачи. В работах [2, 3] рассмотрены задачи синтеза проч-
ных и 2– связных сетей. В этих работах исследуются свойства задачи, полу-
ченные путем релаксации исходных задач, и показаны, что если граф представ-
ляющий сеть, полный и веса его ребер удовлетворяют неравенству треугольни-
ка, то алгоритмы решения задачи коммивояжера могут быть применены для ре-
шения этих же задач. Мы покажем, что в случае, когда ijij qp = для всех дуг
),( ji из E , решение ЗННЦ сводится к решению задачи нахождения потока ми-
нимальной стоимости на сети, которая представляется двудольным графом. Для
решения последней задачи на произвольной сети предложены строго полиноми-
альные алгоритмы в [4, 5, 6]. В случае произвольных весов ijp и ijq построим
пример показывающий, что задача полученная путем релаксации ЗННЦ не все-
гда имеет целочисленное (0,1) решение. Тем не менее, основываясь на некото-
ЗАДАЧА НАХОЖДЕНИЯ НЕПЕРЕСЕКАЮЩИХСЯ …
Теорія оптимальних рішень. 2003, № 2 157
рых свойствах (см. ниже) ЗННЦ, отметим, что ЗННЦ допускает полиномиаль-
ный алгоритм ее решения. Для удобства доказательства свойств ЗННЦ рассмот-
рим полный неориентированный двудольный граф ),,( bbbb EVUG = с множест-
вами вершин bU , bV и с множеством ребер bE , где )( VnnVU bb === . Каждое
ребро ),( ji из bE соединяет вершину i из bU с вершиной j из bV . Ребрам ),( ii
из bE сопоставим дос-таточно большие веса, т.е. положим Mqp iiii == для
всех ni ,...,1= , а остальным
ребрам ),( ji из bE припишем веса ijij qp ,` . На графе bG рассмотрим задачу
нахож-дения двух непересекающихся паросочетаний с суммарными минималь-
ными весами:
∑∑∑∑
====
+
n
j
ijij
n
i
n
j
ijij
n
i
yqxp
1111
min (1)
∑
=
=
n
i
ijx
1
,1 ∑
=
=
n
i
ijy
1
,1 nj ,...,1= , (2)
∑
=
=
n
j
ijx
1
,1 ∑
=
=
n
j
ijy
1
,1 ni ,...,1= , (3)
,1≤+ ijij yx nji ,...,1, = , (4)
,0≥ijx ,0≥ijy nji ,...,1, = , (5)
,10 ∨=ijx ,10 ∨=ijy nji ,...,1, = . (6)
Теорема 1. Задача нахождения непересекающихся и несовпадающих циклов
на сети G и задача (1)-(6) эквивалентные.
Доказательство. Пусть }),(;{
*
* bij Ejixx ∈= и }),(;{
*
* bij Ejiyy ∈= опти-
мальное решение задачи (1)-(6). Понятно, что множества ребер
}),(,1);,{(
*
1 bij EjixjiM ∈== и }),(,1);,{(
*
2 bij EjiyjiM ∈== являются совер-
шенными паросочетаниями на графе bG . Так как Mqp iiii == для ребер ),( ii ,
то паросочетания 21, MM не содержат ребра ),( ii для произвольного ni ≤≤1 .
Каждому ребру ),( ji паросочетания 1M соответствует дуга ),( ji графа G , ко-
торая ориентирована от вершины i к вершине j . Не трудно проверить, что реб-
рам паросочетания 1M соответствуют непересекающиеся циклы на графе )( pG
и поэтому их копии тоже непересекаются на графе G . Аналогичным образом
показывается, что ребрам паросочетания 2M соответствуют непересекающиеся
циклы на графах G и )(qG . По условиям (4) паросочетания 21, MM не имеют
общих ребер bEji ∈),( . Отсюда следует, что копии циклов на графах )( pG и
)(qG не совпадают на графе G , что и доказывает теорему.
Ф.А. ШАРИФОВ
Теорія оптимальних рішень. 2003, № 2 158
Задачу (1)-(5) назовем LP – релаксацией задачи (1)-(6). Рассмотрим частный
случай задачи (1)-(6) когда веса всех дуг удовлетворяют следующим условиям:
11
jiijij vucp ++= ,
22
jiijij vucq ++= , Eji ∈),( , (7)
для некоторых чисел
2121
,,,, jjii vvuu .
Утверждение 1. Если условия (7) верны, то LP – релаксации задачи (1)-(6)
имеет целочисленное 1,0 оптимальное решение.
Доказательство. Допустим, что условия (7) верны. В этом случае задача
(1)-(6) преобразуется к следующей задаче нахождения минимального потока
(ЗНМП).
∑∑
= =
n
i
n
j
ijij zc
1 1
min
,,,1,2
1
∑
=
==
n
j
ij niz K ,,,1,2
1
∑
=
==
n
i
ij njz K .10 ∨=ijz
Из теории решения транспортных задач известно, что после замены условия
10 ∨=ijz на условие 10 ≤≤ ijz для всех ),( ji из E , полученная задача тоже
имеет целочисленное 1,0 оптимальное решение. Отсюда следует справедливость
утверждения.
Выполнение условий (7) для весов ребер графов )( pG и )(qG можно про-
верить за )( 3
nO времени следующим образом. Пусть ijijij qp −=δ для ребер
bEji ∈),( , ji ≠ , и Mii =δ для ребер bEii ∈),( . Допустим, что найдено решение
задачи назначения на двудольном графе bG с весами ijδ ребер bEji ∈),( , и iu ,
jv - оптимальные значения потенциалов для вершин bUi ∈ и bVj ∈ . Если
ijij uv −=δ для всех ребер bEji ∈),( , ji ≠ , то условия (7) верны для весов ре-
бер графов )( pG и )(qG . Легко показать, что обратное утверждение тоже вер-
но. Поэтому путем решения задачи назначения с одним из известных алгорит-
мов в [7], выполнимость условий (7) можно проверить за )( 3
nO времени. Если
ответ положительный, то решение ЗННЦ сводится к решению задачи нахожде-
ния потока минимальной стоимости. Для ее решения можно применить один из
вышеупомянутых строго полиномиальных алгоритмов. Однако на практике са-
мым эффективным является специализированный симплекс метод (метод потен-
циалов [8]) с использованием древовидных структур для представления данных.
Теперь предположим, что для весов ребер графов )( pG и )(qG условия (7)
не выполняются. Рассмотрим пример со следующими матрицами P и Q , где
ЗАДАЧА НАХОЖДЕНИЯ НЕПЕРЕСЕКАЮЩИХСЯ …
Теорія оптимальних рішень. 2003, № 2 159
005
050
500
=P и
050
005
500
=Q .
Если положить
2
1
=ijx и
2
1
=ijy для всех нулевых элементов ),( ji матрицы
QP, соответственно, то находим оптимальное решения задачи (1)-(5) (релакса-
ции ЗННЦ) с оптимальным значением 0. Легко проверить, что оптимальное зна-
чение ЗННЦ равно 5. Этот пример показывает, что не всегда LP –релаксации
задачи (1)-(6) имеют целочисленное 0,1 оптимальное решение. Допустим, что
}),(;{
*
* bij Ejixx ∈= и }),(;{
*
* bij Ejiyy ∈= оптимальное решение задачи (1)-(5) .
Теорема 2. Пусть существуют два совершенных непересекающихся паросо-
четаний ,xM yM такие, что }),(,0);,{(
*
bijxx EjixjiEM ∈>=⊆ и
}),(,0);,{(
*
bijyy EjiyjiEM ∈>=⊆ и ребра ),( lk , для которых 1
**
=+ klkl yx ,
являются ребрами либо паросочетания xM , либо yM . Тогда вектора инцидент-
ности паросочетаний xM и yM являются оптимальным решением задачи (1)-(6).
Доказательство. Пусть )( pv , )( pu , )(qv , )(qu , w – вектора двойственных
переменных, где )( pv , )( pu и )(qv , )(qu , соответствуют ограничениям из (2),
(3) которые содержат переменные ijx и ijy соответственно, а вектор w соот-
ветствует ограничениям (4). Из второй теоремы двойственности линейного про-
граммирования следует, что если 1**
<+ ijij yx то 0=ijw , и если 0
*
>ijx ,
0
*
>ijy , то ijijij pwpupv =+− )()( , ijijij qwquqv =+− )()( . Поэтому для суммы
весов )(,)( yx MqMp паросочетания yx MM , имеем следующее равенство,
=+=+ ∑ ∑
∈ ∈x yMij Mij
ijijyx qpMqMp
)( )(
)()(
∑ ∑∑∑∑∑
∈ ∈====
++−+−
x yMij Mij
ijij
n
i
i
n
j
j
n
i
i
n
j
j wwquqvpupv
)( )(1111
)()()()( .
При 1**
<+ ijij yx , так как 0=ijw и ребра ),( ji , для которых 1**
=+ ijij yx явля-
ются ребрами либо паросочетания xM , либо yM , то значение выражения в пра-
вой части этого равенства равно значению целевой функции двойственной зада-
чи к задаче (1)-(5). Поэтому вектора инцидентности паросочетаний xM и yM
являются оптимальным решением задачи (1)-(6).
Согласно этой теореме получаем интересное свойство задачи (1)-(5). Пусть
xyE – пересечение множеств ребер yx EE , и граф xyG определяется множеством
Ф.А. ШАРИФОВ
Теорія оптимальних рішень. 2003, № 2 160
ребер xyE . Ясно, что xyG двудольный граф и в общем случае может быть не
связным. Обозначим через )(,),1( kGG xyxy K компоненты связности графа xyG .
Допустим, что для произвольного t , граф )(tGxy содержит цикл, проходящий
через все его вершины. В этом случае, как следствие второй теоремы двойствен-
ности линейного программирования можно доказать, что существуют два непе-
ресекающихся совершенных паросочетаний xM и yM во множествах yx EE ,
соответственно, такие, что вектора инцидентности их являются оптимальным
решением задачи (1)-(6), и поэтому они оптимальное решение ЗННЦ. Таким об-
разом, если математически сформулировать, что в оптимальном решения задачи
(1)-(5) для произвольного t граф )(tGxy должен содержат цикл проходящий че-
рез все его вершины, как отдельное ограничение и добавить это условие в каче-
стве ограничений к задаче (1)-(5), тогда можем гарантировать целочисленность
оптимального решения полученной задачи. Так как графы )(tGxy заранее не из-
вестные, поэтому не возможно предварительно сформулировать что они содер-
жат цикл, проходящий через все их вершины в оптимальном решения задачи (1)-
(5), как условия гарантирующие целочисленность оптимального решения этой
задачи. Эти условия формулируются в процессе решения ЗННЦ следующим об-
разом.
1.Пусть паросочетания xM и yM оптимальные решение задач назначений
на графах )( pG и )(qG . В оптимальном решения ЗННЦ значения переменных
ijx и kly равные единице для некоторых ребер ),(),,( lkji паросочетании xM и
yM , соответственно.
2. Для произвольных чисел
2121
,,,, jjii vvuu если положить
11
: jiijij vupp +−= , и
22
: jiijij vuqq +−= то полученная задача и ЗННЦ эквива-
лентные .
3. Если ijij qp = для некоторой дуги ),( ji , то после замены переменных ijx
и ijy на новую переменную ijz в i – е и j – е ограничениях (2) и (3), а также ог-
раничение 1≤+ ijij yx на ограничение 10 ≤≤ ijz , полученная задача и ЗННЦ эк-
вивалентные.
С учетом свойства 1 и 2, путем решения задач назначений на графах )( pG
и )(qG находим паросочетания xM , yM на этих графах и числа
2121
,,,, jjii vvuu , такие, что после переопределения значении весов дуг как в
свойстве 2, получим, что ijij qp = для нескольких ребер ),( ji графа bG . При
этом паросочетания xM и yM либо не пересекаются т.е. не имеют общих ребер
ЗАДАЧА НАХОЖДЕНИЯ НЕПЕРЕСЕКАЮЩИХСЯ …
Теорія оптимальних рішень. 2003, № 2 161
(в этом случае, вектора инцидентности xM и yM – оптимальное решение
ЗННЦ), либо все подграфы )(tGxy содержат циклы про-ходящие через все их
вершины. Это означает, что для ребер ),( ji графов )(tGxy проведены заме-
ны указанные в свойстве 3 и тем самым решение ЗННЦ сводится к решению
ЗНМП на сети представленной двудольным графом xyG . Отметим, что на базе
свойств 1, 2 и 3 разработан строго полиномиальный алгоритм для решения
ЗННЦ и его детальное изложение и обоснование есть тема отдельной статьи.
Ф.А. Шаріфов
ЗАДАЧА ЗНАХОДЖЕННЯ НЕ ПЕРЕТИНАЮЧИХ І НЕ СПІВПАДАЮЧИХ ЦИКЛІВ НА
МЕРЕЖІ
Разглянуто задачу знаходження циклів на мережі, що не перетинаються і не співпадають.
Показано, що ця задача еквівалентна задачі знаходження двох паросполучень на двудольно-
му графі. В окремих випадках розглянута задача є задачею знаходження потоку мінімальної
вартості. Наведено, що ці властивості є основними для разробки поліноміального алгоритму
вирішення задачі.
F.A. Sharifov
MINIMUM COST NODE AND ARC DISJOINT CYCLES PROBLEM
We study a minimum cost node and arc-disjoint cycles problem on a directed graph. It is shown that
the problem is equivalent to the minimum cost disjoint matchings problem on complete bipartite
graph. In particular case, for which weights of arcs are special, then the considered problem is re-
duced to minimum cost flow problem. Some interesting properties of LP-relaxation problem are
proved and it is noted that namely these properties are on bases for polynomial algorithm to solve
the problem.
1. Fortz B., Labbe M. Polyhedral results for two-connected network with bounded rings // Math.
Prog. – 2002. – 3 – P. 27–54.
2. Goemans M.X., Bertsimans D. J. Survivable networks, linear programming relaxation and the
persimonions property // Math. Prog. – 1993. – 60 –. P. 145–166.
3. Шарифов Ф.А., Прудкой Ю.И., Фигурская И.Л., Трубина Л.В. Задача синтеза интегриро-
ванных цифровых сетей // Методы решения экстремальных задач. – Киев: Ин-т киберне-
тики им. В.М. Глушкова НАН Украины. – 1996. – С. 10–14.
4. Ahuja R.K., Thomas L., etc. Some resent advances in network flows // SIAM Review. – 1991. –
33. – № 2 – P. 175–219.
5. Vygen J. On dual minimum cost flow algorithms // Math. Methods. Oper. Res. – 2002. – № 56.
– P. 101–126.
6. Orlin J.B. A faster strongly polynomial minimum cost flow algorithm // Oper. Res. – 1993. –
№ 41. – P. 338–350.
7. Cook W.J., Cunningam W.H., etc. Combinatorial optimization. – New-York: Jonh Wiley-
Sons.INC, 1998. – 338 p.
8. Шарифов Ф.А. Об эффективности алгоритмов решения сетевых задач на древовидных
структурах // Кибернетика и системный анализ. – 2003. – № 3. – С. 179–184.
Получено 01.09.2003
|
| id | nasplib_isofts_kiev_ua-123456789-84868 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | XXXX-0013 |
| language | Russian |
| last_indexed | 2025-12-07T15:31:06Z |
| publishDate | 2003 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Шарифов, Ф.А. 2015-07-16T15:18:55Z 2015-07-16T15:18:55Z 2003 Задача нахождения непересекающихся и несовпадающих циклов на сети / Ф.А. Шарифов // Теорія оптимальних рішень: Зб. наук. пр. — 2003. — № 2. — С. 155-161. — Бібліогр.: 8 назв. — рос. XXXX-0013 https://nasplib.isofts.kiev.ua/handle/123456789/84868 519.8 Рассмотрена задача нахождения непересекающихся и несовподающих циклов на сети с двумя весами дуг. Показано, что она может быть сформулирована как задача нахождения непересекаюшихся совершенных паросочетаний на двудольном графе. Когда веса дуг равные, данная задача эквивалентна задаче нахождения потока минимальной стоимости на сети представленой двудольным графом. Для последней задачи разработаны ряд строгих полиномиальных алгоритмов. В общем случае рассмотренная задача не имеет целочисленное решение. В работе приводятся основные этапы полиномиального алгоритма для решения задачи в общем случае. Разглянуто задачу знаходження циклів на мережі, що не перетинаються і не співпадають. Показано, що ця задача еквівалентна задачі знаходження двох паросполучень на двудольному графі. В окремих випадках розглянута задача є задачею знаходження потоку мінімальної вартості. Наведено, що ці властивості є основними для разробки поліноміального алгоритму вирішення задачі. We study a minimum cost node and arc-disjoint cycles problem on a directed graph. It is shown that the problem is equivalent to the minimum cost disjoint matchings problem on complete bipartite graph. In particular case, for which weights of arcs are special, then the considered problem is reduced to minimum cost flow problem. Some interesting properties of LP-relaxation problem are proved and it is noted that namely these properties are on bases for polynomial algorithm to solve the problem. ru Інститут кібернетики ім. В.М. Глушкова НАН України Теорія оптимальних рішень Задача нахождения непересекающихся и несовпадающих циклов на сети Задача знаходження не перетинаючих і не співпадаючих циклів на мережі Minimum cost node and arc disjoint cycles problem Article published earlier |
| spellingShingle | Задача нахождения непересекающихся и несовпадающих циклов на сети Шарифов, Ф.А. |
| title | Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_alt | Задача знаходження не перетинаючих і не співпадаючих циклів на мережі Minimum cost node and arc disjoint cycles problem |
| title_full | Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_fullStr | Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_full_unstemmed | Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_short | Задача нахождения непересекающихся и несовпадающих циклов на сети |
| title_sort | задача нахождения непересекающихся и несовпадающих циклов на сети |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/84868 |
| work_keys_str_mv | AT šarifovfa zadačanahoždeniâneperesekaûŝihsâinesovpadaûŝihciklovnaseti AT šarifovfa zadačaznahodžennâneperetinaûčihínespívpadaûčihciklívnamereží AT šarifovfa minimumcostnodeandarcdisjointcyclesproblem |