46. Двудольные графы. Необходимое и достаточное условие двудольности графа.

Двудольный граф (или биграф, бихроматический граф, четный граф, граф паросочетаний) G — это граф, множество вершин V которого можно разбить на два подмножества V1 и V2 таким образом, что каждое ребро графа G соединяет вершины из разных множеств.

Теорема. Граф является двудольным тогда и только тогда, когда все его простые циклы четны.

Если граф G содержит все ребра, соединяющие V1 и V2, то этот граф называется полным двудольным.