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