Изменения
Нет описания правки
|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>.
}}
{{Теорема
|statement=
Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф <tex>G = (W,E)</tex> - — 2 - раскрашиваем. <tex>\chi(G) = 2</tex>.
Так же, если граф 2 - раскрашиваем, значит множество его вершин можно разделить на два непересекающихся множества так, что в каждом из них не найдется двух смежных вершин, то граф является двудольным.
}}
{{Теорема
|about=
|statement=
Граф <tex> G </tex> является двудольным тогда и только тогда, когда все циклы в графе <tex> G </tex> имеют чётную длину.
