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

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

Задача 3. Заранее заданное разбиение

Дано: неориентированный граф G = (V, E) с неотрицательными весами ребер и целые числа k1, ... , kr, такие, что Pi ki = j Vj.

Требуется: найти разбиение V = V 1 • • • U Vr графа G с j V i j = ki для всех i, такое, что общий вес ребер, конечные точки которых принадлежат к разным множествам Vi, насколько возможно мал.