Русская Википедия:Максимальный разрез графа

Материал из Онлайн справочника
Перейти к навигацииПерейти к поиску

Файл:Max-cut.svg
Максимальный разрез.

Максимальный разрез графа — это разрез, размер которого не меньше размера любого другого разреза. Задача определения максимального разреза для графа известна как задача о максимальном разрезе.

Задачу можно сформулировать следующим образом. Следует найти подмножество вершин S, такое, что число рёбер между S и его дополнением было бы настолько велико, насколько это возможно.

Существует расширенная версия, задача о взвешенном максимальном разрезе. В этой версии каждому ребру приписано вещественное число, его вес, и целью является максимизация не числа рёбер, а общего веса рёбер между S и его дополнением. Задача о взвешенном максимальном разрезе часто, но не всегда, ограничивается неотрицательными весами, поскольку отрицательные веса могут изменить природу задачи.

Вычислительная сложность

Следующая задача разрешимости, связанная с максимальным разрезом, широко изучалась в теоретической информатике:

Задан граф G и целое число k, определить, имеется ли разрез в G размером, не меньшим k.

Известно, что эта задача NP-полная. NP-полноту задачи можно показать, например, приведением от задачи Шаблон:Не переведено 5 (Шаблон:Не переведено 5 с ограничениями)Шаблон:Sfn. Взвешенная версия задачи разрешимости входит в 21 NP-полную задачу КарпаШаблон:Sfn. Карп показал NP-полноту путём приведения от Шаблон:Не переведено 5.

Канонический оптимизационный вариант вышеупомянутой задачи разрешимости известен как «задача о максимальном разрезе» и определяется следующим образом:

Пусть задан граф G, нужно найти максимальный разрез.

Алгоритмы полиномиального времени

Так как задача о максимальном разрезе является NP-трудной, нет алгоритмов полиномиального времени для задачи о максимальном разрезе для общих графов.

Для планарных графов, однако, задача о максимальном разрезе двойственна задаче китайского почтальона (задаче поиска кратчайшего обхода с обходом всех рёбер по меньшей мере один раз), в том смысле, что рёбра, не принадлежащие максимальному разрезу графа G, двойственны рёбрам, которые проходятся многократно в оптимальном обходе двойственного графа для графа G. Оптимальный обход образует самопересекающуюся кривую, которая разбивает плоскость на два подмножества, подмножество точек, для которых порядок относительно кривой чётен, и подмножества точек, порядок которых нечётен. Эти два подмножества образуют разрез, в который входят все рёбра, двойственные рёбрам, которые появляются нечётное число раз в обходе. Задача о китайском почтальоне может быть решена за полиномиальное время, и эта двойственность позволяет задачу максимального разреза решать для планарных графов за полиномиальное времяШаблон:Sfn. Известно, однако, что задача максимальной бисекции NP-труднаШаблон:Sfn.

Аппроксимационные алгоритмы

Задача о максимальном разрезе является APX-сложной (Пападимитроу и Яннакакис доказали MaxSNP-полноту данной задачиШаблон:Sfn), что означает, что не существует аппроксимационной схемы полиномиального времени (PTAS) как угодно близкой к оптимальному решению, если только не P = NP. Таким образом, любой аппроксимационный алгоритм полиномиального времени даёт аппроксимационный коэффициент, строго меньший единицы.

Существует простой вероятностный 0,5-аппроксимационный алгоритм — для любой вершины бросаем монету с целью решить, к какой части разреза отнести данную вершинуШаблон:SfnШаблон:Sfn. Ожидается, что половина рёбер являются разрезающими. Этот алгоритм может быть дерандомизирован с помощью метода условных вероятностей. Таким образом, существует простой детерминированный полиномиального времени алгоритм с 0,5-аппроксимациейШаблон:SfnШаблон:Sfn. Один такой алгоритм начинает с произвольного разбиения вершин заданного графа <math>G = (V, E)</math> и передвигает одну вершину за один шаг из одной части разреза в другую, улучшая решение на каждом шаге до тех пор, пока улучшение возможно. Число итераций алгоритма не превосходит <math>|E|</math>, поскольку алгоритм улучшает разрез по меньшей мере на одно ребро. Когда алгоритм прекращает работу, по меньшей мере половина рёбер, инцидентных любой вершине, принадлежат разрезу, в противном случае перенос вершины улучшил бы разрез (увеличил бы размер разреза). Таким образом, разрез включает по меньшей мере <math>|E|/2</math> рёбер.

Полиномиального времени аппроксимационный алгоритм для задачи о максимальном разрезе с лучшим известным аппроксимационным коэффициентом — это метод Геманса и Вильямсона, использующий полуопределённое программирование и вероятностное округление. Метод даёт аппроксимационный коэффициент <math>\alpha \approx 0{,}878</math>, где <math>\alpha = \tfrac{2}{\pi} \min_{0 \le \theta \le \pi} \tfrac{\theta}{1 - \cos \theta}</math>Шаблон:SfnШаблон:Sfn. Если Шаблон:Не переведено 5 верна, это лучший возможный аппроксимационный коэффициент для максимального разрезаШаблон:Sfn. Если не принимать такие недоказанные допущения, было доказано, что NP-трудно аппроксимировать значение максимального разреза с коэффициентом, лучшим <math>\tfrac{16}{17} \approx 0{,}941</math>Шаблон:SfnШаблон:Sfn.

См. также

Примечания

Шаблон:Примечания

Литература

Задача о максимальном разрезе (оптимизационная версия) — задача ND14 в Приложении B (стр. 399).
Задача о максимальном разрезе (задача разрешимости) — задача ND16 в Приложении A2.2.
Максимальный двудольный подграф (задача разрешимости) — задача GT25 в Приложении A1.2.

Литература для дополнительного чтения

Ссылки

Шаблон:Rq

Партнерские ресурсы
Криптовалюты
Магазины
Хостинг
Разное

Источник — http://wikihandbk.com/ruwiki/index.php?title=Русская_Википедия:Максимальный_разрез_графа&oldid=10318566