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

Решение:

В любом дереве число вершин \( n \) связано с числом рёбер \( m \) соотношением \( m = n - 1 \).

Число концевых вершин (листьев) в дереве можно найти по формуле \( L = 2 + \sum_{i=1}^{k} (d_i - 2) \), где \( k \) — число внутренних вершин (вершин со степенью больше 2), а \( d_i \) — степень \( i \)-й внутренней вершины.

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

Рассмотрим дерево с \( n = 100 \) вершинами.

Самый простой случай — это когда у нас есть одна центральная вершина, соединённая со всеми остальными. В этом случае одна вершина будет иметь степень \( 99 \), а остальные \( 99 \) вершин будут иметь степень \( 1 \) (концевые вершины).

В этом случае количество концевых вершин равно \( 99 \).

Другой случай — это когда у нас есть дерево, похожее на цепь. Тогда у нас будет две концевые вершины.

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

В нашем случае \( n = 100 \). Если мы построим звездообразное дерево, одна вершина будет иметь степень \( 100 - 1 = 99 \), а остальные \( 100 - 1 = 99 \) вершин будут иметь степень \( 1 \).

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

Ответ: 99.