Вопрос 7 из 31

Практика: графы и маршруты

Почему нечётный цикл мешает раскрасить граф в два цвета

От чтения к действию

А теперь — вы

Одна компонента — цикл из шести вершин без дополнительных рёбер. Можно ли раскрасить его двумя цветами?

Разберёмся в теме

В двудольном неориентированном графе вершины разделяются на две группы, а каждое ребро соединяет разные группы. Это равносильно корректной раскраске двумя цветами. Нечётный цикл делает такую раскраску невозможной, поскольку при чередовании цветов конец цикла конфликтует с началом.

Объяснение и примеры

Частые вопросы

Где найти подробное решение?

Перейдите по ссылке «Объяснение и примеры» над этим блоком. Там разобрана тема текущего вопроса.

Можно ли попробовать снова?

Да. После проверки можно изменить ответ. Переход к следующему вопросу не блокируется результатом, а личный счёт не сохраняется.