4446
правок
Минимальная бисекция: различия между версиями
Перейти к навигации
Перейти к поиску
→Разрезы и бисекции
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 15: | Строка 15: | ||
Пусть G = (V, E) – неориентированный граф, имеющий n = |V| вершин. Для простоты предположим, что n четно Для подмножества S вершин положим <math>\bar{S} = V \backslash S \;</math>. [[Разрез]] <math>(\bar{S}, S) \;</math>, также называемый [[сечение|сечением]], определяется как множество всех ребер, имеющих одну конечную точку в <math>S \;</math>, а другую – в <math>\bar{S} \;</math>. Говорится, что эти ребра пересекают разрез, а множества <math>S \;</math> и <math>\bar{S} \;</math> называются сторонами разреза. | Пусть G = (V, E) – неориентированный граф, имеющий n = |V| вершин. Для простоты предположим, что n четно Для подмножества S вершин положим <math>\bar{S} = V \backslash S \;</math>. [[Разрез]] <math>(\bar{S}, S) \;</math>, также называемый [[сечение|сечением]], определяется как множество всех ребер, имеющих одну конечную точку в <math>S \;</math>, а другую – в <math>\bar{S} \;</math>. Говорится, что эти ребра пересекают разрез, а множества <math>S \;</math> и <math>\bar{S} \;</math> называются сторонами разреза. | ||
Будем предполагать, что ребра графа G имеют неотрицательные веса. (В невзвешенной версии будем предполагать веса всех ребер единичными). Стоимость разреза (S, | Будем предполагать, что ребра графа G имеют неотрицательные веса. (В невзвешенной версии будем предполагать веса всех ребер единичными). [[Стоимость]] разреза <math>(S, \bar{S}) \;</math> определяется как сумма весов всех ребер, пересекающих разрез. | ||
Разрез (S, S’) называется бисекцией графа G, если обе его стороны имеют одинаковую мощность, а именно – |S| = | | Разрез (S, S’) называется [[бисекция|бисекцией]] графа G, если обе его стороны имеют одинаковую мощность, а именно – <math>|S| = |\bar{S}| = n/2 \;</math>. Обозначим за b(G) минимальную стоимость бисекции G. | ||
Задача 1 (Минимальная бисекция) | '''Задача 1 (Минимальная бисекция)''' | ||
Дано: неориентированный граф G с неотрицательными весами ребер. | Дано: неориентированный граф G с неотрицательными весами ребер. | ||
Требуется: найти бисекцию (S, S) графа G с минимальной стоимостью. | Требуется: найти бисекцию <math>(S, \bar{S}) \;</math> графа G с минимальной стоимостью. | ||
Это определение имеет одно существенное отличие от определения классической задачи о минимальном разрезе (см, например, [ ] и ссылки в этой работе): в нем имеется ограничение на обе стороны разреза. В результате задача о минимальной бисекции (MINIMUM-BISECTION) является NP-полной [ ], тогда как задача о минимальном разрезе (MINIMUM-CUT) может быть решена за полиномиальное время. | Это определение имеет одно существенное отличие от определения классической задачи о минимальном разрезе (см, например, [10] и ссылки в этой работе): в нем имеется ограничение на обе стороны разреза. В результате задача о минимальной бисекции (MINIMUM-BISECTION) является NP-полной [9], тогда как задача о минимальном разрезе (MINIMUM-CUT) может быть решена за полиномиальное время. | ||
Сбалансированные разрезы и реберные сепараторы | == Сбалансированные разрезы и реберные сепараторы == | ||
Вышеприведенное, довольно простое определение минимальной бисекции можно расширить несколькими способами. В частности, можно задать только верхнюю границу размера каждой стороны разреза. Для 0 < | Вышеприведенное, довольно простое определение минимальной бисекции можно расширить несколькими способами. В частности, можно задать только верхнюю границу размера каждой стороны разреза. Для <math>0 < \beta < 1 \;</math> разрез <math>(S, \bar{S}) \;</math> называется <math>\beta</math>-сбалансированным, если <math>max \{ |S|, |\bar{S}| \} \le \beta n \;</math>. Отметим, что из последнего требования следует minfjSj; \S\} > (1 — f$)n. В этих терминах бисекция является 1/2-сбалансированным разрезом. | ||