Теория графа: разбиение графика

У меня есть эта проблема. У меня есть график из n узлов, которые я хочу разбить на два подграфа x узлов и n-x узлов, которые ограничены тем, что число оставшихся ребер максимизируется (или минимизирует количество ребер, которые разрезаются).

Не уверен, что это имеет смысл. Не человек теории графа, но это абстрактная версия моей проблемы. Какие алгоритмы я должен смотреть, что может помочь мне?

Это НЕ домашняя проблема. Интересная проблема, хотя я думаю!

Я планирую реализовать на C.

Ответ 1

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

Ответ 2

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

Учитывая полный набор узлов S, пусть P и P '- множества узлов, изначально пустые, а K - числом режущих ребер, изначально 0.
Пусть S *, K * - наилучшее известное решение и его количество режущих ребер, причем K * изначально бесконечна.
Выберите node N, чтобы начать и назначить его S.
Для каждого неназначенного node M:
- Назначьте M в S 'и добавьте количество ребер из M в узлы в S до K.
- Если K > K *, то никакое решение, основанное на этом, не превзойдет самого лучшего, поэтому назначьте M в S.
- Если | S | > X, тогда множество стало слишком большим; отступаться.
- В противном случае, рекурсия из 4.
Если все узлы назначены и K < K *, то пусть S * = S и K * = K.

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

Ответ 3

В основном вы смотрите на измененную версию проблемы с минимальным разрешением.

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

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