4551
правка
Минимальная бисекция: различия между версиями
Перейти к навигации
Перейти к поиску
→Разрезы и бисекции
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 28: | Строка 28: | ||
Это определение имеет одно существенное отличие от определения классической задачи о минимальном разрезе (см, например, [ ] и ссылки в этой работе): в нем имеется ограничение на обе стороны разреза. В результате задача о минимальной бисекции (MINIMUM-BISECTION) является NP-полной [ ], тогда как задача о минимальном разрезе (MINIMUM-CUT) может быть решена за полиномиальное время. | Это определение имеет одно существенное отличие от определения классической задачи о минимальном разрезе (см, например, [ ] и ссылки в этой работе): в нем имеется ограничение на обе стороны разреза. В результате задача о минимальной бисекции (MINIMUM-BISECTION) является NP-полной [ ], тогда как задача о минимальном разрезе (MINIMUM-CUT) может быть решена за полиномиальное время. | ||
Сбалансированные разрезы и реберные сепараторы | |||
Вышеприведенное, довольно простое определение минимальной бисекции можно расширить несколькими способами. В частности, можно задать только верхнюю границу размера каждой стороны разреза. Для 0 < (3 < 1 разрез (S,; S) называется ^-сбалансированным, если maxfjSj; \S\} < fin. Отметим, что из последнего требования следует minfjSj; \S\} > (1 — f$)n. В этих терминах бисекция является 1/2-сбалансированным разрезом. | |||
Задача 2 (/!-сбалансированный разрез) | |||
Дано: неориентированный граф G с неотрицательными весами ребер. | |||
Требуется: найти ft-сбалансированный разрез (S, S) графа G с maxfjSj; \S\} j f$ n, такой, что его стоимость насколько возможно мала. | |||
Специальный случай f$ = 2/3 часто называется задачей о реберном сепараторе (EDGE-SEPARATOR). | |||