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

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

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

Это не домашняя задача. Интересная проблема, хотя я подумай!

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

3 16
algorithm graph-theory

3 ответа:

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

11

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

  1. учитывая полное множество узлов S, пусть P и P' - множества узлов, изначально пустые, а K-число обрезанных ребер, изначально равное 0.
  2. Пусть S*, K* - наиболее известное решение и его число обрезанных ребер, причем K* изначально бесконечно.
  3. Выберите узел N для начала и назначить С.
  4. для каждого неназначенного узла M:
    1. назначить м в S', и добавить количество ребер из M узлов в К.
    2. Если K > K*, то никакое решение, основанное на этом, не будет лучшим, поэтому назначьте M на S.
    3. Если |S| > X, то набор стал слишком большим; обратный путь.
    4. в противном случае рекурсия из 4.
  5. Если все узлы назначены и K

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

2

В основном вы смотрите на модифицированную версию задачи min-cut.

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

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

0