Как разделять двудольный граф по цвету?

Question

К примеру, предположим, что есть граф G = (V, E), где

В = {А, В, С, D}
Е = {(А, В), (А, D), (C, D)}

Этот граф двудольный и поэтому может быть разбит на два непересекающихся множества {A, C} и {B, D}. Мое первое предположение состоит в том, что я могу просто ходить по графу и назначать переменные цвета для каждой вершины. Это так, или это сложнее/проще, чем это? Существуют ли для этого известные алгоритмы?

Answer 1

Ваша первая предпосылка правильная - пересечь график и чередовать.

Алгоритм должен быть простым. Я бы запустил две очереди узлов, по одному для каждого цвета. Поменяйте узлы с очередей поочередно, пометьте свой цвет и нажмите любые не посещаемые соседние узлы в очередь для противоположного цвета. Завершить, когда количество посещенных узлов + длина обеих очередей = количество узлов в графике.

Answer 2

Если вы уверены, что граф biparte, то вы можете просто назначить цвета чередуя их для перемещения каждой вершины, так как он считает, что:

Граф является двудольным тогда и только тогда, когда это 2- раскраска.

Answer 3

Материал из Википедии (http://en.wikipedia.org/wiki/Bipartite_graph)

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

Таким образом, можно эффективно проверить, является ли граф двудольным, используя этот метод контроля четности для назначения вершин двум подмножествам U и V отдельно в каждом соединении компонент графа, а затем изучить каждое ребро, чтобы убедиться, что он имеет конечные точки, назначенные t o разные подмножества.

Answer 4

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

Answer 5

Только в случае, если кто-то любопытно, вот код, который я придумал:

def dfs(root, colorings): 
    to_visit1 = deque() 
    to_visit2 = deque() 
    to_visit1.append(root) 
    while len(to_visit1) != 0 or len(to_visit2) != 0: 
     dfs_color(to_visit1, to_visit2, True, colorings) 
     dfs_color(to_visit2, to_visit1, False, colorings) 

def dfs_color(queue, opposite_queue, color, colorings): 
    while len(queue) != 0: 
    v = queue.pop() 
    if v in adjacency_list: 
     colorings[v] = color 
     neighbors = adjacency_list[v] 
     del adjacency_list[v] 
     for neighbor in neighbors: 
     opposite_queue.append(neighbor) 

Следует признать, что это не мой лучший код. Я использую True/False как цвет, потому что, когда я использовал рекурсию, это упростило просто сказать not color. Конечно, мне пришлось изменить его, потому что я взорвал свой стек на больших графиках. Также, чтобы отдать должное, этот код основан на коде Википедии для DFS.

Хотя, как было указано, я думаю, что это может быть просто замаскированная BFS.

Answer 6

Я внедрил его в своем graph drawing tool, вы можете увидеть мой код в JavaScript.

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

Может быть, это можно сделать проще, но в течение последних нескольких месяцев у меня было несколько жестких Пролог - дней кодирования Haskell, может быть, это затронуло мой мозг, и теперь я вижу рекурсию во всем :-D