Двудольные графы и раскраска в 2 цвета

Определение:

Неориентированный граф [math] G =(W, E) [/math] называется двудольным, если множество его вершин можно разбить на две части [math]U \cup V = W , |U| \gt 0, |V| \gt 0[/math], так, что ни одна вершина в [math]U[/math] не соединена с вершинами в [math] U [/math] и ни одна вершина в [math] V [/math] не соединена с вершинами в [math]V[/math].

Раскраска в 2 цвета

Теорема:

Граф 2-раскрашиваемый тогда и только тогда, когда он двудольный.

Доказательство:

[math]\triangleright[/math]

Файл:Bipartite graph.jpg Пример двудольного графа Если множество вершин двудольного графа можно разделить на два независимых подмножества так, что ни одна из вершин ни в одном из этих подмножеств не является смежной к вершине из этого же подмножества, тогда граф [math]G = (W, E)[/math] — 2-раскрашиваем. [math]\chi(G) = 2[/math]. Если же граф 2-раскрашиваемый, то множество его вершин можно разделить на два непересекающихся множества так, чтобы в каждом из них не нашлось двух смежных вершин. Тогда граф будет двудольным.

[math]\triangleleft[/math]

Теорема Кенига

Теорема (Кениг):

Граф [math] G [/math] является двудольным тогда и только тогда, когда все циклы в графе [math] G [/math] имеют чётную длину.

Доказательство:

[math]\triangleright[/math]

Достаточность. Рассмотрим двудольный граф. Начнем цикл в доли [math] U [/math]. Нужно пройти по четному числу ребер, чтобы вернуться в [math] U [/math] снова. Следовательно, при замыкании цикла число ребер будет четным. Необходимость. Пусть ненулевой граф [math] G [/math] связен и не имеет циклов нечетной длины. Выберем произвольно вершину [math] u [/math] и разобьем множество всех вершин на два непересекающихся множества [math] U [/math] и [math] V [/math] так, чтобы в [math] U [/math] лежали вершины [math] v_0 [/math], такие что кратчайшая цепь [math](u, v_0)[/math] была чётной длины, а в [math] V [/math] соответственно вершины [math]v_1[/math], для которых длина цепи [math](u, v_1)[/math] — нечётная. При этом [math] u \in U [/math]. В графе [math] G [/math] нет ребер [math]ab[/math], таких что [math]a, b [/math] лежат одновременно в [math] U [/math] и [math]V[/math]. Докажем это от противного. Пусть [math]a, b \in U [/math]. Зададим [math] P_0 [/math] — кратчайшая [math] (u, a) [/math] цепь, а [math] P_1 [/math] — кратчайшая [math] (u, b) [/math] цепь. Обе цепи четной длины. Пусть [math] v_0 [/math] — последняя вершина цепи [math] P_0 [/math], принадлежащая [math] P_1 [/math]. Тогда подцепи от [math] u [/math] до [math] v_0 [/math] в [math] P_0[/math] и [math]P_1[/math] имеют одинаковую длину (иначе бы, пройдя по более короткой подцепи от [math]u[/math] до [math]v_0[/math] мы смогли бы найти более короткую цепь от [math] u [/math] до [math] a [/math] или от [math] u [/math] до [math] b [/math], чем цепь [math] P_0 [/math] или [math] P_1 [/math] ). Так как подцепи от [math] v_0 [/math] до [math] a [/math] и от [math] v_0 [/math] до [math] b [/math] в цепях [math] P_0 [/math] и [math] P_1 [/math] имеют одинаковую четность, а значит в сумме с ребром [math] ab [/math] они образуют цикл нечётной длины, что невозможно.

[math]\triangleleft[/math]

Алгоритм

Так как граф является двудольным тогда и только тогда, когда все циклы четны, определить двудольность можно за один проход в глубину. На каждом шаге обхода в глубину помечаем вершину. Допустим мы пошли в первую вершину — помечаем её как [math] 1 [/math]. Затем просматриваем все смежные вершины и если не помечена вершина, то на ней ставим пометку [math] 2 [/math] и рекурсивно переходим в нее. Если же она помечена и на ней стоит та же пометка, что и у той, из которой шли (в нашем случае [math] 1 [/math]), значит граф не двудольный.

Источники

1. Асанов М. О., Баранский В. А., Расин В. В. - Дискретная математика: Графы, матроиды, алгоритмы. ISBN 978-5-8114-1068-2
2. Харари Ф. - Теория графов. ISBN 978-5-397-00622-4

См. также

• Графы. Раскраски и укладки.