Быстрый алгоритм нахождения 2-фактора минимального веса

Маций, О. Б.; Морозов, А. В.; Панишев, А. В.

Рассмотрена задача минимизации в графе H = (V, U) суммы весов ребер подмножества <$E U prime~symbol <172>~U>, образующих совокупность непересекающихся в вершинах <$E v~symbol <174>~V> простых циклов и покрывающих V. Рассматриваемая задача (задача 2-f) полиномиально разрешима алгоритмами, которые характеризуются техническими трудностями, препятствующими ускорению процесса вычислений. Решение задачи 2-f находится сведением ее к более простому двудольному случаю. Результат представлен совершенным паросочетанием двудольного графа, соответствующим решению задачи о назначениях, в цикловом разложении которой каждый контур содержит не менее трех дуг.


	Наукова періодика України		Кібернетика та системний аналіз