Страница 68 номер 91, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Какое наименьшее и какое наибольшее количество листьев может иметь дерево, у которого 5 вершин? 50 вершин? 2024 вершины?
Дерево с \(n\) вершинами содержит \(n-1\) ребро, поэтому сумма степеней его вершин равна \(2(n-1) = 2n - 2\).
Наименьшее число листьев. У самой длинной цепи \(v_0 v_1 \ldots v_k\) оба конца — листья: второе ребро из \(v_0\) вело бы либо в вершину вне цепи (цепь удлинилась бы), либо в вершину самой цепи (получился бы цикл); то же и для \(v_k\). Значит, листьев не меньше двух, а ровно два даёт цепь из \(n\) вершин.
Наибольшее число листьев. Все \(n\) вершин листьями быть не могут: сумма степеней равнялась бы \(n\), а она равна \(2n - 2\), что при \(n \geqslant 3\) больше. Значит, листьев не больше \(n-1\), а ровно \(n-1\) даёт дерево, в котором одна вершина соединена со всеми остальными: её степень \(n-1\), у прочих \(n-1\) вершин — 1.
При 5 вершинах листьев от 2 до \(5 - 1 = 4\); при 50 вершинах — от 2 до \(50 - 1 = 49\); при 2024 вершинах — от 2 до \(2024 - 1 = 2023\).
Ответ: у дерева с 5 вершинами наименьшее число листьев 2, наибольшее 4; с 50 вершинами — 2 и 49; с 2024 вершинами — 2 и 2023.
Какое наименьшее и какое наибольшее количество листьев может иметь дерево, у которого 5 вершин? 50 вершин? 2024 вершины?
Дерево с \(n\) вершинами содержит \(n-1\) ребро, поэтому сумма степеней всех его вершин равна \(2(n-1) = 2n - 2\).
Наименьшее число листьев. Возьмём в дереве самую длинную цепь \(v_0 v_1 \ldots v_k\). Оба её конца — листья: если бы из \(v_0\) выходило ещё одно ребро, оно вело бы либо в вершину вне цепи (тогда цепь можно было бы удлинить), либо в вершину самой цепи (тогда получился бы цикл). То же рассуждение годится и для \(v_k\). Значит, листьев не меньше двух.
Ровно два листа бывает: у цепи из \(n\) вершин две концевые вершины имеют степень 1, а все остальные — степень 2.
Наибольшее число листьев. Все \(n\) вершин листьями быть не могут: тогда сумма степеней равнялась бы \(n\), а она равна \(2n - 2\), и при \(n \geqslant 3\) число \(2n - 2\) больше, чем \(n\). Значит, при \(n \geqslant 3\) листьев не больше \(n-1\) (в дереве из двух вершин листьями будут обе).
Ровно \(n-1\) лист бывает: соединим одну вершину со всеми остальными. Получится связный граф без циклов с \(n-1\) ребром, у которого одна вершина имеет степень \(n-1\), а остальные \(n-1\) вершина — степень 1.
Остаётся подставить числа: при 5 вершинах листьев от 2 до \(5 - 1 = 4\); при 50 вершинах — от 2 до \(50 - 1 = 49\); при 2024 вершинах — от 2 до \(2024 - 1 = 2023\).
Ответ: у дерева с 5 вершинами наименьшее число листьев 2, наибольшее 4; с 50 вершинами — 2 и 49; с 2024 вершинами — 2 и 2023.
