Анализ алгоритма
(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.
Еще по теме Анализ алгоритма:
- § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
- Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
- Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
- АЛГОРИТМ
- АЛГОРИТМ УДАЧИ
- Алгоритм исцеления:
- Алгоритм избавления от боли
- 2. Специфика и алгоритмы работы с источниками.
- Алгоритм обработки результатов.
- СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
- 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
- Принципы анализа происшествия.
- АНАЛИЗ
- АНАЛИЗ КОРОТКИЙ
- КОНТЕНТ - АНАЛИЗ
- Анализ документов
- МЕТОД АНАЛИЗА ЖИЗНИ
- АНАЛИЗ ДИСПЕРСИОННЫЙ
- Анализ линий