В дереве нет вершин степени 2. Докажите, что количество висячих вершин (т.е. вершин степени 1) больше половины общего количества вершин.

Предположим, что в графе было x вершин степени 1 и n − x вершин степени хотя бы 3. Тогда
$ \sum_{i=1}^{n}{deg(v_i)} $ ≥ 1 · x + (n − x) · 3 = 3n − 2x. С другой стороны $ \sum_{i=1}^{n}{deg(v_i)} $ = 2 · (n − 1) = 2n − 2 ⇒ 2n − 2 ≥ 3n − 2x ⇔ 2x ≥ n + 2 ⇔ x ≥ (n + 2) / 2 = 1 + n / 2. Получим, что количество вершин степени 1 больше
половины общего количества вершин.


info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp