В дереве 14 вершин. Какое в нем может быть наибольшее число концевых вершин?

Решение:

В дереве наибольшее число концевых вершин достигается, когда дерево является путём. В таком случае, если дерево имеет \( n \) вершин, оно будет иметь \( n-1 \) ребро.

В дереве \( n = 14 \) вершин.

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

Однако, если рассматривать дерево, которое не является путём, например, звездообразное дерево, где одна центральная вершина соединена со всеми остальными, то число концевых вершин может быть равно \( n-1 \).

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

Если же мы можем построить дерево так, чтобы максимально использовать вершины как концевые, то можно представить себе структуру, где одна вершина имеет степень 2, а остальные \( 13 \) вершин имеют степень 1 (концевые). Это возможно, например, если построить длинную цепь и добавить одну вершину к одной из вершин, кроме конечных.

Давайте рассмотрим теорему о числе концевых вершин. В любом дереве с \( n \) вершинами, где \( n > 1 \), число концевых вершин \( L \) и число вершин степени \( k ≥ 2 \) \( I \) связаны соотношением \( L = I + 2 \).

Для \( n = 14 \), нам нужно максимизировать \( L \). Это произойдет, когда \( I \) будет минимально возможное.

Минимальное значение \( I \) равно 1 (одна неконцевая вершина, не являющаяся путем). Например, если у нас есть путь из 13 вершин, а 14-я вершина присоединена к одной из вершин пути, но не к концевой. Тогда у нас будет 2 концевые вершины пути и 1 новая концевая вершина, а также одна вершина с двойной степенью.

Рассмотрим другой вариант: одна центральная вершина и 13 других вершин, присоединенных к ней. Это даст 13 концевых вершин. Такая структура является деревом.

В дереве с \( n \) вершинами, сумма степеней всех вершин равна \( 2(n-1) \).

Пусть \( L \) — число концевых вершин (степени 1), а \( I \) — число внутренних вершин \(степени \u2265 2 \\).

\( L + I = n = 14 \)

Сумма степеней: \( L \cdot 1 + \sum_{i=1}^{I} deg(v_i) = 2(n-1) = 2(14-1) = 2  13 = 26 \)

\( L + \sum_{i=1}^{I} deg(v_i) = 26 \)

Подставим \( L = 14 - I \):

\( (14 - I) + \sum_{i=1}^{I} deg(v_i) = 26 \)

\( \sum_{i=1}^{I} deg(v_i) - I = 12 \)

\( \sum_{i=1}^{I} deg(v_i) - I = 12 \)

Чтобы максимизировать \( L \), нам нужно минимизировать \( I \). Минимальное \( I \) для дерева (кроме случая \( n=2 \)) равно 1.

Если \( I = 1 \), то \( L = 14 - 1 = 13 \).

Проверим: \( deg(v_1) \) — степень единственной внутренней вершины. \( deg(v_1) - 1 = 12 \) \( \implies deg(v_1) = 13 \).

Это соответствует звездообразному дереву, где одна центральная вершина соединена со всеми остальными 13 вершинами, которые являются концевыми.

Ответ: 13