В дереве 84 вершины, сколько концевых вершин у него может быть?

Чтобы понять, сколько концевых (или листовых) вершин может быть в дереве с 84 вершинами, начнем с определения некоторых понятий.

Определение дерева:

• Дерево — это связная ациклическая структура, состоящая из вершин и рёбер. Каждая пара вершин соединена только одним путём.

Концевые (листовые) вершины:

• Концевые вершины — это вершины, у которых степень (количество рёбер, соединяющих её с другими вершинами) равна 1. То есть, это вершины, которые не соединены с другими вершинами, кроме одной.

Для анализа численного результата, воспользуемся следующим свойством деревьев:

• В дереве с \( n \) вершинами всегда существует хотя бы две листовые вершины.
• Общее количество рёбер в дереве с \( n \) вершинами равно \( n - 1 \). В данном случае: \[ Рёбер = 84 - 1 = 83 \]

Формула для количества конечных вершин: Согласно известной теореме о деревьях, количество листовых вершин \( L \) может быть определено как: \[ L = k + 1 \] где \( k \) — количество внутренних вершин (вершин с степенью 2 и более).

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

Рассчитываем количества: При максимальной конфигурации дерева (например, когда дыры между ними небольшие, такие как звёздное дерево):

• Если сосредоточить 83 рёбра на одной внутренней вершине, это дает много листьев. Простая конфигурация может быть:

• Вершина дерева: 1 (внутренняя) + 83 (лист) = 84.

Таким образом, максимальное количество листовых вершин в дереве из 84 вершин может достигать 83.

Ответ В дереве с 84 вершинами может быть максимум 83 концевых вершины.