Номер 11, страница 8, часть 2 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

11 В дереве 100 вершин. Какое в нём может быть:

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

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

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

По определению, дерево — это связный граф без циклов. Концевой вершиной (или листом) называется вершина, степень которой равна 1 (т.е. из нее выходит ровно одно ребро). В дереве с $n$ вершинами всегда $n-1$ ребер. В нашем случае $n=100$, значит, в дереве 99 ребер.

Согласно лемме о рукопожатиях, сумма степеней всех вершин графа равна удвоенному числу ребер. Для нашего дерева: $$ \sum_{i=1}^{100} \text{deg}(v_i) = 2 \times (100 - 1) = 2 \times 99 = 198 $$ где $\text{deg}(v_i)$ — степень $i$-ой вершины.

Пусть $k$ — число концевых вершин. Тогда в дереве есть $100-k$ неконцевых (внутренних) вершин. Степень каждой концевой вершины равна 1. Степень любой внутренней вершины не может быть меньше 2 (если бы она была равна 0, вершина была бы изолированной, а граф — несвязным; если бы она была равна 1, вершина была бы концевой).

Чтобы максимизировать число концевых вершин $k$, нужно минимизировать число внутренних вершин. В любом дереве с числом вершин больше двух должна быть хотя бы одна внутренняя вершина, иначе граф будет несвязным.

Рассмотрим случай, когда в дереве есть только одна внутренняя вершина. Тогда остальные $100 - 1 = 99$ вершин являются концевыми. Такая структура возможна: одна центральная вершина соединена ребрами с 99 остальными вершинами. Этот граф называется "звезда".

В такой конфигурации:

• Центральная (внутренняя) вершина имеет степень 99.
• Каждая из 99 остальных вершин имеет степень 1, то есть является концевой.

Сумма степеней равна $1 \times 99 + 99 \times 1 = 198$, что соответствует нашим расчетам. Этот граф является деревом, так как он связный и не содержит циклов.

Таким образом, максимальное возможное число концевых вершин равно 99.

Ответ: 99

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

Воспользуемся теми же основными положениями. Пусть $k$ — число концевых вершин. Сумма их степеней равна $k \times 1 = k$. В дереве $100-k$ внутренних вершин, и степень каждой из них не меньше 2. Следовательно, сумма их степеней не меньше чем $2 \times (100-k)$.

Общая сумма степеней всех вершин равна 198. Мы можем записать неравенство: $$ k + 2(100-k) \le 198 $$ $$ k + 200 - 2k \le 198 $$ $$ 200 - k \le 198 $$ $$ 2 \le k $$ Это означает, что в любом дереве со 100 вершинами должно быть как минимум 2 концевые вершины.

Теперь покажем, что существует дерево ровно с двумя концевыми вершинами. Чтобы минимизировать число концевых вершин, нужно, чтобы степени внутренних вершин были как можно меньше, то есть равны 2.

Рассмотрим случай, когда $k=2$. Тогда в дереве есть 2 концевые вершины и $100 - 2 = 98$ внутренних. Сумма степеней концевых вершин равна $2 \times 1 = 2$. Сумма степеней внутренних вершин должна быть $198 - 2 = 196$. Средняя степень внутренней вершины: $196 / 98 = 2$.

Поскольку минимальная степень внутренней вершины равна 2, то все 98 внутренних вершин должны иметь степень ровно 2. Граф, в котором есть 2 вершины степени 1, а остальные 98 вершин имеют степень 2, представляет собой простую цепь (путь).

Такой граф можно представить как $v_1 - v_2 - v_3 - \dots - v_{99} - v_{100}$. Вершины $v_1$ и $v_{100}$ являются концевыми (их степень равна 1), а все промежуточные 98 вершин ($v_2, \dots, v_{99}$) имеют степень 2. Этот граф является деревом, так как он связный и ацикличный.

Следовательно, минимально возможное число концевых вершин равно 2.

Ответ: 2