Теория графов: разделение графа

Частный случай, когда x = n - x, называется проблемой минимального деления пополам и является NP-трудным. Это также делает вашу проблему NP-трудной. В статье Википедии о разбиении графа описано несколько эвристик, включая локальный поиск (например, начать с случайный разрез и многократное переключение пар вершин, что уменьшает размер разреза) и спектральные методы (например, вычисление и пороговое значение второго собственного вектора). Если n мало, целочисленное программирование также возможно.

Возможно, поиск в глубину по узлам. Мы назначаем узлы по одному и подсчитываем количество разрезов на данный момент. Если это число превышает число лучшего решения, то мы прерываем это и возвращаемся.

1. Учитывая полный набор узлов S, пусть P и P' будут множествами узлов, изначально пустыми, а K числом отрезанных ребер, изначально равным 0.
2. Пусть S*, K* — наилучшее известное решение и его количество ребер, где K* изначально равно бесконечности.
3. Выберите узел N для начала и назначьте его S.
4. For each unassigned node M:
   1. Assign M to S', and add the number of edges from M to nodes in S to K.
   2. Если K > K*, то никакое решение, основанное на этом, не будет лучше лучшего, поэтому присвойте M значению S.
   3. Если |S| > X, то множество стало слишком большим; отступать.
   4. В противном случае рекурсия от 4.
5. Если все узлы назначены и K ‹ K*, то пусть S* = S и K* = K.

Я представлял себе это как алгоритм типа Пролога, но сделать это на C не должно быть слишком сложно. Возврат просто означает отмену назначения последнего назначенного узла.

в основном вы смотрите на модифицированную версию задачи о минимальном сокращении.

Одним из способов может быть изменение алгоритма Каргера. В алгоритме Каргера вы сжимаете вершины вдоль случайных ребер, пока не получите заканчиваются только двумя вершинами, остальные ребра представляют разрез. Поскольку это случайно, вы просто делаете это много раз и сохраняете решение с наименьшим количеством ребер в разрезе.

В модифицированной версии после того, как вершина схлопывается x раз, вы можете остановить схлопывание и подсчитать исходящие ребра (в вашем случае это будут разрезы), сделать это подходящее количество раз, и у вас есть решение. Сложная часть заключается в том, чтобы выяснить, сколько раз нужно повторить вычисления, чтобы повысить достоверность до удовлетворительного предела.