5. Общая задача построения остовного подграфа с предписанными степенями

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

Исходя из графа построим граф Если требуется, чтобы было степенью вершины в графе то в будут сопоставлены ершине вершин Каждому ребру графа будут соответствовать в две дополнительные вершины ребра все со стоимостями ребра со стоимостями и ребро со стоимостью 0.

Теперь совершенно очевидно, что общая задача для графа соответствует задаче о назначениях для графа Если ребро лежит в паросочетании то это означает, что ребро не принадлежит графу Если два ребра лежат в паросочетании графа то это означает, что ребро принадлежит Существует взаимно однозначное соответствие между паросочетаниями в и остовными подграфами с допустимыми степенями в графе Но так как число вершин в намного больше вышеприведенное преобразование графа с вычислительной точки зрения неэффективно. На самом деле не обязательно строить явно граф возможно [13], так модифицировать алгоритм из разд. 3.1.1, что он будет оперировать непосредственно с первоначальным графом но все будет относиться к графу