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

Question

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

V = {А, В, С, D}
E = {(A, B), (A,D), (C, D)}

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

Answer 1

Ваша первая догадка верна — пересекайте график и чередуйте его.

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

Answer 2

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

Answer 3

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

Граф двудольный тогда и только тогда, когда он раскрашивается в 2 цвета.

Answer 4

Из Википедии (http://en.wikipedia.org/wiki/Bipartite_graph)

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

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

Answer 5

Я реализовал это в своем инструмент для рисования графиков, вы можете увидеть мой код на JavaScript.

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

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

Answer 6

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

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.Конечно, мне пришлось это изменить, потому что я потратил свой стек на более крупных графиках.Также, чтобы отдать должное, этот код основан на коде Википедии для ДФС.

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