Взвешенное совершенное паросочетание с ограничениями на суммарный вес его частей

Рассматривается NP-трудная в сильном смысле задача поиска в сбалансированном полном двудольном графе с весами на рёбрах и разбиением одной его доли на несколько непустых непересекающихся множеств такого совершенного паросочетания, что наибольший суммарный вес рёбер паросочетания, покрывающих все вершины одного множества разбиения, минимален. Предложена характеризация решений специального случая этой задачи, в котором, во-первых, веса рёбер графа принимают значения из множества $\{0, 1, \Delta\},$ где $\Delta$ — целое число, большее количества рёбер единичного веса, и, во-вторых, есть совершенное паросочетание, состоящее исключительно из рёбер нулевого и единичного весов. Кроме этого, выделены полиномиально разрешимый и сильно NP-трудный случаи рассматриваемой задачи. Установлена эквивалентность специального случая задачи с фиксированным числом множеств, на которые разбивается доля графа, задаче поиска совершенного паросочетания заданного веса в сбалансированном двудольном графе с весами на рёбрах. Ил. 5, библиогр. 29.