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

Теорема о двудольности

Граф G = (X, A) является двудольным тогда и только тогда, когда он не содержит циклов нечетной длины.

1. Необходимость. Поскольку множество X разбивается на две части X^а и X^b , то X^а X^b = X и X^а X^b = Ø .

Пусть существует цикл нечетной длины х_i1 , х_i2, ...,х_{i q} , х_i1 . Без потери общности допустим, что х_i1 X^а . Согласно определению одна из двух следующих друг за другом вершин этого цикла должна принадлежать множеству X^а , а другая – множеству X^b , тогда имеем: х_i2 X^b, х_i3 X^а и т. д. Следовательно, х_ik X^а , если k – нечетное, и х_ik X^b , если k – четное.

Мы предположили, что длина цикла нечетная. Поэтому из соотношения х_{i q} X^а следует, что х_i1 X^b . Это противоречит исходному условию, поскольку X^а X^b = Ø и вершина не может принадлежать одновременно как X^a , так и X^b .

Для большей ясности можно рассмотреть цикл нечетной длины для графа, изображенного на рис. 5.6:

 

Рис. 5.6. Построение цикла

х₁---х₃--- х₅--- х₄--- х₂--- х₁

X^а X^b X^а X^b X^а X^b .

Поочередно помечая вершины, мы видим противоречие: вершина Х₁ X^а и согласно определению должна принадлежать X^b, следовательно, рассматриваемый граф не является двудольным.

2. Достаточность. Предположим, что в графе G не существует цикла нечетной длины. Выберем одну из вершин графа, например, х_i, и пометим ее"+". Выполним итерационную процедуру.

Берем уже помеченную вершину х_i и помечаем все вершины из множества Г⁺¹(х_i) знаком, противоположным тому, который присвоен вершине х_i .

Будем продолжать эту операцию до тех пор, пока не будет сделано следующее:

1) все вершины не будут помечены, а знаки, приписанные им, согласованы (иными словами, любые две вершины, соединенные ребром, помечены противоположными знаками);

2) для каждой помеченной вершины х_i все вершины из множества Г⁺¹(х_i) помечены, но существуют другие, еще не помеченные вершины;

3) некоторая вершина, например х_ik , которая была уже помечена каким-то знаком ("+" или"–"), может быть помечена теперь (со стороны другой вершины) знаком, противоположным приписанному вершине х_ik .

В случае 1 все вершины , помеченные знаком"+", отнесем к множеству X^a , а помеченные знаком "–" – к множеству X^b . Поскольку все ребра соединяют вершины, помеченные противополож-ными знаками, то граф является двудольным.

Рассмотрим граф на рис. 5.6. Пометим знаком"+", например, вершину х₁ . Найдем отображение Г⁺(х₁) = { х₄, х₅ }. Вершины х₄ и х₅ пометим знаком"–". Отображение Г⁺(х₄, х₅) = = { х₂, х₃ }, помечаем вершины х₂ и х₃ знаком"+". Г⁺(х₂, х₃) = = { х₄, х₅, х₆ }. Оставшуюся непомеченной вершину х₆ помечаем знаком"–". Таким образом, получили два подмножества вершин X^a = { х₁, х₂, х₃ } и X^b = { х₄, х₅, х₆ } и показали, что рассматриваемый граф является двудольным.

Случай 2 означает, что между помеченной и непомеченной вершинами не существует дуги. Перейдем к неориентированному графу и повторим процедуру пометок знаками "+" и"–". Если остались непомеченные вершины, то это означает, что граф распадается на две или больше частей, и каждая из них может тогда рассматриваться отдельно. Итак, в конце приходим к случаю 1.

В графе на рис. 5.5в, пометки были начаты знаком "+" с вершины х ₂ . Г⁺(х₂) = { х₄ }. Вершина х₄ помечается знаком"–". Г⁺(х₄) = { х₃ }. Вершина х₃ помечается знаком"+". Г⁺(х₃) = Ø.

В графе остались непомеченные вершины, но если перейти к неориентированному двойнику этого графа, то процедура пометок легко выполняется и множество вершин разбивается на два подмножества Х^a= { х₁, х₂, х₃ } и Х^b= { х₄, х₅, х₆ }, тем самым исходный граф является двудольным.

В случае 3 вершина х_ik должна быть помечена знаком "+" на некотором маршруте (например, М₁), состоящем из вершин х_i1, х_i2, ..., х_ik ; причем знаки "+" и"–", приписываемые этим вершинам при движении по маршруту М₁, должны образовывать чередующуюся последовательность. Например, для графа на рис. 5.5г маршрут М₁можно выбрать таким:

М₁: х₁ х₃ х₅ х₄ х₂.

"+" "-" "+" "-" "+"

Аналогично знаком "-" вершина х_ik помечается вдоль некоторого маршрута М₂ . Например,

М₂: х₁ х₄ х₆ х₂.

"+" "-" "+" "-"

Пусть x^* – предпоследняя (последней является х_ik ) общая вершина маршрутов М₁ и М₂ . Если вершина x^* помечена знаком"+", то участок от x^* до х_ik маршрута М₁ должен быть четным, а участок от x^* до х_ik маршрута М₂ должен быть нечетным. Если же вер-шина x^* помечена знаком"-", то участок маршрута М₁ будет нечетным, а маршрута М₂ – четным. Следовательно, цикл, состоящий из участка маршрута М₁ , от x^* до х_ik , и соответствующего участка маршрута М₂ , от х_ik до x^* , имеет нечетную длину. Это противоречит предположению, что граф не содержит циклов нечетной длины, и, значит, случай 3 невозможен.

В рассматриваемом примере x^* = х₄ . В маршруте М₁ длина участка от х₄ до х₂ равна 1, а в маршруте М₂ длина участка от х₄ до х₂ равна 2, что в сумме составляет нечетное число, следовательно, граф содержит цикл нечетной длины и не является двудольным.