1. а) Какое наименьшее количество вершин степени 1 может быть у дерева, в котором 50 вершин? б) Какое наибольшее количество вершин степени 1 может быть у дерева, в котором 50 вершин?

Решение:

В любом дереве, если оно содержит более одной вершины, всегда есть хотя бы две вершины степени 1 (листья). Это связано с тем, что сумма степеней всех вершин в любом графе (включая дерево) равна удвоенному числу рёбер. В дереве с n вершинами число рёбер равно n-1. Следовательно, сумма степеней вершин равна 2(n-1). Если бы все вершины имели степень больше 1, то минимальная степень была бы 2. Тогда сумма степеней была бы не менее 2n, что противоречит равенству 2(n-1).

• а) Наименьшее количество вершин степени 1: В дереве с 50 вершинами, минимальное количество вершин степени 1 равно 2.
• б) Наибольшее количество вершин степени 1: Максимальное количество вершин степени 1 достигается, когда одна вершина имеет степень 49, а остальные 49 вершин имеют степень 1.

Ответ: а) 2; б) 49