Изменения

Неориентированный граф <tex>G = (W,E)</tex> называется '''двудольным''', если множество его вершин можно разбить на две части <tex> U \cup V = W , \mid U\mid > 0, \mid V\mid > 0</tex>, так, что ни одна вершина в <tex>U</tex> не соединена с вершинами в <tex>U</tex> и ни одна вершина в <tex>V</tex> не соединена с вершинами в <tex>V</tex>.

Граф <tex> G </tex> с конечным числом вершин является двудольным <tex> \iff </tex> тогда и только тогда, когда все циклы в графе <tex> G </tex> имеют чётную длину.

[[Файл:Двудольный граф.jpg|thumb|upright|Пример двудольного графа]]  Рассмотрим двудольный граф. Начнем цикл в доли <tex> U </tex>. Нужно пройти по четному числу ребер, чтобы подняться в <tex> U </tex> снова. Следовательно, при замыкании цикла число ребер будет четным. Очевидно, что в двудольном графе нет петель. 

== Раскраска в 2 цвета Алгоритм == Так как множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества <tex>\Rightarrow</tex> граф <tex>G = (W,E)</tex> - 2 - раскрашиваем. <tex>\chi(G) = 2</tex>.

Так жекак граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину.На каждом шаге обхода в глубину помечаем вершину. Допустим мы пошли в первую вершину - помечаем её как <tex> 1 </tex>. Затем просматриваем все смежные вершины и если граф не помечена вершина, то на ней ставим пометку <tex> 2 - раскрашиваем, значит множество его вершин можно разделить </tex> и рекурсивно переходим в нее. Если же она помечена и на два непересекающихся множества такней стоит та же пометка, что и у той, из которой шли(в каждом из них не найдется двух смежных вершиннашем случае <tex> 1 </tex>), то значит граф является двудольнымне двудольный.