Изменения
→Следствие
===Алгоритм проверки графа на двудольность, используя обход в глубину===
Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один [[Обход в глубину, цвета вершин|проход в глубину (англ. ''Depth-first search'')]].
На каждом шаге обхода в глубину помечаем вершину. Допустим, мы пошли в первую вершину — помечаем её как <tex> 1 </tex>. Затем просматриваем все смежные вершины, и если не помечена вершина, то на ней ставим пометку <tex> 2 </tex> и рекурсивно переходим в нее. Если же она помечена и на ней стоит та же пометка, что и у той, из которой шли (в нашем случае <tex> 1 </tex>), значит граф не двудольный.
===Алгоритм проверки графа на двудольность, используя обход в ширину===
Произведём серию поисков в [[Обход в ширину (англ. ''Breadth-first search'')|ширину]]. Т.е. будем запускать поиск в ширину из каждой непосещённой вершины. Ту вершину, из которой мы начинаем идти, мы помещаем в первую долю. В процессе поиска в ширину, если мы идём в какую-то новую вершину, то мы помещаем её в долю, отличную от доли текущей вершину. Если же мы пытаемся пройти по ребру в вершину, которая уже посещена, то мы проверяем, чтобы эта вершина и текущая вершина находились в разных долях. В противном случае граф двудольным не является.
По окончании работы алгоритма мы либо обнаружим, что граф не двудолен, либо найдём разбиение вершин графа на две доли.
