Есть хороший алгоритм для этой проблемы графа?

Question

Существует неориентированный граф с весами по ребрам (весовые значения неотрицательные целые числа, а их сумма не велика, большинство равно 0).Мне нужно разделить его на некоторое количество подграфов (скажем, граф из 20 узлов в 4 подграфа по 5 узлов в каждом) таким образом, чтобы свести к минимуму сумму весов ребер между различными подграфами.проблема минимального среза, но не совсем близко.

В альтернативной формулировке - есть группа сегментов, все элементы принадлежат ровно двум сегментам, и мне нужно разделить сегменты на группы блоков таким образом, чтобы минимизироватьпредметы в более чем одной группе ведер.(отображение узлов на ведра, отображение веса ребер на дублирование количества элементов)

Answer 1

Это минимальная проблема k-cut, и она сложная для NP. Вот жадная эвристика, которая гарантирует вам приближение 2-1 / k:

Хотя на графике меньше k компонентов: 1) Найти мин-разрез в каждом компоненте 2) Разделить компонент с минимальным весом минимальной резки.

Проблема изучается в этой статье: http://www.cc.gatech.edu/~vazirani/k-cut.ps