Часть 2 задача 11 страница 8, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого: вероятность и статистика

По свойству 3, в дереве со 100 вершинами ровно 99 рёбер.

а) Наибольшее число концевых вершин.

Рассмотрим дерево-«звезду»: одна центральная вершина соединена ребром с каждой из остальных 99 вершин. В таком дереве 99 рёбер и 100 вершин — это действительно дерево. Все 99 вершин, кроме центральной, имеют степень 1, то есть являются концевыми.

Больше 99 концевых вершин быть не может: если бы все 100 вершин были концевыми (степени 1), то сумма степеней равнялась бы 100. Но сумма степеней всех вершин равна удвоенному числу рёбер: .

Наибольшее число концевых вершин равно 99.

б) Наименьшее число концевых вершин.

Рассмотрим дерево-«путь» (цепь): вершины , где каждая соединена ребром с . В таком дереве 99 рёбер, вершины и имеют степень 1 (концевые), а все остальные — степень 2. Концевых вершин ровно 2.

Меньше 2 концевых вершин быть не может. По свойству 2, в конечном дереве с хотя бы одним ребром есть хотя бы одна концевая вершина. Покажем, что концевых вершин не может быть ровно 1. Пусть в дереве ровно одна концевая вершина степени 1. Сумма степеней всех вершин равна . Вершина вносит в сумму 1, а остальные 99 вершин имеют степень не менее 2, поэтому их суммарный вклад не менее . Тогда общая сумма степеней не менее . Противоречие. Значит, концевых вершин не менее 2.

Наименьшее число концевых вершин равно 2.

Ответ: а) наибольшее число концевых вершин — 99; б) наименьшее число концевых вершин — 2.