Минимальная бисекция: различия между версиями

Вышеприведенное, довольно простое определение минимальной бисекции можно расширить несколькими способами. В частности, можно задать только верхнюю границу размера каждой стороны разреза. Для <math>0 < \beta < 1 \;</math> разрез <math>(S, \bar{S}) \;</math> называется <math>\beta</math>-сбалансированным, если <math>max \{ |S|, |\bar{S}| \} \le \beta n \;</math>. Отметим, что из последнего требования следует <math>min \{ |S|, |\bar{S}| \} \ge (1 - \beta) n \;</math>. В этих терминах бисекция является 1/2-сбалансированным разрезом.

'''Задача 2 (<math>\beta</math>-сбалансированный разрез)'''

Требуется: найти <math>\beta</math>-сбалансированный разрез <math>(S, \bar{S}) \;</math> графа G с <math>max \{ |S|, |\bar{S}| \} \le \beta n \;</math>, такой, что его стоимость насколько возможно мала.

Специальный случай <math>\beta = 2/3 \;</math> часто называется задачей о реберном сепараторе (EDGE-SEPARATOR).

В общем случае размер обеих сторон может изначально задаваться произвольным образом (они не обязательно должны быть равными); в этом случае входные условия содержат число k, а задача заключается в нахождении разреза <math>(S, \bar{S}) \;</math>, такого, что |S| = k. Можно также разделить граф на более чем два фрагмента равного размера – в этом случае входные данные содержат число <math>r \ge 2 \;</math> – или разделить граф на r фрагментов размерами <math>k_1,... , k_r \;</math>, где числа <math>k_i \;</math> заранее заданы во входных данных; и в том и в другом случае задача заключается в минимизации количества ребер между различными фрагментами.