Разделите граф на непересекающиеся множества одинакового размера с минимальным разрезом
Существует ли какой-либо алгоритм или код, который делит узлы графа на два или более непересекающихся множества, которые удовлетворяют следующим условиям: во-первых, удаляются только ребра. во-вторых, ребра взвешены, и те, которые будут удалены, должны иметь минимальный вес (алгоритм минимального разреза). в-третьих, желаемые непересекающиеся множества имеют одинаковый размер как можно дольше.
1 ответ
Похоже, вы пытаетесь решить проблему минимального деления, в которой для заданного графа G вы хотели бы разбить V[G] на два непересекающихся подмножества A и B одинакового размера, чтобы сумма весов ребер между A и B сведено к минимуму. К сожалению, проблема мин-бисекции, как известно, NP-трудна. Однако алгоритм Кернигана – Линя является очень простым O(n^2*logn) эвристическим алгоритмом для задачи. Хотя теоретически очень мало известно об алгоритме (у нас нет проверенной границы его производительности относительно оптимального решения), алгоритм показан достаточно эффективным в экспериментах.