Проверка двудольности: практическое применение поиска в ширину

Вспомним определение двудольного графа: так называется граф, множество уз- лов V которого может быть разбито на такие подмножестваX и Y, что один конец каждого ребра принадлежит X, а другой конец принадлежит Y.
Чтобы обсуждение было более наглядным, представьте, что узлы множества X окрашены в красный цвет, а узлы множества Y — в синий. Тогда можно сказать, что граф является двудольным, если его узлы можно раскрасить в красный и синий цвет так, чтобы у каждого ребра один конец был красным, а другой синим.

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

Еще по теме Проверка двудольности: практическое применение поиска в ширину:

  1. Часть вторая. Практическое применение
  2. Практическое применение
  3. Практическое применение
  4. Практическое применение типоведения
  5. Практическое применение стратегий Аристотеля
  6. Глава 10 ДРУГИЕ ОБЛАСТИ ПРАКТИЧЕСКОГО ПРИМЕНЕНИЯ Р-МЕТОДА
  7. Глава VI ПРИЕМЫ ПСИХОЛОГО-ПЕДАГОГИЧЕСКОГО ВЗАИМОДЕЙСТВИЯ И ТЕХНОЛОГИЯ ИХ ПРИМЕНЕНИЯ В ПРАКТИЧЕСКОЙ ДЕЯТЕЛЬНОСТИ
  8. Проверка содержательности и достоверности информации является более сложным делом и требует другого аппарата и других методов проверки.
  9. Поиск смысла жизни – это поиск бессмертия!
  10. 12.5. Тактика проверки показаний на месте
  11. Статья 162. Аудиторская проверка
  12. § 10. Психология проверки показаний на месте
  13. Проверка криминалистической версии
  14. ПРОВЕРКА ГИПОТЕЗ СТАТИСТИЧЕСКИХ
  15. Проверка показаний на месте
  16. фиксация хода и результатов проверки показаний на месте.
  17. Правило критической проверки веера версий.
  18. Проверка версий о самооговоре
  19. 6.2.6. Шаг пятый :проверка причинности
  20. Проверка и настройка.