Анализ алгоритма

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

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

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

(ii) В G существует ребро, соединяющее два узла одного уровня. В этом случае G содержит цикл нечетной длины, а следовательно, не может быть двудольным.

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

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

удобства записи будем считать, что L0 («уровень 0») представляет собой множе- ство, состоящее только из 5. Теперь возьмем дерево BFS T, построенное нашим алгоритмом, и обозначим z узел наивысшего возможного уровня, для которого z является предком как x, так и у в дереве T; по очевидным причинам z можно на- звать низшим общим предком x и у. Допустим, z l, где i < j. Возникает ситуация, изображенная на рис. 3.6. Рассмотрим цикл C, определяемый переходом по пути z-x в T, затем по ребру e и затем по пути у-z в T. Длина этого цикла, вычисляемая суммированием длин трех частей, равна (j - i) + 1 + (j - i); получается 2( j - i) + 1, то есть нечетное число. ■


Рис. 3.6. Если два одноуровневых узла x и у соединены ребром, то цикл через x, у и их низшего общего предка z имеет нечетную длину; это показывает, что граф не может быть двудольным

3.5.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Анализ алгоритма:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. 2. Специфика и алгоритмы работы с источниками.
  9. Алгоритм обработки результатов.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. Принципы анализа происшествия.
  13. АНАЛИЗ
  14. АНАЛИЗ КОРОТКИЙ
  15. КОНТЕНТ - АНАЛИЗ
  16. Анализ документов
  17. МЕТОД АНАЛИЗА ЖИЗНИ
  18. АНАЛИЗ ДИСПЕРСИОННЫЙ
  19. Анализ линий