Система анализа алгоритмов

Теперь можно доказать утверждение о том, что этот алгоритм правильно опре- деляет, является ли граф двудольным. Также оно показывает, что если граф G не является двудольным, в нем можно найти нечетный цикл.

(3.15) Пусть G — связный граф, а L1, L2, … — уровни, построенные алгорит- мом BFS, начиная с узла s. В этом случае должно выполняться ровно одно из следующих двух условий.

• В G не существует ребра, соединяющего два узла одного уровня. В таком случае G является двудольным графом, в котором узлы четных уровней могут быть окрашены в красный цвет, а узлы нечетных уровней — в синий цвет.
• В G существует ребро, соединяющее два узла одного уровня. В этом случае

G содержит цикл нечетной длины, а следовательно, не может быть двудольным.

Доказательство. Сначала рассмотрим случай (i): предположим, не существует ребра, соединяющего два узла одного уровня. В соответствии с (3.4) мы знаем, что каждое ребро G соединяет узлы либо одного уровня, либо смежных уровней.

Предположение для случая (i) заключается в том, что первая из двух вариантов альтернатив не встречается, то есть каждое ребро соединяет два узла смежных уровней. Но наша процедура окрашивания назначает смежным уровням противо- положные цвета, поэтому каждое ребро имеет разноцветные концы. Следователь- но, описанная схема окрашивания обеспечивает двудольность G.

Теперь допустим, что выполняется условие (ii); почему граф G обязан содер- жать нечетный цикл? Известно, что G содержит ребро, соединяющее два узла одного уровня. Допустим, это ребро e = (x, y), при этом x, y Ѯ Lj.

Допустим, z Ѯ Li, где i < j. Возникает ситуация, изображенная на рис. 3.6. Рассмотрим цикл C, определяемый переходом по пути z–x в T, затем по ребру e и затем по пути y–z в T. Длина этого цикла, вычисляемая суммированием длин трех частей, равна ( j − i) + 1 + ( j − i); получается 2( j − i) + 1, то есть нечетное число.