Изменения

{{Определение |definition=Неориентированный = Двудольный граф <tex> G =(W, E) </tex> называется '''двудольным''', если множество его вершин можно разбить на две части <tex>U \cup V = W , |U| > 0, |V| > 0</tex>, так, что ни одна вершина в <tex>U</tex> не соединена с вершинами в <tex> U </tex> и ни одна вершина в <tex> V </tex> не соединена с вершинами в <tex>V</tex>.}}[[Файл: Bipartite_graph.png|300px|thumb|rightcenter|300pxПример [[Основные_определения_теории_графов#Двудольный_граф |Пример двудольного ]] графа]]

Граф 2-раскрашиваемый тогда и только тогда, когда он двудольный(англ. '' bipartite graph'' or ''bigraph'').

==Теорема КенигаКёнига==

== Следствие == === Алгоритм проверки графа на двудольность, используя обход в глубину===

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

== Источники ==1Произведём серию поисков в ширину (англ. Асанов М''Breadth-first search''). ОТ., Баранский Ве. Абудем запускать поиск в ширину из каждой непосещённой вершины.Ту вершину, Расин Виз которой мы начинаем идти, мы помещаем в первую долю. В. процессе поиска в ширину, если мы идём в какую- Дискретная математика: Графыто новую вершину, матроидыто мы помещаем её в долю, алгоритмыотличную от доли текущей вершину. '''ISBN 978-5-8114-1068-2'''<br />2Если же мы пытаемся пройти по ребру в вершину, которая уже посещена, то мы проверяем, чтобы эта вершина и текущая вершина находились в разных долях. Харари ФВ противном случае граф двудольным не является. - Теория графовПо окончании работы алгоритма мы либо обнаружим, что граф не двудолен, либо найдём разбиение вершин графа на две доли. '''ISBN 978-5-397-00622-4'''