Изменения
Нет описания правки
На каждом шаге обхода в глубину метим вершину. Допустим мы пошли в первую вершину - добавляем ее в множество <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| Графы. Раскраски и укладки.]
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Раскраски графов]]
