4817
правок
Максимальный разрез: различия между версиями
Материал из WEGA
м
→Постановка задачи
Irina (обсуждение | вклад) м (→Применение) |
Irina (обсуждение | вклад) |
||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Пусть имеется неориентированный граф G = (V, E). Задача о максимальном разрезе (MAX-CUT) заключается в нахождении такого биразбиения вершин, при котором суммарный вес ребер, пересекающих это разбиение, оказывается максимальным. Если веса ребер неотрицательны, то эта задача эквивалентна нахождению подмножества ребер с максимальным весом, которое образует двудольный подграф, то есть задаче о максимальном двудольном подграфе. Все результаты, обсуждаемые далее в статье, предполагают неотрицательные веса ребер. MAX-CUT входит в число изначальных NP-полных задач Карпа [19] [https://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%9A%D0%B0%D1%80%D0%BF%D0%B0]. На самом деле она является NP-трудной для аппроксимации с точностью до коэффициента, лучшего, чем 16/17 [16, 33]. | Пусть имеется неориентированный граф G = (V, E). Задача о максимальном разрезе (MAX-CUT) заключается в нахождении такого биразбиения вершин, при котором суммарный вес ребер, пересекающих это разбиение, оказывается максимальным. Если веса ребер неотрицательны, то эта задача эквивалентна нахождению подмножества ребер с максимальным весом, которое образует [[двудольный граф|двудольный подграф]], то есть задаче о максимальном двудольном подграфе. Все результаты, обсуждаемые далее в статье, предполагают неотрицательные веса ребер. MAX-CUT входит в число изначальных NP-полных задач Карпа [19] [https://ru.wikipedia.org/wiki/%D0%A1%D0%BF%D0%B8%D1%81%D0%BE%D0%BA_%D0%9A%D0%B0%D1%80%D0%BF%D0%B0]. На самом деле она является NP-трудной для аппроксимации с точностью до коэффициента, лучшего, чем 16/17 [16, 33]. | ||
