Здравствуйте! Задача такая. В дереве на 2019 вершинах ровно три вершины имеют степень 1. Сколько вершин имеют степень 3?

задан 23 Сен '19 17:14

10|600 символов нужно символов осталось
2

В дереве с 2019 вершинами 2018 ребер. Сумма всех степеней вершин равна удвоенному количеству ребер. Отсюда следует, что если три вершины имеют степень 1, то 2015 имеют степень 2 и одна вершина степень 3.
Например, так. Пусть х вершин имеет степень 2. Тогда 2018*2>=3+2х+3(2016-х). Откуда х>=2015.
Также очевидно, что х<=2019-3=2016, а 2016 вершин степень 2 не могут иметь из-за четности.

ссылка

отвечен 23 Сен '19 17:58

изменен 23 Сен '19 18:07

@spades, Можно глупый вопрос. А почему в 2018*2>=3+2х+3(2016-х) больше либо равно, а не просто равно?

(24 Сен '19 23:30) Math_2012
1

Возможно есть вершины со степенью 4 и более

(24 Сен '19 23:48) spades
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×1,832
×9

задан
23 Сен '19 17:14

показан
1368 раз

обновлен
24 Сен '19 23:48

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru