Главная > Теория графов. Алгоритмический подход
НАПИШУ ВСЁ ЧТО ЗАДАЛИ
СЕКРЕТНЫЙ БОТ В ТЕЛЕГЕ
<< Предыдущий параграф Следующий параграф >>
Пред.
След.
Макеты страниц

Распознанный текст, спецсимволы и формулы могут содержать ошибки, поэтому с корректным вариантом рекомендуем ознакомиться на отсканированных изображениях учебника выше

Также, советуем воспользоваться поиском по сайту, мы уверены, что вы сможете найти больше информации по нужной Вам тематике

ДЛЯ СТУДЕНТОВ И ШКОЛЬНИКОВ ЕСТЬ
ZADANIA.TO

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

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

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

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

1
Оглавление
email@scask.ru