Разделите график на два набора

Question

Вопрос от Code jam.

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

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

Answer 1

Вы создаете граф из заданных узлов (используя хеш-таблицу для сопоставления имен узлам), а затем вы используете BFS или DFS для перемещения по графу и определения того, является ли его двудольный (то есть divisibe на два непересекающихся множества таких что узел в одном наборе находится только в «проблемах» с узлами другого набора, но не с каким-либо узлом в своем собственном наборе). Это делается путем присвоения булевому значению каждому узлу при его посещении BFS/DFS и затем проверке того, имеет ли одно из его посещенных соседей одно и то же значение, что означает, что граф не двудольный (не делимый на две группы).

Answer 2

Во-первых, проблема осуществимости (есть такой комплект/не существует такой набор) является 2-coloring problem, где:

G = (V,E) 
V = { all nodes } 
E = { (u,v) | u and v are "troubling each other" } 

Эта задача решается путем проверки, если граф bi-partite, и может быть сделано используя BFS.

---

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

Прежде всего, предположим, что график является двучастным, поэтому существует некоторое решение.

Разделить график на набор подключенных компонентов: (S1,S2,S3,...,Sk).
Каждая компонента связности на самом деле является подграфом (Si = Li, Ri) - где Li, Ri - две стороны двудольного графа (в каждой связной компоненте есть только одно такое расщепление, если игнорировать порядок Li и Ri) ,

Создать новый массив:

arr[i] = |Li| - |Ri| 
where |X| is the cardinality of X (number of elements in the set) 

Теперь, решая эту проблему так же, как решение в partition problem, что может быть сделано в псевдо-полиномиальное время (который полиномиальное числе узлов).

Решение разделить проблему разбивает каждый arr[i] быть в A или в B, таким образом, что sum{A} ближе, насколько это возможно, чтобы sum{B}. Если arr[i] находится в A, в вашем решении цвет Li с «1» и Ri с «2». В противном случае - сделайте наоборот.

Решение будет O(k*n+m), где k это число компонент связности, n это число узлов в графе, а m это число ребер в графе.