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

Теперь можно доказать утверждение о том, что этот алгоритм правильно определяет, является ли граф двудольным. Также оно показывает, что если граф 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.

Кроме того, для удобства записи будем считать, что L0 («уровень 0») представляет собой множество, состоящее только из s. Теперь возьмем дерево BFS T, построенное нашим алгоритмом, и обозначим z узел наивысшего возможного уровня, для которого z является предком как x, так и y в дереве T; по очевидным причинам z можно назвать низшим общим предком x и y.

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