Задание 3. Какое наименьшее и какое наибольшее количество вершин степени 1 может быть у дерева, в котором 50 вершин?

Решение:

Привет! Давай разберём эту задачку про деревья.

Что такое дерево в математике? Это такой специальный граф, где между любыми двумя вершинами есть только один путь. Ещё одно важное свойство деревьев: в любом дереве с $$n$$ вершинами ровно $$n-1$$ рёбер.

Что такое степень вершины? Это количество рёбер, которые к ней подходят. У нас в задаче речь идёт про вершины степени 1, их ещё называют висячими вершинами.

Дано:

• $$n = 50$$ (количество вершин)

Найти:

• Наименьшее количество вершин степени 1.
• Наибольшее количество вершин степени 1.

Наибольшее количество вершин степени 1

Чтобы вершин степени 1 было как можно больше, мы должны постараться сделать так, чтобы большинство вершин имели только одно соединение. Это похоже на вытягивание в цепочку.

Представь, что мы строим дерево, добавляя вершины по одной:

• Если у нас 2 вершины, то это просто отрезок. Обе вершины имеют степень 1.
• Если у нас 3 вершины, то это тоже отрезок (или звезда с одной центральной вершиной, но тогда степени 1, 2, 1). В линейном варианте 2 вершины степени 1.
• Если у нас $$n$$ вершин, то максимальное количество вершин степени 1 достигается, когда дерево имеет вид цепочки (или пути). В этом случае все $$n$$ вершин, кроме двух крайних, будут иметь степень 2, а две крайние вершины будут иметь степень 1.

Итак, для $$n=50$$ вершин, наибольшее количество вершин степени 1 будет 2.

Маленькое замечание: Это верно для $$n ≥ 2$$. Если $$n=1$$, то вершина имеет степень 0, и вершин степени 1 нет.

Наименьшее количество вершин степени 1

Чтобы вершин степени 1 было как можно меньше, мы должны стремиться к тому, чтобы вершины имели степени больше 1.

Вспомним лемму о степенях: сумма степеней всех вершин в любом графе равна удвоенному числу рёбер ($$ \text{sum}(\text{deg}(v)) = 2E $$). Для дерева $$E = n-1$$.

Для $$n=50$$ вершин, $$E = 50-1 = 49$$. Сумма степеней всех вершин равна $$2 \times 49 = 98$$.

Пусть $$k$$ — количество вершин степени 1. Пусть $$m$$ — количество вершин степени больше 1.

Тогда $$k + m = 50$$.

Сумма степеней: $$k \times 1 + \text{сумма степеней вершин степени > 1} = 98$$.

Каждая из $$m$$ вершин имеет степень хотя бы 2.

Следовательно, $$k + 2m ≤ \text{сумма степеней} = 98$$.

Подставим $$m = 50 - k$$:

$$k + 2(50 - k) ≤ 98$$

$$k + 100 - 2k ≤ 98$$

$$100 - k ≤ 98$$

$$k ≥ 100 - 98$$

$$k ≥ 2$$

Значит, минимальное количество вершин степени 1 равно 2. Это достигается, например, когда дерево является