6.7.3. Двудольное представление графов

Биграф, двудольный граф или чeтный граф – это математиче-

ский термин теории графов, который обозначает множество вершин и связей между ними, таких, что если множество вершин разбить на два непересекающихся подмножества V1 и V2, то связи будут только между вершинами из разных подмножеств.

Неориентированный граф G = (V,U) называется двудольным, если множество его вершин можно разбить на две части V1 V2 V , |V1 | > 0, |V2 | > 0, так, что выполняются условия:

ни одна вершина в V1 не соединена с вершинами в V1;

ни одна вершина в V2 не соединена с вершинами в V2. Двудольный граф называется полным двудольным графом, ес-

ли для каждой пары вершин v1 V1, v2 V2 существует ребро (v1,v2 ) U . Для |U | = i, |V | = j такой граф называется Ki,j

Теорема 6.12. Граф является двудольным тогда и только тогда, когда он 2-раскрашиваемый (то есть его хроматическое число равняется двум).

На самом деле, если раскрасить вершины графа в два цвета, то легко расположить все вершины одного цвета в одной доле, все