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

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

5 голосов
/ 31 октября 2009

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

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

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

Ответы [ 6 ]

5 голосов
/ 31 октября 2009

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

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

2 голосов
/ 31 октября 2009

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

1 голос
/ 04 октября 2011

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

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

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

1 голос
/ 31 октября 2009

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

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

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

1 голос
/ 31 октября 2009

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

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

0 голосов
/ 01 ноября 2009

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

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.

...