Страница 8 номер 11, ГДЗ по математике за 7, 8 и 9 класс к учебнику Высоцкого 2 часть. Углубленный уровень
В дереве 100 вершин. Какое в нём может быть: а) наибольшее число концевых вершин; б) наименьшее число концевых вершин?
Дерево со 100 вершинами конечное, поэтому рёбер в нём на одно меньше, чем вершин, — 99. Сумма степеней всех вершин равна \(2 \cdot 99 = 198\). Дерево связно и в нём больше одной вершины, поэтому степень каждой вершины не меньше 1.
а) Все 100 вершин концевыми быть не могут: тогда сумма степеней была бы равна 100, а не 198. Значит, концевых вершин не больше 99. Ровно 99 концевых вершин у дерева, в котором одна вершина соединена рёбрами с каждой из остальных 99 вершин: граф связный, а циклов в нём нет, потому что у каждого ребра один конец — вершина степени 1. Значит, наибольшее число концевых вершин — 99.
б) Если концевых вершин меньше двух, то хотя бы у 99 вершин степень не меньше 2, а у оставшейся — не меньше 1, и сумма степеней не меньше \(2 \cdot 99 + 1 = 199\), а не 198. Значит, концевых вершин не меньше двух. Ровно две концевые вершины у цепи из 100 вершин — это её концы. Значит, наименьшее число концевых вершин — 2.
Ответ: а) 99 концевых вершин; б) 2 концевые вершины.
В дереве 100 вершин. Какое в нём может быть: а) наибольшее число концевых вершин; б) наименьшее число концевых вершин?
Дерево со 100 вершинами конечное, поэтому рёбер в нём на одно меньше, чем вершин, — 99. Сумма степеней всех вершин вдвое больше числа рёбер: \(2 \cdot 99 = 198\). Дерево связно и в нём больше одной вершины, поэтому степень каждой вершины не меньше 1.
а) Все 100 вершин концевыми быть не могут: тогда сумма степеней была бы равна 100, а не 198. Значит, концевых вершин не больше 99. Ровно 99 концевых вершин у дерева, в котором одна вершина соединена рёбрами с каждой из остальных 99 вершин: граф связный, а циклов в нём нет, потому что у каждого ребра один конец — вершина степени 1. Значит, наибольшее число концевых вершин — 99.
б) Если концевых вершин меньше двух, то хотя бы у 99 вершин степень не меньше 2, а у оставшейся — не меньше 1, и сумма степеней не меньше \(2 \cdot 99 + 1 = 199\), а не 198. Значит, концевых вершин не меньше двух. Ровно две концевые вершины у цепи из 100 вершин — это её концы. Значит, наименьшее число концевых вершин — 2.
Ответ: а) 99 концевых вершин; б) 2 концевые вершины.
