Задача
Разумеется, треугольник не может быть двудольным: первый узел окрашива- ется в красный цвет, другой в синий, а с третьим уже ничего не сделать.
В более общем смысле возьмем цикл C нечетной длины с пронумерованными узлами 1, 2, 3, ... , 2k, 2k + 1. Если раскрасить узел 1 в красный цвет, то узел 2 должен быть окрашен в синий цвет, после чего узел 3 окрашивается в красный и т. д.; нечетные узлы окрашиваются в красный цвет, а четные в синий. Но тогда узел 2k + 1 должен быть красным, и от него ведет ребро к узлу 1 — тоже красному. Следовательно, раз- бить C на красные и синие узлы так, как требуется по условию задачи, невозмож- но. Обобщая далее, мы видим, что если граф G просто содержит нечетный цикл, можно применить тот же аргумент; следовательно, мы приходим к следующему утверждению.(3.14) Если граф G является двудольным, он не может содержать нечетные циклы.
Легко проверить, что граф является двудольным, если соответствующие мно- жества X и Y (то есть красные и синие узлы) уже были определены за нас; и во многих ситуациях, в которых встречаются двудольные графы, это естественно. Но предположим, имеется граф G без информации о разбиении, и нам хотелось бы определить, является ли граф двусторонним, то есть существует ли требуемое разбиение на красные и синие узлы. Насколько сложна эта задача? Из (3.14) вид- но, что одним из простых препятствий к двудольности графа является наличие нечетных циклов. Существуют ли другие, более сложные препятствия?
Еще по теме Задача:
- ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
- 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
- Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
- ЗАДАЧА
- ЗАДАЧА: РЕШЕНИЕ
- Основные задачи.
- в) Задачи
- в) Задачи
- ПСИХОАНАЛИЗ: ЗАДАЧА
- ЗАДАЧА ДВИГАТЕЛЬНАЯ
- Основные задачи
- Правило решаемой психологической задачи.
- Задачи и упражнения
- Терапевтическая задача
- 3. Задачи и функции социологии
- Основные задачи МПП.
- Задачи и упражнения
- Задачи
- Трудная задача
- 1.1. Предмет и задачи криминалистики