Задача нахождения непересекающихся и несовпадающих циклов на сети

Abstract

Рассмотрена задача нахождения непересекающихся и несовподающих циклов на сети с двумя весами дуг. Показано, что она может быть сформулирована как задача нахождения непересекаюшихся совершенных паросочетаний на двудольном графе. Когда веса дуг равные, данная задача эквивалентна задаче нахождения потока минимальной стоимости на сети представленой двудольным графом. Для последней задачи разработаны ряд строгих полиномиальных алгоритмов. В общем случае рассмотренная задача не имеет целочисленное решение. В работе приводятся основные этапы полиномиального алгоритма для решения задачи в общем случае.

Разглянуто задачу знаходження циклів на мережі, що не перетинаються і не співпадають. Показано, що ця задача еквівалентна задачі знаходження двох паросполучень на двудольному графі. В окремих випадках розглянута задача є задачею знаходження потоку мінімальної вартості. Наведено, що ці властивості є основними для разробки поліноміального алгоритму вирішення задачі.

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.