Максимальный разрез графа — это разрез, размер которого не меньше размера любого другого разреза данного графа. Задача определения максимального разреза известна как задача о максимальном разрезе.
Эквивалентно, её можно сформулировать как разбиение множества вершин графа на две непересекающиеся части так, чтобы число рёбер, соединяющих эти части, было максимально возможным.
Существует также обобщённая версия задачи — задача о взвешенном максимальном разрезе. В этом случае каждому ребру назначается вещественный вес, и целью становится максимизация суммарного веса рёбер между двумя частями разреза. Взвешенные разрезы не обязательно ограничены неотрицательными весами, поэтому отрицательные значения могут изменять структуру оптимального решения.
Вычислительная сложность Следующая задача разрешимости, связанная с максимальным разрезом, широко изучалась в теоретической информатике.
Пусть задан граф G и целое число k. Требуется определить, имеется ли в G разрез размера не меньшего, чем k.
Известно, что эта задача является NP-полной. NP-полноту можно показать с помощью сведения от задачи а также от ряда других классических задач разбиения. Взвешенная версия задачи входит в 21 NP-полную задачу Карпа.
Каноническая оптимизационная формулировка задачи известна как «задача о максимальном разрезе» и определяется следующим образом:
Пусть задан граф G. Необходимо найти максимальный разрез его множества вершин.
Алгоритмы полиномиального времени Так как задача о максимальном разрезе является NP-трудной, нет известных алгоритмов полиномиального времени для задачи о максимальном разрезе для общих графов.
Для планарных графов, однако, задача о максимальном разрезе двойственна задаче китайского почтальона (задаче поиска кратчайшего обхода с обходом всех рёбер по меньшей мере один раз), в том смысле, что рёбра, не принадлежащие максимальному разрезу графа G, двойственны рёбрам, которые проходятся многократно в оптимальном обходе двойственного графа для графа G. Оптимальный обход образует самопересекающуюся кривую, которая разбивает плоскость на два подмножества, подмножество точек, для которых порядок относительно кривой чётен, и подмножества точек, порядок которых нечётен. Эти два подмножества образуют разрез, в который входят все рёбра, двойственные рёбрам, которые появляются нечётное число раз в обходе. Задача о китайском почтальоне может быть решена за полиномиальное время, и эта двойственность позволяет задачу максимального разреза решать для планарных графов за полиномиальное время. Известно, однако, что задача максимальной бисекции NP-трудна.
Аппроксимационные алгоритмы Задача о максимальном разрезе является APX-сложной (Пападимитроу и Яннакакис доказали MaxSNP-полноту данной задачи), что означает, что не существует аппроксимационной схемы полиномиального времени (PTAS) как угодно близкой к оптимальному решению, если только не P = NP. Таким образом, любой аппроксимационный алгоритм полиномиального времени даёт аппроксимационный коэффициент, строго меньший единицы.
Существует простой вероятностный 0,5- аппроксимационный алгоритм — для любой вершины бросаем монету с целью решить, к какой части разреза отнести данную вершину. Ожидается, что половина рёбер являются разрезающими. Этот алгоритм может быть дерандомизирован с помощью метода условных вероятностей. Таким образом, существует простой детерминированный полиномиального времени алгоритм с 0,5-аппроксимацией. Один такой алгоритм начинает с произвольного разбиения вершин заданного графа и передвигает одну вершину за один шаг из одной части разреза в другую, улучшая решение на каждом шаге до тех пор, пока улучшение возможно. Число итераций алгоритма не превосходит , поскольку алгоритм улучшает разрез по меньшей мере на одно ребро. Когда алгоритм прекращает работу, по меньшей мере половина рёбер, инцидентных любой вершине, принадлежат разрезу, в противном случае перенос вершины улучшил бы разрез (увеличил бы размер разреза). Таким образом, разрез включает по меньшей мере рёбер.
Полиномиального времени аппроксимационный алгоритм для задачи о максимальном разрезе с лучшим известным аппроксимационным коэффициентом — это метод Геманса и Вильямсона, использующий полуопределённое программирование и вероятностное округление. Метод даёт аппроксимационный коэффициент , где . Если верна, это лучший возможный аппроксимационный коэффициент для максимального разреза. Если не принимать такие недоказанные допущения, было доказано, что NP-трудно аппроксимировать значение максимального разреза с коэффициентом, лучшим .
См. также Наименьший разрез Наименьший k-разрез
Примечания
Литература
Задача о максимальном разрезе (оптимизационная версия) — задача ND14 в Приложении B (стр. 399).
Задача о максимальном разрезе (задача разрешимости) — задача ND16 в Приложении A2.2. Максимальный двудольный подграф (задача разрешимости) — задача GT25 в Приложении A1.2.
.
Литература для дополнительного чтения
Ссылки Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger (2000), "Maximum Cut", in "A compendium of NP optimization problems". Andrea Casini, Nicola Rebagliati (2012), "A Python library for solving Max Cut"
Категория:Объекты теории графов Категория:Комбинаторная оптимизация Категория:NP-полные задачи Категория:Вычислительные задачи теории графов