Страница 59 номер 95, ГДЗ по математике за 10 и 11 класс к учебнику Высоцкого. Вероятность и статистика базовый и углубленный уровни
В дереве 1001 вершина. Каково может быть: а) наибольшее число концевых вершин; б) наименьшее число концевых вершин?
Рёбер в дереве \(1001 - 1 = 1000\), сумма степеней всех вершин \(2 \cdot 1000 = 2000\).
Пусть концевых вершин \(k\). Степень каждой вершины не меньше 1, а степень каждой неконцевой вершины не меньше 2, поэтому сумма степеней не меньше \[1 \cdot k + 2 \cdot (1001 - k) = 2002 - k.\]
Отсюда \(2002 - k \leqslant 2000\), то есть \(k \geqslant 2\). Все 1001 вершина концевой быть не может: сумма степеней равнялась бы 1001, а она равна 2000. Значит, \(k \leqslant 1000\).
а) Наибольшее значение \(k = 1000\) достигается на звезде: вершина \(A\) соединена ребром с каждой из 1000 остальных вершин. Граф связен, в нём 1000 рёбер, циклов нет — каждое ребро содержит вершину \(A\), а в цикле вершины не повторяются. Степень каждой вершины, кроме \(A\), равна 1, значит, концевых вершин 1000.
б) Наименьшее значение \(k = 2\) достигается на цепи \(V_1V_2\ldots V_{1001}\), в которой ребро соединяет вершины с соседними номерами: концевые в ней только \(V_1\) и \(V_{1001}\), степень каждой из остальных вершин равна 2.
Ответ: а) наибольшее число концевых вершин равно 1000; б) наименьшее число концевых вершин равно 2.
В дереве 1001 вершина. Каково может быть: а) наибольшее число концевых вершин; б) наименьшее число концевых вершин?
В конечном дереве вершин на одну больше, чем рёбер, поэтому рёбер в нём \(1001 - 1 = 1000\), а сумма степеней всех вершин равна удвоенному числу рёбер, то есть \(2 \cdot 1000 = 2000\).
Пусть в дереве \(k\) концевых вершин. Изолированных вершин в нём нет (дерево связно, а вершин больше одной), поэтому степень каждой вершины не меньше 1, а степень каждой неконцевой вершины не меньше 2. Значит, сумма степеней не меньше \[1 \cdot k + 2 \cdot (1001 - k) = 2002 - k.\]
Отсюда \(2002 - k \leqslant 2000\), то есть \(k \geqslant 2\). Кроме того, все 1001 вершина концевой быть не может: тогда сумма степеней равнялась бы 1001, а она равна 2000. Значит, \(k \leqslant 1000\).
а) Наибольшее значение \(k = 1000\) достигается на звезде: вершина \(A\) соединена ребром с каждой из 1000 остальных вершин. Такой граф связен и содержит 1000 рёбер; циклов в нём нет, потому что каждое ребро содержит вершину \(A\), а в цикле вершины не повторяются, и через \(A\) цикл прошёл бы дважды. Значит, это дерево, и в нём 1000 концевых вершин: степень каждой вершины, кроме \(A\), равна 1.
б) Наименьшее значение \(k = 2\) достигается на цепи \(V_1V_2\ldots V_{1001}\), в которой ребро соединяет вершины с соседними номерами. Это дерево, и в нём концевые вершины только \(V_1\) и \(V_{1001}\): степень каждой из остальных вершин равна 2.
Ответ: а) наибольшее число концевых вершин равно 1000; б) наименьшее число концевых вершин равно 2.
