Как найти, является ли граф двудольным?

Question

Я пытался понять двудольный граф. Насколько я понимаю, это граф G, который можно разделить на два подграфа U и V. Так что пересечение U и V является нулевым множеством, а объединение - графом G. Я пытаюсь найти, если граф двудольный или не используется BFS. Тем не менее мне непонятно, как мы можем найти это с помощью BFS.

Скажем, у нас есть график, определенный ниже.

a:e,f 
b:e 
c:e,f,h 
d:g,h 
e:a,b,c 
f:a,c,g 
g:f,d 
h:c,d 

Что мне нужно здесь шаг за шагом объяснение того, как этот граф является двудольным или не использовать BFS.

Answer 1

Взятые из GeeksforGeeks

Ниже приводится простой алгоритм, чтобы выяснить, является ли данный граф Birpartite или не используя поиск в ширину (BFS): -

1. Присвоить RED цвет исходной вершины (положив в множество U).
2. Цвет всех соседей со СИНЯМ цветом (сдача в набор V).
3. Цвет соседа соседнего со КРАСНЫМ цветом (помещенный в набор U).
4. Таким образом, назначьте цвет всем вершинам таким образом, чтобы он удовлетворял всем ограничениям проблемы раскраски m-типа, где m = 2.
5. При назначении цветов, если мы найдем сосед, окрашенный тем же цветом, что и текущая вершина, то график не может быть окрашен двумя вершинами (или граф не является двудольным).

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

Также Примечание: -

-> Можно раскрасить цикл графа с четным циклом с использованием двух цветов.

-> Невозможно окрасить график циклов с нечетным циклом, используя два цвета.

РЕДАКТИРОВАТЬ: -

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

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

И, график будет называться двудольным, ЕСЛИ И ТОЛЬКО ЕСЛИ, каждый из его подключенных компонентов окажется двудольным.

Answer 2

Из Университета Карнеги-Меллона:

«Напомним, что граф G = (V, E) называется двудольным , если его множество вершин V можно разбить на два непересекающихся множества V1, V2 таким образом, что все ребра в E. имеют одну конечную точку в V1 и одну конечную точку в V2

(источник: http://www.cs.cmu.edu/~15251/homework/hw5.pdf).

вы уверены, что вам нужно использовать BFS? Определение, если граф, если двудольный требует определения длины цикла, и DFS, вероятно, лучше для обнаружения цикла, чем BFS.

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

Answer 3

Ниже приведен подход BFS, чтобы проверить, является ли граф двудольным.

• c = 0
• выбрать узел x и установить x.class = c
• пусть ys быть узлы, полученные BFS
  • c = 1-c
  • для y в ys набор y.class = c
  • если таковые y в ys есть сосед z с z.class == c то граф не является двудольным
  • повторить, пока не больше узлов не обнаружено
• граф двудольный

Это предполагает, что граф является одной компонентой связности - - если это не так, просто выполните эту процедуру для каждого компонента.

Answer 4

Сделайте это более простым способом.

Запуск алгоритма сильно связанных компонентов.

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

Answer 5

Это Prolog CLP (FD). Просто моделируйте каждое ребро в графе как переменную в домене 0..1. Затем смоделируйте каждую вершину в виде уравнения:

X #\= Y. 

Затем выпишите маркировку. Если маркировка находит решение, все готово. Однако он может найти множество решений. Вот пробег для примера:

Welcome to SWI-Prolog (Multi-threaded, 64 bits, Version 7.3.23) 
Copyright (c) 1990-2015 University of Amsterdam, VU Amsterdam 

:- use_module(library(clpfd)). 
problem(L) :- L=[A,B,C,D,E,F,G], 
    A #\= E, A #\= F, 
    B #\= E, 
    C#\= E, C#\= F, C#\= H, 
    D #\= G, D #\= H, 
    E #\= A, E #\= B, E #\= C, 
    F #\= A, F #\= C, F #\= G, 
    G #\= F, G #\= D, 
    H #\= C, H #\= D. 

?- problem(L), L ins 0..1, label(L). 
L = [0, 0, 0, 1, 1, 1, 0] ; 
L = [1, 1, 1, 0, 0, 0, 1]. 

работает и в GNU Prolog, SICStus Пролог, Jekejeke Minlog и т.д .. в основном с любой системой Prolog, реализующего CLP (FD). Альтернативно также можно использовать CLP (B) или dif/2.

Answer 6

Создайте дерево bfs. Если между вершинами одинакового уровня дерева есть ребра. Тогда граф не является двудольным, а другой - двудольным.