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