Участник:Kirillskor/MAX-CUT-NPC — Решение Скорнякова Кирилл

Материал из DISCOPAL
< Участник:Kirillskor
Версия от 11:00, 14 мая 2015; Kirillskor (обсуждение | вклад) (Новая страница: «Category:На проверку Сведем эту задачу к задаче нахождения MAX-CUT. Сначала найдем бинпоиском…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Сведем эту задачу к задаче нахождения MAX-CUT. Сначала найдем бинпоиском величину максимального разреза(ограничение сверху - сумма пропускных способностей всех ребер). Далее буде. Удалять ребра, начиная с ребер самого большого веса. После каждого удаления буде запускать нашу программу с найденным значением MAX-CUT. Если оно изменилось, то удаленное ребро входило в разрез. Указанные операции выполняются за полином. Значит задача из условия лежит в NPC, т.к. она очевидно в NP.