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