Аннотация. Рассмотрена задача минимизации в графе H = (V, U) суммы весов ребер подмножества U' ⊂ U, образующих совокупность непересекающихся в вершинах v ∈ V простых циклов и покрывающих V. Рассматриваемая задача (задача 2-f ) полиномиально разрешима алгоритмами, которые характеризуются техническими трудностями, препятствующими ускорению процесса вычислений. Решение задачи 2-f находится сведением ее к более простому двудольному случаю. Результат представлен совершенным паросочетанием двудольного графа, соответствующим решению задачи о назначениях, в цикловом разложении которой каждый контур содержит не менее трех дуг.

Ключевые слова: 2-фактор, задача о назначениях, паросочетание, двудольный граф, увеличивающий путь.