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