Дано:
Количество вершин в дереве: 50.
Найти:
Наибольшее количество вершин степени 1 в дереве с 50 вершинами.
Решение:
В дереве с n вершинами количество рёбер m равно n - 1. Для нахождения количества вершин степени 1 обозначим их как k. Пусть p - количество вершин степени больше 1. Тогда:
k + p = 50,
1*k + s*p = 2m = 2(n - 1) = 2(50 - 1) = 98, где s - средняя степень остальных вершин.
Чтобы максимизировать k, минимизируем p. Минимальное значение p равно 1 (тогда одна вершина степени больше 1). Подставим p = 1:
k + 1 = 50,
k = 49.
Теперь подставим в уравнение с суммой степеней:
1*49 + s*1 = 98,
49 + s = 98,
s = 49.
Это допустимо, так как одна вершина может иметь степень 49.
Ответ: Наибольшее количество вершин степени 1 равно 49.