Раскраски графов
Ошибка.
Попробуйте повторить позже
В графе любые два нечетных цикла имеют общую вершину. Докажите, что его вершины можно правильным образом покрасить в 
цветов. Напомним, что покраску вершин графа называют правильной, если никакие две одноцветные вершины не соединены
ребром.
Подсказка 1
Непонятно как красить весь граф в 5 цветов. Во сколько цветов вы умеете красить графы? Вспоминается, что нечетный цикл (которые, кстати, есть в условии) красится в 3 цвета, а граф без нечетных циклов в 2 цвета.
Подсказка 2
Попробуйте вершины разбить на 2 группы, одну покрасить в 2 цвета, а другую в 3.
Подсказка 3
Отбросьте один нечетный цикл из графа, может такое разбиение подойдет?
Найдем в графе наименьший цикл нечетной длины. Удалим все вершины, принадлежащие этому циклу, и все ребра, исходящие из этих
вершин. В оставшемся (не обязательно связном) графе не будет нечетных циклов, т.к. по условию любые два пересекались по вершине.
Тогда наш граф двудольный, а значит, мы можем покрасить его в 
цвета.
Вернем наш цикл вместе со всеми удаленными ребрами. Поскольку этот цикл был наименьшим, то любая вершина цикла была соединена
только с двумя вершинами из этого же цикла. Тогда его можно раскрасить в 
цвета, отличающиеся от 
предыдущих (одну вершину
красим в цвет 
для остальных вершин чередуем 
и 
цвета). Новые цвета не будут мешать раскраске остального графа. Значит, мы
смогли покрасить весь граф в 
цветов правильным образом.
Специальные программы
Программа
лояльности v2.0
Приглашай друзей в Школково и получай вознаграждение до 10%!
Крути рулетку
и выигрывай призы!
Крути рулетку и покупай курсы со скидкой, которая привязывается к вашему аккаунту.
Бесплатное онлайн-обучение
Для школьников из приграничных территорий России, проживающих в ДНР, ЛНР, Херсонской, Запорожской, Белгородской, Курской, Брянской областях и Крыму.
Налоговые вычеты
Узнай, как получить налоговый вычет при оплате обучения в «Школково».
Специальное предложение
для учителей
Бесплатный доступ к любому курсу подготовки к ЕГЭ, ОГЭ и олимпиадам от «Школково». Мы с вами делаем общее и важное дело, а потому для нас очень значимо быть чем-то полезными для учителей по всей России!
Вернём деньги за курс
за твою сотку на ЕГЭ
Сдать экзамен на сотку и получить обратно деньги за подготовку теперь вполне реально!
