Loading AI tools
Из Википедии, свободной энциклопедии
Максимальный разрез графа — это разрез, размер которого не меньше размера любого другого разреза. Задача определения максимального разреза для графа известна как задача о максимальном разрезе.
Задачу можно сформулировать следующим образом. Следует найти подмножество вершин S, такое, что число рёбер между S и его дополнением было бы настолько велико, насколько это возможно.
Существует расширенная версия, задача о взвешенном максимальном разрезе. В этой версии каждому ребру приписано вещественное число, его вес, и целью является максимизация не числа рёбер, а общего веса рёбер между S и его дополнением. Задача о взвешенном максимальном разрезе часто, но не всегда, ограничивается неотрицательными весами, поскольку отрицательные веса могут изменить природу задачи.
Следующая задача разрешимости, связанная с максимальным разрезом, широко изучалась в теоретической информатике:
Известно, что эта задача NP-полная. NP-полноту задачи можно показать, например, приведением от задачи максимальной 2-выполнимости[англ.] (задача максимальной выполнимости[англ.] с ограничениями)[1]. Взвешенная версия задачи разрешимости входит в 21 NP-полную задачу Карпа[2]. Карп показал NP-полноту путём приведения от задачи разбиения[англ.].
Канонический оптимизационный вариант вышеупомянутой задачи разрешимости известен как «задача о максимальном разрезе» и определяется следующим образом:
Так как задача о максимальном разрезе является NP-трудной, нет известных алгоритмов полиномиального времени для задачи о максимальном разрезе для общих графов.
Для планарных графов, однако, задача о максимальном разрезе двойственна задаче китайского почтальона (задаче поиска кратчайшего обхода с обходом всех рёбер по меньшей мере один раз), в том смысле, что рёбра, не принадлежащие максимальному разрезу графа G, двойственны рёбрам, которые проходятся многократно в оптимальном обходе двойственного графа для графа G. Оптимальный обход образует самопересекающуюся кривую, которая разбивает плоскость на два подмножества, подмножество точек, для которых порядок относительно кривой чётен, и подмножества точек, порядок которых нечётен. Эти два подмножества образуют разрез, в который входят все рёбра, двойственные рёбрам, которые появляются нечётное число раз в обходе. Задача о китайском почтальоне может быть решена за полиномиальное время, и эта двойственность позволяет задачу максимального разреза решать для планарных графов за полиномиальное время[3]. Известно, однако, что задача максимальной бисекции NP-трудна[4].
Задача о максимальном разрезе является APX-сложной (Пападимитроу и Яннакакис доказали MaxSNP-полноту данной задачи[5]), что означает, что не существует аппроксимационной схемы полиномиального времени (PTAS) как угодно близкой к оптимальному решению, если только не P = NP. Таким образом, любой аппроксимационный алгоритм полиномиального времени даёт аппроксимационный коэффициент, строго меньший единицы.
Существует простой вероятностный 0,5- аппроксимационный алгоритм — для любой вершины бросаем монету с целью решить, к какой части разреза отнести данную вершину[6][7]. Ожидается, что половина рёбер являются разрезающими. Этот алгоритм может быть дерандомизирован с помощью метода условных вероятностей. Таким образом, существует простой детерминированный полиномиального времени алгоритм с 0,5-аппроксимацией[8][9]. Один такой алгоритм начинает с произвольного разбиения вершин заданного графа и передвигает одну вершину за один шаг из одной части разреза в другую, улучшая решение на каждом шаге до тех пор, пока улучшение возможно. Число итераций алгоритма не превосходит , поскольку алгоритм улучшает разрез по меньшей мере на одно ребро. Когда алгоритм прекращает работу, по меньшей мере половина рёбер, инцидентных любой вершине, принадлежат разрезу, в противном случае перенос вершины улучшил бы разрез (увеличил бы размер разреза). Таким образом, разрез включает по меньшей мере рёбер.
Полиномиального времени аппроксимационный алгоритм для задачи о максимальном разрезе с лучшим известным аппроксимационным коэффициентом — это метод Геманса и Вильямсона, использующий полуопределённое программирование и вероятностное округление. Метод даёт аппроксимационный коэффициент , где [10][11]. Если гипотеза уникальной игры[англ.] верна, это лучший возможный аппроксимационный коэффициент для максимального разреза[12]. Если не принимать такие недоказанные допущения, было доказано, что NP-трудно аппроксимировать значение максимального разреза с коэффициентом, лучшим [13][14].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
