ГДЗ по вероятности и статистике, 10 класс, Высоцкий, номер 95: Изоморфные графы. Плоские и планарные графы
Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание — Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.
Илья Морозов, методист по вероятности Шпаргача обновлено 11 сентября 2026
Условие
В дереве 1001 вершина. Найти
а) наибольшее число концевых вершин
б) наименьшее число концевых вершин.
Номер как в учебнике. Условие — полный пересказ редакции: те же пункты, числа и факты, не цитата из книги.
Пошаговое решение
Рассмотрим свойства дерева с n вершинами. В любом дереве число рёбер равно m=n-1. Сумма степеней всех вершин равна удвоенному числу рёбер: ∑°(v)=2m=2(n-1).
Шаг 1. Анализ пункта а): наибольшее число концевых вершин
Концевая (листовая) вершина — это вершина степени 1. Чтобы максимизировать количество таких вершин, нужно минимизировать степень остальных вершин, но при этом сохранить связность и отсутствие циклов.
Представим дерево в виде «звезды»: одна центральная вершина соединена со всеми остальными. Пусть k — число концевых вершин. Тогда одна вершина имеет степень k, а остальные k вершин имеют степень 1. Общее число вершин n=k+1.
В нашем случае n=1001. Значит, k+1=1001, откуда k=1000. Проверим сумму степеней: 1000·1+1·1000=2000. Число рёбер m=1000, сумма степеней 2m=2000. Всё сходится.
Таким образом, наибольшее число концевых вершин равно 1000.
Шаг 2. Анализ пункта б): наименьшее число концевых вершин
Чтобы минимизировать число концевых вершин, нужно сделать дерево максимально «вытянутым», то есть превратить его в цепочку (путь). В таком графе две крайние вершины имеют степень 1, а все промежуточные вершины имеют степень 2.
Пусть l — число концевых вершин. Для любого дерева с более чем одной вершиной существует хотя бы две листовые вершины. Это следует из того, что если начать движение от любой вершины по рёбрам, не посещая уже пройденные, мы неизбежно придём в тупик (вершину степени 1), так как циклов нет.
В цепи из 1001 вершины ровно 2 вершины являются концевыми (степень 1), а 999 вершин имеют степень 2. Сумма степеней: 2·1+999·2=2+1998=2000. Число рёбер m=1000, 2m=2000. Условие выполняется.
Меньше двух концевых вершин в дереве быть не может (иначе это был бы цикл или изолированная вершина, что противоречит определению дерева).
Таким образом, наименьшее число концевых вершин равно 2.
а) 1000
б) 2
Краткий ответ сверен с разделом «Ответы» учебника.
Как решение?
Двойная оценка: понятность и подробность. Можно выбрать одно или оба.
У вас другое условие?
Загрузите фото — учтём ваши числа и редакцию.
Частые вопросы
Это точный номер 95 из моего учебника?
Номер совпадает с учебником «Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание», Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.. Формулировка — пересказ редакции, не дословная цитата. Если в вашей редакции другие числа — загрузите фото.
Какой ответ в задании 95?
Краткий ответ: а) 1000 б) 2.
Как пользоваться этим разбором?
Сначала прочитайте условие и чертёж, затем шаги решения по порядку и сверьте свой ход с кратким ответом внизу.
Какой учебник имеется в виду?
«Математическая вертикаль: 10-11-е классы: углублённый уровень: учебник по вероятности и статистике для физико-математических классов; 1-е издание», Высоцкий И.Р., Ященко И.В.; под редакцией Ященко И.В.. Проверьте часть, год и автора на обложке. Тема в учебнике: § 10. Изоморфные графы. Плоские и планарные графы.
Можно ли списать ответ без решения?
Лучше сначала решить самостоятельно, а разбор использовать для проверки хода и поиска ошибки.