Задача

В предыдущих главах приводились примеры двудольных графов. Для начала за- дадимся вопросом: существуют ли естественные примеры недвудольных графов, то есть графов, для которых такое разбиение V невозможно?

Разумеется, треугольник не может быть двудольным: первый узел окрашива- ется в красный цвет, другой в синий, а с третьим уже ничего не сделать.

В более общем смысле возьмем цикл C нечетной длины с пронумерованными узлами 1, 2, 3, ... , 2k, 2k + 1. Если раскрасить узел 1 в красный цвет, то узел 2 должен быть окрашен в синий цвет, после чего узел 3 окрашивается в красный и т. д.; нечетные узлы окрашиваются в красный цвет, а четные в синий. Но тогда узел 2k + 1 должен быть красным, и от него ведет ребро к узлу 1 — тоже красному. Следовательно, раз- бить C на красные и синие узлы так, как требуется по условию задачи, невозмож- но. Обобщая далее, мы видим, что если граф G просто содержит нечетный цикл, можно применить тот же аргумент; следовательно, мы приходим к следующему утверждению.

(3.14) Если граф G является двудольным, он не может содержать нечетные циклы.

Легко проверить, что граф является двудольным, если соответствующие мно- жества X и Y (то есть красные и синие узлы) уже были определены за нас; и во многих ситуациях, в которых встречаются двудольные графы, это естественно. Но предположим, имеется граф G без информации о разбиении, и нам хотелось бы определить, является ли граф двусторонним, то есть существует ли требуемое разбиение на красные и синие узлы. Насколько сложна эта задача? Из (3.14) вид- но, что одним из простых препятствий к двудольности графа является наличие нечетных циклов. Существуют ли другие, более сложные препятствия?

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

Еще по теме Задача:

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