Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше
Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике
5. Общая задача построения остовного подграфа с предписанными степенями
Для заданного графа дугам которого приписаны гоимости, общая задача была сформулирована во введении как адача нахождения остовного подграфа по отношению к которому степени вершин равны заданным целым числам и сумма стоимостей ребер в максимальна (или минимальна). Во ввеении отмечалось, что ЗМП является частным случаем этой общей гдачи. Теперь мы покажем, что общая задача сама может быть ешена как ЗМП с использованием алгоритма из разд. 3.1.1.
Исходя из графа построим граф Если требуется, чтобы было степенью вершины в графе то в будут сопоставлены ершине вершин Каждому ребру графа будут соответствовать в две дополнительные вершины ребра все со стоимостями ребра со стоимостями и ребро со стоимостью 0.
Теперь совершенно очевидно, что общая задача для графа соответствует задаче о назначениях для графа Если ребро лежит в паросочетании то это означает, что ребро не принадлежит графу Если два ребра лежат в паросочетании графа то это означает, что ребро принадлежит Существует взаимно однозначное соответствие между паросочетаниями в и остовными подграфами с допустимыми степенями в графе Но так как число вершин в намного больше вышеприведенное преобразование графа с вычислительной точки зрения неэффективно. На самом деле не обязательно строить явно граф возможно [13], так модифицировать алгоритм из разд. 3.1.1, что он будет оперировать непосредственно с первоначальным графом но все будет относиться к графу