{{Определение|definition=Неориентированный граф <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>.}}==Теорема Кенига=={{Теорема |about=Кёниг|statement=Граф <tex> G </tex> с конечным числом вершин является двудольным <tex> \iff </tex> когда все циклы в графе <tex> G </tex> имеют чётную длину.|proof=''Достаточность.'' Рассмотрим двудольный граф. Начнем цикл в доли <tex> U </tex>. Нужно пройти по четному числу ребер, чтобы подняться в <tex> U </tex> снова. Следовательно, при замыкании цикла число ребер будет четным. Очевидно, что в двудольном графе нет петель.''Необходимость.''Пусть ненулевой граф <tex> G </tex> связен и не имеет циклов нечетной длины. Выберем произвольно вершину <tex> u </tex> и разобьем множество всех вершин на на два непересекающихся множества <tex> V_0 </tex> и <tex> V_1 </tex> так, чтобы в <tex> V_0 </tex> лежали вершины <tex> v_0 </tex>,такие что кратчайшая цепь <tex>(u, v_0)</tex> была чётной длины, а в <tex> V_1 </tex> соответственно вершины <tex>v_1</tex>, для которых длина цепи <tex>(u, v_1)</tex> - нечётная. При этом <tex> u \in V_0 </tex>В <tex> G </tex>}} #перенаправление [[Файл:Двудольный граф.jpg|thumb|upright|Пример Раскраска двудольного графа]]== Раскраска в 2 два цвета ==Так как множество вершин двудольного графа можно разделить на 2 независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества <tex>\Rightarrow</tex> граф <tex>G = (W,E)</tex> - 2-раскрашиваем. <tex>\chi(G) = 2</tex>.Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину.На каждом шаге обхода в глубину метим вершину. Допустим мы пошли в первую вершину - добавляем ее в множество <tex> U </tex>. То есть ставим метку <tex> 1 </tex>. Затем просматриваем все смежные вершины и если не помечена вершина, то метим ее как <tex> 2 </tex> (то есть добавляем во множество <tex> V </tex> ) и рекурсивно переходим в нее. Если же она мечена и у нее такая же метка как у нашей - то все граф не двудольный.=== Источники ===1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. '''ISBN 978-5-8114-1068-2'''<br />2. Харари Ф. - Теория графов. '''ISBN 978-5-397-00622-4'''===См. также ===* [http://rain.ifmo.ru/cat/view.php/theory/graph-coloring-layout| Графы. Раскраски и укладки.][[Категория: Алгоритмы и структуры данных]][[Категория: Раскраски графов]]
