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