Условие
В дереве 100 вершин. Какое в нём может быть:
а) наибольшее число концевых вершин;
б) наименьшее число концевых вершин?
Идея решения. Больше всего концевых вершин у «звезды», меньше всего — у цепи.
Решение
Все 100 концевыми быть не могут
В дереве из 100 вершин рёбер. Если бы все вершины были концевыми, из каждой выходило бы одно ребро, и рёбер было бы , а не 99.
а) Наибольшее число — 99
Возьмём «звезду»: одна вершина соединена со всеми остальными 99. Из каждой из этих 99 вершин выходит одно ребро — все они концевые. Значит, 99 концевых вершин возможно, а 100 — нет.
Меньше двух не бывает
В дереве, где есть рёбра, всегда не меньше двух концевых вершин: это крайние вершины самой длинной цепи.
б) Наименьшее число — 2
Соединим все 100 вершин в одну цепь. Концевыми будут только две крайние вершины.
Ответ
- а) 99
- б) 2
✓ Ответ проверен вычислением