Основа проектирования алгоритма
На самом деле существует очень простая процедура проверки двудольности, а из ее анализа следует, что других препятствий, кроме нечетных циклов, нет. Сначала предположим, что граф G является связным, поскольку в противном случае мы могли бы сначала вычислить его компоненты связности и проанализировать каждую из них по отдельности.
В этот момент у нас либо появляется действительная красно-синяя окраска G, в которой каждое ребро имеет разноцветные концы, либо у какого-то ребра концы имеют одинако- вый цвет. Похоже, в последнем случае ничего сделать было нельзя: просто граф G не является двудольным. Теперь это обстоятельство нужно обосновать более формально, а также выработать эффективный способ раскраски.
Прежде всего следует заметить, что описанная процедура окрашивания по сути идентична описанию BFS: мы перемещаемся вперед от s, раскрашивая узлы, когда они впервые попадаются в процессе перебора. Более того, алгоритм окрашивания можно описать следующим образом: мы выполняем поиск BFS, узел s окрашива- ется в красный цвет, все узлы уровня L1 — в синий, все узлы уровня L2 в красный и так далее.
Нечетные уровни окрашиваются в синий цвет, а четные — в красный. Чтобы реализовать это описание на базе BFS, достаточно взять реализацию BFS и добавить дополнительный массив Color.
При каждом шаге BFS, на котором узел v добавляется в список L[i + 1], выполняется присваивание Color[v] = red, если i + 1 является четным числом, или Color[v] = blue, если i + 1 нечетное.
В конце этой процедуры остается перебрать все ребра и определить, не был ли присвоен обоим концам одинаковый цвет. Следовательно, общее время выполнения алгоритма
окрашивания составляет O(m + n), как и для алгоритма BFS.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу