Проектирование алгоритма

На самом деле существует очень простая процедура проверки двудольности, а из ее анализа следует, что других препятствий, кроме нечетных циклов, нет. Сначала предположим, что граф G является связным, поскольку в противном случае мы могли бы сначала вычислить его компоненты связности и проанализировать каж- дую из них по отдельности.
Затем мы выбираем любой узел 5 V и окрашиваем его в красный цвет; никакой потери общности при этом не происходит, так как 5 все равно должен быть связан с каким-то цветом. Все соседи 5 должны быть окрашены в синий цвет, мы так и поступаем. Все соседи этих узлов окрашиваются в красный цвет, их соседи в синий и т. д., пока не будет раскрашен весь граф. В этот момент у нас либо появляется действительная красно-синяя окраска G, в которой каждое ребро имеет разноцветные концы, либо у какого-то ребра концы имеют одинако- вый цвет. Похоже, в последнем случае ничего сделать было нельзя: просто граф G не является двудольным. Теперь это обстоятельство нужно обосновать более формально, а также выработать эффективный способ раскраски.

Прежде всего следует заметить, что описанная процедура окрашивания по сути идентична описанию BFS: мы перемещаемся вперед от 5, раскрашивая узлы, когда они впервые попадаются в процессе перебора. Более того, алгоритм окрашивания можно описать следующим образом: мы выполняем поиск BFS, узел 5 окрашива- ется в красный цвет, все узлы уровня L1 — в синий, все узлы уровня L2 в красный и так далее. Нечетные уровни окрашиваются в синий цвет, а четные — в красный.

Чтобы реализовать это описание на базе BFS, достаточно взять реализацию BFS и добавить дополнительный массив Color. При каждом шаге BFS, на котором узел v добавляется в список L[i + 1], выполняется присваивание Color[v] = red, если i + 1 является четным числом, или Color[v] = blue, если i + 1 нечетное. В конце этой процедуры остается перебрать все ребра и определить, не был ли присвоен обоим концам одинаковый цвет. Следовательно, общее время выполнения алгоритма окрашивания составляет O(m + n), как и для алгоритма BFS.

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

Еще по теме Проектирование алгоритма:

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